Improving access time on SortedDictionary

Question

I have 2 million items in a SortedDictionary<string, MyClass>

I did the following and take age, any ideas?

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

Answer 1

The SortedDictionary<TKey, TValue> does not support direct (fast) index search; it is internally implemented as a binary search tree. Therefore, every call to the LINQ Enumerable.ElementAt method that you have creates a new counter that iterates over each value of the sequence represented by the key-value pairs in the collection (sorted by key) from the very beginning until it reaches the desired index. This means that the loop will have to pull out something like 1 + 2 + 3 + ... + Count (about 2 trillion) elements before it is completed, making it (at least) quadratic in its time complexity.

Try this instead, which should run in approximately linear time:

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

If you really need quick access by index (from the provided code, there seems to be no reason to indicate this), consider using SortedList<TKey, TValue> . There are drawbacks to this choice (slow non-added inserts and deletes) that you should evaluate.

I also noticed that the loop condition i < dic.Count - 1 , and not the more general i < dic.Count . This is either a "one by one" error, or perhaps you are not going to consider the last meaning in the dictionary. In the latter case, you can maintain a local variable serving as a counter, or using LINQ:

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

Answer 2

foreach may be faster since you are not using an indexer

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

Also, in terms of speed, Debug.Writeline is probably not the best option (what are you going to do with 2 million debugging entries anyway?). Consider writing to a file, database, etc.

EDIT Looking at the reflector, searching for a value in SortedDictionry comes down to a binary search:

 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; } 

Implementing an Iteration of SortedDictionary seems a bit more complicated:

 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; } 

It seems to support a stack whose top element is the smallest (or largest, depending on direction), and thus always the one that needs to be popped up and returned during the iteration. I did not do any complexity analysis, but it should be significantly more efficient than running a binary search every time.

Answer 3

Use foreach :

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

I am sure that debugging output takes longer than dictionary lookups.