二分查找性能对比：自定义比较器法与long列表法测试分析

我手头有大约200万条有序的DataPoint类型记录，需要找出与指定时间戳最接近的单条数据。数据定义如下：

public class DataPoint
{
    public long OpenTimeTs;
}

我实现了三种逻辑一致的查找方法，但对它们的性能表现产生了疑惑，下面逐一说明：

private DataPoint BinaryFindClosest(List<DataPoint> candles, List<long> times, long dateToFindMs)
{
    int index = times.BinarySearch(dateToFindMs);

    if (index >= 0)
        return candles[index];

    // If not found, List.BinarySearch returns the complement 
    // of the index where the element should have been.
    index = ~index;

    // This date search for is larger than any
    if (index == times.Count)
        return candles[index - 1];

    // The date searched is smaller than any in the list.
    if (index == 0)
        return candles[0];

    if (Math.Abs(dateToFindMs - times[index - 1]) < Math.Abs(dateToFindMs - times[index]))
        return candles[index - 1];
    else
        return candles[index];
}

逻辑和方法1基本一致，但直接对DataPoint列表进行二分查找，通过自定义比较器来对比时间戳：

private DataPoint BinaryFindClosest2(List<DataPoint> candles, DataPoint toFind)
{
    var comparer = Comparer<DataPoint>.Create((x, y) => x.OpenTimeTs > y.OpenTimeTs ? 1 : x.OpenTimeTs < y.OpenTimeTs ? -1 : 0);

    int index = candles.BinarySearch(toFind, comparer);

    if (index >= 0)
        return candles[index];

    // If not found, List.BinarySearch returns the complement 
    // of the index where the element should have been.
    index = ~index;

    // This date search for is larger than any
    if (index == candles.Count)
        return candles[index - 1];

    // The date searched is smaller than any in the list.
    if (index == 0)
        return candles[0];

    if (Math.Abs(toFind.OpenTimeTs - candles[index - 1].OpenTimeTs) < Math.Abs(toFind.OpenTimeTs - candles[index].OpenTimeTs))
        return candles[index - 1];
    else
        return candles[index];
}

这是我之前一直在用的遍历查找方式：

private DataPoint FindClosest(List<DataPoint> candles, DataPoint toFind)
{
    long timeToFind = toFind.OpenTimeTs;

    int smallestDistanceIdx = -1;
    long smallestDistance = long.MaxValue;

    for (int i = 0; i < candles.Count(); i++)
    {
        var candle = candles[i];
        var distance = Math.Abs(candle.OpenTimeTs - timeToFind);
        if (distance <= smallestDistance)
        {
            smallestDistance = distance;
            smallestDistanceIdx = i;
        }
        else
        {
            break;
        }
    }

    return candles[smallestDistanceIdx];
}

最开始我手动写测试代码验证时，发现方法2的性能居然是最优的——这和我“long列表二分查找应该更快”的直觉完全不符，当时特别疑惑。

初始手动测试代码（Release模式） #

var candles = AppState.GetLoadSymbolData();
var times = candles.Select(s => s.OpenTimeTs).ToList();

var dateToFindMs = candles[candles.Count / 2].OpenTimeTs;
var candleToFind = new DataPoint() { OpenTimeTs = dateToFindMs };

var numberOfFinds = 100_000;

var sw = Stopwatch.StartNew();
for (int i = 0; i < numberOfFinds; i++)
{
    var foundCandle = BinaryFindClosest(candles, times, dateToFindMs);
}
sw.Stop();
var elapsed1 = sw.ElapsedMilliseconds;

sw.Restart();
for (int i = 0; i < numberOfFinds; i++)
{
    var foundCandle = BinaryFindClosest2(candles, candleToFind);
}
sw.Stop();
var elapsed2 = sw.ElapsedMilliseconds;

sw.Restart();
for (int i = 0; i < numberOfFinds; i++)
{
    var foundCandle = FindClosest(candles, candleToFind);
}
sw.Stop();
var elapsed3 = sw.ElapsedMilliseconds;

Console.WriteLine($"Elapsed 1: {elapsed1} ms");
Console.WriteLine($"Elapsed 2: {elapsed2} ms");
Console.WriteLine($"Elapsed 3: {elapsed3} ms");

初始测试结果 #

• Elapsed 1: 19 ms
• Elapsed 2: 1 ms
• Elapsed 3: 60678 ms

这个结果显然有问题，于是我改用专业性能测试工具BenchmarkDotNet重新测试，终于得到了准确的结果：

结论 #

原来初始测试的顺序影响了结果（比如JIT编译、缓存等因素），实际性能排序是：方法1 > 方法2 > 方法3，遍历法始终是最慢的，就算优化后性能依旧垫底。

这里最大的教训就是：性能测试一定要用专业工具，手动写Stopwatch很容易因为各种因素得到错误结论。

内容的提问来源于stack exchange，提问作者Alex