SortedDictionary 与字典排序的性能对比

Question

我有一个对象列表。这些对象具有许多属性，包括价格和数量。我需要创建一个带有键“价格”和值“数量”的新字典。如果两个对象具有相同的价格，则生成的字典应将价格作为键，将两个对象的数量总和作为值。据我所知，我可以通过两种方式做到这一点。

1. 使用Dictionary数据结构，对最终的字典进行排序：

var result = new Dictionary<int, int>();
foreach(List<object> obj in list) {
    if(result.ContainsKey(obj.price)) {
        result[price] += quantity;
    }
    else {
        result[price] = quantity;
    }
}
result = result.OrderBy(x => x.Key);

2. 使用SortedDictionary：

var result = new SortedDictionary<int, int>();
foreach(List<object> obj in list) {
    if(result.ContainsKey(obj.price)) {
        result[price] += quantity;
    }
    else {
        result[price] = quantity;
    }
}

在第一种方法中，时间复杂度为 ，ContainsKey对于O(1)排序， order by 使用时间复杂度为 的快速排序O(nlogn)。所以总的时间复杂度是O(nlogn)。在第二种方法中，ContainsKeysortedDictionary 已经接受了O(log n)，并且由于我n多次重复此操作，因此总复杂度为O(nlogn)。根据我的计算，我觉得使用这两种方法应该花费相同的时间。如果我错了，请纠正我。而且，如果我错了，哪种方法具有更好的性能？

Answer 1

1 通常会更快。排序一次比维护一个已排序的字典更容易。

Big-O 复杂度可能相同，但相同的复杂度并不意味着相同的性能。

基准测试结果：

|      Method |     Mean |    Error |   StdDev |  Gen 0 | Gen 1 | Gen 2 | Allocated |
|------------ |---------:|---------:|---------:|-------:|------:|------:|----------:|
|        Dict | 361.7 ns |  7.07 ns |  7.26 ns | 0.1554 |     - |     - |     488 B |
| DictOrderBy | 499.9 ns |  9.66 ns |  9.04 ns | 0.2651 |     - |     - |     832 B |
|  SortedDict | 943.7 ns | 18.26 ns | 22.42 ns | 0.2241 |     - |     - |     704 B |

代码： https: //gist.github.com/ptupitsyn/71eefbdb607ce3f9ddfae2f5e099184e

笔记：

• TryGetValue消除了额外的字典查找
• 所有基准测试方法都会返回结果，以List使其公平