SortedDictionary与Dictionary相比表现不佳的意外情况

Question

我不明白为什么使用 SortedDictionary 在设置和检索值方面的性能大约比 Dictionary 慢了5倍。我预计插入和删除会更慢，但不是更新或检索。我已经测试过 .Net 3.5 和 .Net 4.0 发布编译的代码。已经预先计算好了一个随机键数组，以确保随机访问并非造成差异的原因。

下面是测试的场景：

1. 使用[key]访问器进行每个值的顺序更新
2. 使用[key]访问器进行每个值的顺序访问
3. 使用TryGetValue进行每个值的顺序访问
4. 使用[key]访问器进行每个值的随机访问
5. 使用TryGetValue进行每个值的随机访问

有人知道为什么会有这种性能差异吗？

如果我做错或愚蠢的事情，请指出。

示例代码：只需将 Dictionary 替换为 SortedDictionary 即可测试差异。

    const int numLoops = 100;
    const int numProperties = 30;
    const int numInstances = 1000;

    static void DictionaryBench(int numLoops, int numValues, int numInstances, string[] keyArray)
    {
        Stopwatch sw = new Stopwatch();
        double total = 0.0d;

        for (int j = 0; j < numLoops; j++)
        {
            //sw.Start();
            Dictionary<string, object> original = new Dictionary<string, object>(numValues);
            for (int i = 0; i < numValues; i++)
            {
                original.Add(String.Format("Key" + i.ToString()), "Value0:" + i.ToString());
            }
            List<Dictionary<string, object>> collectionList = new List<Dictionary<string, object>>(numInstances);
            for (int i = 0; i < numInstances; i++)
            {
                collectionList.Add(new Dictionary<string, object>(original));
            }
            sw.Start();
            //Set values on each cloned instance to uniqe values using the same keys
            for (int k = 0; k < numInstances; k++)
            {
                for (int i = 0; i < numValues; i++)
                {
                    collectionList[k]["Key" + i.ToString()] = "Value" + k.ToString() + ":" + i.ToString();
                }
            }

            //Access each unique value
            object temp;
            for (int k = 0; k < numInstances; k++)
            {
                for (int i = 0; i < numValues; i++)
                {
                    temp = collectionList[k]["Key" + i.ToString()];
                }
            }
            //Random access
            //sw.Start();
            for (int k = 0; k < numInstances; k++)
            {
                for (int i = 0; i < numValues; i++)
                {
                    collectionList[k].TryGetValue(keyArray[i],out temp);
                }
            }
            sw.Stop();
            total += sw.ElapsedMilliseconds;
            sw.Reset();
        }

- Firestrand

Answer 1

SortedDictionary 使用二分查找，时间复杂度为 O(log n)。
Dictionary 使用哈希表，时间复杂度为 O(1)。

因此，Dictionary 查找更快。

使用字符串作为键的差异会更大，比较字符串的成本很高。
一个 Dictionary 只需要迭代两次字符串（如果存在哈希冲突，则可能需要更多次）- 一次计算哈希码，一次确保它是完全匹配的。而一个 SortedDictionary 将为每个比较迭代字符串。

- SLaks

Answer 2

我认为这并不奇怪。其他人也得到了相同的结果。

我认为为什么一个会比另一个慢很容易理解。SortedDictionary正在执行更多操作，即排序，而Dictionary没有进行排序，因此速度更快。

唯一真正测试性能的方法就是你上面进行的测试。我认为你在做任何错误的事情。

- David Morton

---

我希望很快能够比较B-Tree-Sorted-Dictionary和SortedDictionary在包含超过1,000,000个对象的数据集上的性能，以期提高查找内存数据集中匹配对象的访问速度。这可能会变得有趣。 - Wonderbird