SortedDictionary 的性能与对字典进行排序

Question

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

使用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);

使用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)。在第二种方法中，sortedDictionary 的 ContainsKey 已经使用了 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 消除了额外的字典查找
所有基准测试方法 return 的结果都是 List 以使其公平

SortedDictionary 的性能与对字典进行排序

Performance of SortedDictionary vs sorting a Dictionary

c#

performance

dictionary

time-complexity

sorteddictionary