3

As we all know skip list is such a fascinating data structure with O(logn) insertion/search with ease of implementation over complex (AVL, Red-black) trees and also it is already been implemented in various applications and frameworks.

Is their any obvious reason why .NET is unaware of this data structure (java already implemented though)?

nawfal
  • 70,104
  • 56
  • 326
  • 368
Bishnu Rawal
  • 1,387
  • 16
  • 33
  • How is `ConcurrentDictionary` inconsistent? The example on MSDN regarding `GetOrAdd` leads to perfectly consistent behaviour within the dictionary. If you need higher level transactions, you will need to implement them yourself. – Jonas Bötel Nov 10 '13 at 10:07
  • 2
    AVL and red-black are also O(logN). Alternative algorithms like skip lists that promise a smaller Oh are quickly defeated by modern processors, cache is king and any algorithm that ignores them will only ever look good on paper. Just never write code that adds the same item to a collection with more than one thread and expect one of them to always "win". That never works, regardless of the collection type. – Hans Passant Nov 10 '13 at 11:28
  • @HansPassant: great advice. As skip list is randomized and probabilistic collection type, its average case lowers as nodes rises, this looks unnatural but fascinates me. Ya, those trees have also same asymptotic bounds, but complex in implementation. I don't understand how skip list algorithms ignores cache? – Bishnu Rawal Nov 10 '13 at 13:07
  • 1
    Not sure what answers do you expect. "why .net is unaware of this data structure"? Because they didn't implement it (yet?). What more can be said? – BartoszKP Jan 05 '14 at 14:24
  • 1
    @BartoszKP: Sorry that question is informative, but it hurts when you love some data structure so much but don't find any concrete implementation on monster frameworks like .NET. [Hash table](http://msdn.microsoft.com/en-us/library/system.collections.hashtable%28v=vs.110%29.aspx) along with other [dictionary collection types](http://msdn.microsoft.com/en-us/library/4yh14awz%28v=vs.110%29.aspx) are already there but not skip list. – Bishnu Rawal Jan 05 '14 at 15:57
  • That article dates from a bygone era, 68020 processors did not have the same concerns as modern ones do. Entire classes of elegant algorithms that were put out to pasture, Dekker's was my favorite. The problem with skip lists is demonstrated well in [this question](http://stackoverflow.com/questions/16561122/why-does-my-application-spend-24-of-its-life-doing-a-null-check). – Hans Passant Jun 10 '14 at 10:56
  • @HansPassant: Your answer is great on that link, now i get it, what actually caching things mean. Thanks – Bishnu Rawal Jun 11 '14 at 17:26

0 Answers0