As as human I always thought that lookup in something sorted is the way faster than lookup in not sorted.
But looking at this http://dotnetperls.com/sorteddictionary I can say that I was wrong.
Maybe anyone can explain why it is so ?
views:
103answers:
1
+12
A:
The unsorted dictionary is probably a hash map so lookup is almost O(1) assuming not too many collisions, while a lookup in a sorted list is best case O(log N)
Martin Beckett
2009-11-08 19:11:02
+1. You bet me to it.
Dirk
2009-11-08 19:11:38
Then I think naming of SortedDictionary<> should be changed to something else :). Because most people thinks (so do I) that lookup in something sorted should work definitely faster. I just made huge performance improvement to my algo, where lookup is very important... If I've knew this 3 moths ago, I would hear less screams, because of speed ;)
Lukas Šalkauskas
2009-11-08 19:41:52
On the contrary, I would hope that any programmer would automatically think "O(log n)" when they hear "sorted".
erickson
2009-11-08 19:49:51
@erickson good point. From now I will think that way :)
Lukas Šalkauskas
2009-11-08 20:27:25