SortedList性能

Question

我发现我的应用程序(使用SortedList )性能很差。所以我决定努力提高我的应用程序的性能。我创建了FastSortedList类，我认为它比原来的类要快。

public class FastSortedList
{
    IComparer _comparer;
    List> _list = new List>();
    Dictionary _dict = new Dictionary();
    public FastSortedList(IComparer comparer)
    {
        _comparer = comparer ?? Comparer.Default;
    }

    public int Count => _list.Count;

    public IEnumerable Values => _list.Select(i => i.Value);

    public void Add(TKey key, TValue value)
    {
        if (_dict.ContainsKey(key))
            throw new ArgumentException("An entry with the same key already exists.");
        int index = BinarySearch(key);
        if (index < 0)
        {
            _list.Insert(~index, new KeyValuePair(key, value));
        }
        else
        {
            _list.Insert(index, new KeyValuePair(key, value));
        }
        _dict[key] = value;
    }

    public int IndexOfKey(TKey key)
    {
        if (_dict.ContainsKey(key))
            return BinarySearch(key);
        return -1;
    }

    public void RemoveAt(int index)
    {
        if (index < 0)
            return;
        var item = _list[index];
        _list.RemoveAt(index);
        _dict.Remove(item.Key);
    }

    private int BinarySearch(TKey key)
    {
        int lo = 0;
        int hi = _list.Count - 1;
        while (lo <= hi)
        {
            int i = GetMedian(lo, hi);
            int c = _comparer.Compare(_list[i].Key, key);
            if (c == 0)
                return i;
            if (c < 0)
            {
                lo = i + 1;
            }
            else
            {
                hi = i - 1;
            }
        }
        return ~lo;
    }

    private int GetMedian(int lo, int hi)
    {
        return lo + ((hi - lo) >> 1);
    }
}

用过的比较器：

public class TestComparer : IComparer
{
    public int Compare(string x, string y)
    {
        return string.Compare(x, y);
    }
}

与Stopwatch:

的比较

private static void CompareWithStopwatch()
{
    int index;
    IEnumerable values;

    FastSortedList fast = new FastSortedList(new TestComparer());

    Stopwatch sw = new Stopwatch();
    sw.Start();
    for (int i = 0; i < 1000000; i++)
    {
        fast.Add($"test{i}", i);
    }
    sw.Stop();
    Console.WriteLine($"FastSortedList: Populate records: elapsed time: {sw.Elapsed.TotalSeconds} sec, total records: {fast.Count}");

    sw.Start();
    index = fast.IndexOfKey("test745723");
    sw.Stop();
    Console.WriteLine($"FastSortedList: IndexOfKey: key: 'test745723', index: {index}, elapsed time: {sw.Elapsed.TotalSeconds} sec");

    sw.Start();
    fast.RemoveAt(index);
    sw.Stop();
    Console.WriteLine($"FastSortedList: RemoveAt: key: 'test745723', index: {index} elapsed time: {sw.Elapsed.TotalSeconds} sec");

    sw.Start();
    values = fast.Values;
    sw.Stop();
    Console.WriteLine($"FastSortedList: Get values, elapsed time: {sw.Elapsed.TotalSeconds} sec");


    SortedList sorted = new SortedList(new TestComparer());

    sw.Start();
    for (int i = 0; i < 1000000; i++)
    {
        sorted.Add($"test{i}", i);
    }
    sw.Stop();
    Console.WriteLine($"SortedList: Populate records: elapsed time: {sw.Elapsed.TotalSeconds} sec, total records: {sorted.Count}");

    sw.Start();
    index = sorted.IndexOfKey("test745723");
    sw.Stop();
    Console.WriteLine($"SortedList: IndexOfKey: key: 'test745723', index: {index}, elapsed time: {sw.Elapsed.TotalSeconds} sec");

    sw.Start();
    sorted.RemoveAt(index);
    sw.Stop();
    Console.WriteLine($"SortedList: RemoveAt: key: 'test745723', index: {index} elapsed time: {sw.Elapsed.TotalSeconds} sec");

    sw.Start();
    values = sorted.Values;
    sw.Stop();
    Console.WriteLine($"SortedList: Get values, elapsed time: {sw.Elapsed.TotalSeconds} sec");

    FastSortedList fastRevrese = new FastSortedList(new TestComparer());

    sw.Start();
    for (int i = 999999; i >= 0; i--)
    {
        fastRevrese.Add($"test{i}", i);
    }
    sw.Stop();
    Console.WriteLine($"FastSortedList: fastRevrese - Populate records: elapsed time: {sw.Elapsed.TotalSeconds} sec, total records: {fastRevrese.Count}");

    sw.Start();
    index = fastRevrese.IndexOfKey("test745723");
    sw.Stop();
    Console.WriteLine($"FastSortedList: fastRevrese - IndexOfKey: key: 'test745723', index: {index}, elapsed time: {sw.Elapsed.TotalSeconds} sec");

    sw.Start();
    fastRevrese.RemoveAt(index);
    sw.Stop();
    Console.WriteLine($"FastSortedList: fastRevrese - RemoveAt: key: 'test745723', index: {index} elapsed time: {sw.Elapsed.TotalSeconds} sec");

    sw.Start();
    values = fastRevrese.Values;
    sw.Stop();
    Console.WriteLine($"SortedList: fastRevrese - Get values, elapsed time: {sw.Elapsed.TotalSeconds} sec");

    SortedList sortedRevrese = new SortedList(new TestComparer());

    sw.Start();
    for (int i = 999999; i >= 0; i--)
    {
        sortedRevrese.Add($"test{i}", i);
    }
    sw.Stop();
    Console.WriteLine($"SortedList: sortedRevrese Populate records: elapsed time: {sw.Elapsed.TotalSeconds} sec, total records: {sortedRevrese.Count}");

    sw.Start();
    index = sortedRevrese.IndexOfKey("test745723");
    sw.Stop();
    Console.WriteLine($"SortedList: sortedRevrese - IndexOfKey: key: 'test745723', index: {index}, elapsed time: {sw.Elapsed.TotalSeconds} sec");

    sw.Start();
    sortedRevrese.RemoveAt(index);
    sw.Stop();
    Console.WriteLine($"SortedList: sortedRevrese - RemoveAt: key: 'test745723', index: {index} elapsed time: {sw.Elapsed.TotalSeconds} sec");

    sw.Start();
    values = sortedRevrese.Values;
    sw.Stop();
    Console.WriteLine($"SortedList: sortedRevrese - Get values, elapsed time: {sw.Elapsed.TotalSeconds} sec");
}

