c# - 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);

1. 使用 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 消除了额外的字典查找
• 所有基准测试方法都以 List 的形式返回结果，以使其公平