4 ms·

Skip lists are probably the easiest way of getting O(log(n)) lookups on ordered lists. Recently I got rid of huge bottleneck on an oldish piece of software by

by airesQ 10y ago

Skip lists are probably the easiest way of getting O(log(n)) lookups on ordered lists. Recently I got rid of huge bottleneck on an oldish piece of software by moving from a vanilla linked list to a skip list. And I did do many things suggested in the article (e.g. having a vector of fixed length for the pointers, and thus a fixed tallness). Funnily enough, for my case, I managed to do without a RNG just fine. I just have an element that is of tallness 'k' every 2^(k*3) insertions (e.g. every 8th insertion is 1 level tall; every 64th insertion is 2 levels tall; and so on). For my particular pattern of insertions, this proved to be more than enough, and and simplified things a little bit.

OskarS 10y ago
> Skip lists are probably the easiest way of getting O(log(n)) lookups on ordered lists. I wouldn't say that. The algorithms for AVL/red-black/splay trees are not especially complex, and they contain much less subtlety than skip lists. If you just look them up on wikipedia and see the list of operations, it's not particularly hard to implement them. Skip lists, on the other hand, are very easy to get wrong (this is the premise of the linked article, after all). Using a skip list is frequently the better choice for performance and memory reasons (especially if you're iterating through the list), but they are not necessarily simpler data structures.
- airesQ 10y ago
  I did a brief survey before deciding to go with skip lists, and found them to be easier to grasp and reason about. (e.g. there is no need to balance trees; a skip list is very similar to a linked list, and linked lists are very simple). I remember somebody saying that "in a sane world skip lists would always have been discovered before red-black trees". This historical accident (skip lists were only discovered 1989; while rb-trees date back to the 1970s) is probably the reason why skip list use is not more widespread, and seen as somewhat exotic at times. (AVL and Splay-trees also predate skip lists.)
  - kazinator 10y ago
    Skip lists are just B+ trees in disguise. Look at the basic diagram here. https://en.wikipedia.org/wiki/B%2B_tree https://en.wikipedia.org/wiki/B%2B_tree See how there is an "express lane" containing just (3 5), and the lower layer contains the entire (1 2 3 4 5 6 7) list? The main difference is that it's a combination of arrays and links rather than parallel lists.
- aidenn0 10y ago
  Binary search tree rotations are hard to implement correctly, but relatively easy to test that you have them right. There are a lot of subtleties in any stochastic algorithm (like a skip list) that are much harder to correctly test. While we're discussing "easy to implement" algorithms, I find Tries (aka radix trees) to be by far the easiest to implement for both ordered and unordered sets/maps. Naive implementations are very space inefficient though.
- kazinator 10y ago
  > The algorithms for AVL/red-black/splay trees are not especially complex and can be coded once, then used in millions of programs. That whole point is largely moot. A red-black tree gives you certain guarantees without any probabilistic arguments. Wikipedia: A skip list does not provide the same absolute worst-case performance guarantees as more traditional balanced tree data structures, because it is always possible (though with very low probability) that the coin-flips used to build the skip list will produce a badly balanced structure. A skip list algorithm which guards against the worst case will necessarily have to do some rebalancing that requires nodes to move among levels according to some heuristic. Skip lists are not storage efficient unless the nodes are variably sized. If each node includes enough pointers to participate in any level, then you waste space. Variable size means we cannot draw nodes from a single, compact pool array of nodes for a skip list. Variable size also creates difficulties if we want to use this as an "intrusive container". (A container which works by inserting the necessary node links and other fields into the client's data structure, so that the client data structures directly link into the graph as nodes, rather than being separately allocated and referenced from it.) I'm looking at a C implementation pointed at by DADS. http://epaperpress.com/sortsearch/txt/skl.txt http://epaperpress.com/sortsearch/txt/skl.txt This uses the C struct hack for variable node sizing, which makes it rely on malloc for the nodes. A client cannot pass in a pre-allocated node. A mistake in this type of code can lead to a buffer overflow: accessing the n-th level of a node which only has k < n levels worth' of pointers. If logic were added which moves a node from one skip level to another, that would require the entire node to be realloc'ed, if its number of links needs to increase. Realloc-ing can change its address; all existing pointers to the node must be rewritten.
- kazinator 10y ago
  Another consideration regarding memory: a binary tree with no parent pointers has two pointers per node. (Traversal then needs temp space due to to recursion or iteration with explicit stack.) However, a binary tree can be traversed in O(n) in both directions. A skip list with a singly-linked level zero cannot be traversed in reverse. If we make it doubly linked to meet the requirement for reverse traversal then ... it has two pointers per node and then some. There goes your storage advantage.
  - sobani 10y ago
    Actually, you can. As per the article, you can view the skiplist as a tree when turned 1/8th. So you can start at the head, put it on the stack, move to the next node referenced at the hightest level, put it on the stack, etc. just like you can start from the top of the tree, put it on the stack, move right, put it on the stack, etc. The advantage of the skiplist over the tree is that you can traverse forward in O(1) space. But both are equally bad in reverse

by airesQ 10y ago

OskarS 10y ago

> Skip lists are probably the easiest way of getting O(log(n)) lookups on ordered lists. I wouldn't say that. The algorithms for AVL/red-black/splay trees are not especially complex, and they contain much less subtlety than skip lists. If you just look them up on wikipedia and see the list of operations, it's not particularly hard to implement them. Skip lists, on the other hand, are very easy to get wrong (this is the premise of the linked article, after all). Using a skip list is frequently the better choice for performance and memory reasons (especially if you're iterating through the list), but they are not necessarily simpler data structures.

airesQ 10y ago
I did a brief survey before deciding to go with skip lists, and found them to be easier to grasp and reason about. (e.g. there is no need to balance trees; a skip list is very similar to a linked list, and linked lists are very simple). I remember somebody saying that "in a sane world skip lists would always have been discovered before red-black trees". This historical accident (skip lists were only discovered 1989; while rb-trees date back to the 1970s) is probably the reason why skip list use is not more widespread, and seen as somewhat exotic at times. (AVL and Splay-trees also predate skip lists.)
- kazinator 10y ago
  Skip lists are just B+ trees in disguise. Look at the basic diagram here. https://en.wikipedia.org/wiki/B%2B_tree https://en.wikipedia.org/wiki/B%2B_tree See how there is an "express lane" containing just (3 5), and the lower layer contains the entire (1 2 3 4 5 6 7) list? The main difference is that it's a combination of arrays and links rather than parallel lists.
aidenn0 10y ago
Binary search tree rotations are hard to implement correctly, but relatively easy to test that you have them right. There are a lot of subtleties in any stochastic algorithm (like a skip list) that are much harder to correctly test. While we're discussing "easy to implement" algorithms, I find Tries (aka radix trees) to be by far the easiest to implement for both ordered and unordered sets/maps. Naive implementations are very space inefficient though.
kazinator 10y ago
> The algorithms for AVL/red-black/splay trees are not especially complex and can be coded once, then used in millions of programs. That whole point is largely moot. A red-black tree gives you certain guarantees without any probabilistic arguments. Wikipedia: A skip list does not provide the same absolute worst-case performance guarantees as more traditional balanced tree data structures, because it is always possible (though with very low probability) that the coin-flips used to build the skip list will produce a badly balanced structure. A skip list algorithm which guards against the worst case will necessarily have to do some rebalancing that requires nodes to move among levels according to some heuristic. Skip lists are not storage efficient unless the nodes are variably sized. If each node includes enough pointers to participate in any level, then you waste space. Variable size means we cannot draw nodes from a single, compact pool array of nodes for a skip list. Variable size also creates difficulties if we want to use this as an "intrusive container". (A container which works by inserting the necessary node links and other fields into the client's data structure, so that the client data structures directly link into the graph as nodes, rather than being separately allocated and referenced from it.) I'm looking at a C implementation pointed at by DADS. http://epaperpress.com/sortsearch/txt/skl.txt http://epaperpress.com/sortsearch/txt/skl.txt This uses the C struct hack for variable node sizing, which makes it rely on malloc for the nodes. A client cannot pass in a pre-allocated node. A mistake in this type of code can lead to a buffer overflow: accessing the n-th level of a node which only has k < n levels worth' of pointers. If logic were added which moves a node from one skip level to another, that would require the entire node to be realloc'ed, if its number of links needs to increase. Realloc-ing can change its address; all existing pointers to the node must be rewritten.
kazinator 10y ago
Another consideration regarding memory: a binary tree with no parent pointers has two pointers per node. (Traversal then needs temp space due to to recursion or iteration with explicit stack.) However, a binary tree can be traversed in O(n) in both directions. A skip list with a singly-linked level zero cannot be traversed in reverse. If we make it doubly linked to meet the requirement for reverse traversal then ... it has two pointers per node and then some. There goes your storage advantage.
- sobani 10y ago
  Actually, you can. As per the article, you can view the skiplist as a tree when turned 1/8th. So you can start at the head, put it on the stack, move to the next node referenced at the hightest level, put it on the stack, etc. just like you can start from the top of the tree, put it on the stack, move right, put it on the stack, etc. The advantage of the skiplist over the tree is that you can traverse forward in O(1) space. But both are equally bad in reverse