上SortedDictionary

Question

提高訪問時間我有一個SortedDictionary<string, MyClass>

2名百萬的項目我已經做了以下和需要年齡，任何想法？

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

Answer 1

SortedDictionary<TKey, TValue>類不直接支持（快速）按索引檢索;它在內部實現爲二叉搜索樹。因此，每次調用LINQ Enumerable.ElementAt方法時，都會創建一個新的枚舉器，它將從集合中的鍵值對（由鍵排序）開始中的每個值進行迭代，直到達到所需的值指數。這意味着該循環在完成之前將不得不拉動類似於1 + 2 + 3 + ... + Count（大約2萬億）的元素，使其在時間複雜度上至少爲二次方。

試試這個，這應該運行在大致呈線性時間：

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

如果你真的想通過索引快速訪問（從提供的代碼，也似乎沒有任何理由表明這一點），請考慮使用SortedList<TKey, TValue>代替。這種選擇有一些缺點（較慢的非附加插入和刪除），你應該評估。

我還注意到循環條件是i < dic.Count - 1而不是更常見的i < dic.Count。這是一個錯誤的錯誤，或者你打算不考慮字典中的最後一個值。在後一種情況下，可以維持一個局部變量作爲計數器，或使用LINQ：

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

Answer 2

foreach可能會更快，因爲你不使用索引

foreach (var value in dic.Values) 
    Debug.Writeline(value) 

此外，至於速度方面，Debug.Writeline可能不是最好的選擇（那你打算怎麼辦有200萬調試跟蹤條目？）。考慮寫入文件，數據庫等

編輯看着反射器，發現在SortedDictionry值歸結爲一個二進制搜索：

internal virtual Node<T> FindNode(T item) 
{ 
    int num; 
    for (Node<T> node = this.root; node != null; node = (num < 0) ? node.Left : node.Right) 
    { 
     num = this.comparer.Compare(item, node.Item); 
     if (num == 0) 
     { 
      return node; 
     } 
    } 
    return null; 
} 

SortedDictionary的迭代的實現似乎有點更多涉及：

public bool MoveNext() 
{ 
    this.tree.VersionCheck(); 
    if (this.version != this.tree.version) 
    { 
     ThrowHelper.ThrowInvalidOperationException(ExceptionResource.InvalidOperation_EnumFailedVersion); 
    } 
    if (this.stack.Count == 0) 
    { 
     this.current = null; 
     return false; 
    } 
    this.current = this.stack.Pop(); 
    SortedSet<T>.Node item = this.reverse ? this.current.Left : this.current.Right; 
    SortedSet<T>.Node node2 = null; 
    SortedSet<T>.Node node3 = null; 
    while (item != null) 
    { 
     node2 = this.reverse ? item.Right : item.Left; 
     node3 = this.reverse ? item.Left : item.Right; 
     if (this.tree.IsWithinRange(item.Item)) 
     { 
      this.stack.Push(item); 
      item = node2; 
     } 
     else 
     { 
      if ((node3 == null) || !this.tree.IsWithinRange(node3.Item)) 
      { 
       item = node2; 
       continue; 
      } 
      item = node3; 
     } 
    } 
    return true; 
} 

它似乎維持的堆疊，其頂部元件爲最小（或最大，這取決於方向）之一，因此總是一個到被彈出和ITER期間返回通貨膨脹。我沒有做過任何複雜性分析，但肯定會比每次運行二進制搜索更有效率。

Answer 3

使用foreach：

foreach (var pair in d) 
     Debug.WriteLine(pair.Value); 

我敢打賭，調試輸出時間比字典查找更多的時間雖然。