结果：

与Benchmark.NET:

的比较

public class RaceBenchmark
{
    const int LENGTH = 100000;

    [Benchmark]
    public void InsertToSortedList()
    {
        SortedList sorted = new SortedList(new TestComparer());
        for (int i = 0; i < LENGTH; i++)
        {
            sorted.Add($"test{i}", i);
        }
    }

    [Benchmark]
    public void InsertToFastSortedList()
    {
        FastSortedList fast = new FastSortedList(new TestComparer());
        for (int i = 0; i < LENGTH; i++)
        {
            fast.Add($"test{i}", i);
        }
    }

    [Benchmark]
    public void SortedListIndexOfKey()
    {
        SortedList sorted = new SortedList(new TestComparer());
        for (int i = 0; i < LENGTH; i++)
        {
            sorted.Add($"test{i}", i);
        }
        var sortedListIndex = sorted.IndexOfKey("test4321");
    }

    [Benchmark]
    public void FastSortedListIndexOfKey()
    {
        FastSortedList fast = new FastSortedList(new TestComparer());
        for (int i = 0; i < LENGTH; i++)
        {
            fast.Add($"test{i}", i);
        }
        var fastIndex = fast.IndexOfKey("test4321");
    }

    [Benchmark]
    public void SortedListRemoveAt()
    {
        SortedList sorted = new SortedList(new TestComparer());
        for (int i = 0; i < LENGTH; i++)
        {
            sorted.Add($"test{i}", i);
        }
        var sortedListIndex = sorted.IndexOfKey("test4321");
        sorted.RemoveAt(sortedListIndex);
    }

    [Benchmark]
    public void FastSortedListRemoveAt()
    {
        FastSortedList fast = new FastSortedList(new TestComparer());
        for (int i = 0; i < LENGTH; i++)
        {
            fast.Add($"test{i}", i);
        }
        var fastIndex = fast.IndexOfKey("test4321");
        fast.RemoveAt(fastIndex);
    }


    [Benchmark]
    public void SortedListGetValues()
    {
        SortedList sorted = new SortedList(new TestComparer());
        for (int i = 0; i < LENGTH; i++)
        {
            sorted.Add($"test{i}", i);
        }
        var values = sorted.Values;
    }

    [Benchmark]
    public void FastSortedLisGetValues()
    {
        FastSortedList fast = new FastSortedList(new TestComparer());
        for (int i = 0; i < LENGTH; i++)
        {
            fast.Add($"test{i}", i);
        }
        var values = fast.Values;
    }
}

结果：

我将很高兴得到这个实现的代码审查。

Answer 1

GetMedian -- (请不要称它为“中位数”；虽然它是索引的中值，但它不是中间键。)

return lo + ((hi - lo) >> 1);

-->

return (hi + lo) >> 1;

你知道你的编译是否会自动“内联”函数吗？如果没有，那就自己做吧：

int i = GetMedian(lo, hi);

-->

int i = (hi + lo) >> 1;

想想频率..。

        if (c == 0) ...
        if (c < 0) ...
        else ...

如果项目数量较低，最好先测试0，但我不认为这是“典型的”情况。所以，重新安排两个测试和其他测试。

此外，特定的"test745723“键每次都会下降N个级别。当N很小时，您的代码就“快”了。因此，我对只涉及一个键的基准测试结果表示怀疑。