3 ms·
Faster List Intersection Using Skip Pointers
- pygy_ 17y agoThe indexable skip list (http://en.wikipedia.org/wiki/Skip_list http://en.wikipedia.org/wiki/Skip_list) is another interesting structure for this kind of problem. It's an expansion of the concept described, with a probablistic twist. It has O(log(n)) insertion, deletion and random access time, and linear traversal time, for a log(n) space overhead over a standard singly linked list. The main drawback is that, in order to get that kind of performance, you have to know roughly the expected size of your structure in advance (although it should be fairly easy to create one whose "added machinery" grows with the list). Example implmentations: Python : http://code.activestate.com/recipes/576930/ http://code.activestate.com/recipes/576930/ Lua : http://love2d.org/wiki/Skip_list http://love2d.org/wiki/Skip_list (a port of the former by yours truly, with some added functionality). Both are released under the MIT License.
- sadiq 17y agoJava also has one as part of the 6 concurrency additions: http://java.sun.com/javase/6/docs/api/java/util/concurrent/ConcurrentSkipListMap.html http://java.sun.com/javase/6/docs/api/java/util/concurrent/C... There's a ConcurrentSkipListSet too.
- jacquesm 17y agoAnother HN'er is busy with something that comes close to this but has a bunch of twists.