改善 SortedDictionary 的访问时间

Question

我有 200 万件商品SortedDictionary<string, MyClass>

我已经完成了以下操作并且需要很长时间，有什么想法吗？

for(int i = 0; i<dic.Count-1; i++)
{
    Debug.WriteLine(dic.ElementAt(i).Value.ToString());
}

Answer 1

该类SortedDictionary<TKey, TValue>不直接支持通过索引（快速）检索；它在内部实现为二叉搜索树。因此，对 LINQ 方法的每次调用都会创建一个新的枚举器，该枚举器从头开始Enumerable.ElementAt迭代集合中键值对（按键排序）表示的序列的每个值，直到到达所需的索引。这意味着循环在完成之前必须拉取 （大约 2 万亿）个元素，使其（至少）时间复杂度呈二次方。1 + 2 + 3 + ... + Count

试试这个，它应该以大致线性的时间运行：

foreach(var myClass in dic.Values)
   Debug.WriteLine(myClass);

如果您确实希望通过索引快速访问（从提供的代码来看，似乎没有任何理由表明这一点），请考虑使用 aSortedList<TKey, TValue>代替。您应该评估此选择的缺点（非追加插入和删除速度较慢）。

我还注意到循环条件i < dic.Count - 1不是更常见的i < dic.Count. 这要么是一个相差一的错误，要么您打算不考虑字典中的最后一个值。在后一种情况下，您可以维护一个局部变量作为计数器，或者使用 LINQ：

foreach(var myClass in dic.Values.Take(dic.Count - 1))
   Debug.WriteLine(myClass);