r/programming • u/Comfortable-Fan-580 • 1d ago
Skip List Data structure
https://pradyumnachippigiri.substack.com/p/skip-lists-data-structure?r=5ev9w0&utm_medium=ios38
u/monocasa 1d ago
Skip lists don't have to be probabilistic fwiw.
https://www.ic.unicamp.br/~celio/peer2peer/skip-net-graph/deterministic-skip-lists-munro.pdf
15
u/wa11ar00 1d ago
Oh.. [skip list] data structure is not the same as skip [list data structure]. Interesting.
7
u/generalmatching 1d ago
In my opinion, skip lists are getting interesting with lock-free implementation, otherwise, a balanced trees have better performance with less memory overhead.
2
u/funny_falcon 1d ago
B+Tree has great concurrent algorithms and implementations as well.
But SkipLists are simpler. Way more simpler. And is made of simple clear concepts.
Operations of any kind of binary search tree is not as trivial as for skip list.
Surprisingly, BTree could be simpler, than BST. But Skip Lists are simpler
23
u/ReDucTor 1d ago
When you make statements about different data structures like "quickly", "slow", "fast", etc it's good to include actual benchmarks, because some of the claims in this article are not as straight forward as what it claims.
Arrays let us randomly access any element quickly, but insertion and deletion is slow because elements need to shift to make room or close the gap.
That's only if your inserting into the middle of the array and depending on the element type and how many there are shifting them is going to be relatively quick, and in many cases ending up quicker then dealing with a linked list or skip list.
Linked lists make inserting and deleting fast once we have reached the right spot
I take it your ignoring the memory allocation that is required for creating nodes? Which an array which has a reserved capacity does not need to do with every insertion.
we flip a fair coin (p = 1/2) to decide if the node should be promoted one level up, or not
This seems like a bad algorithm to me, the fairness of randomness comes with large numbers if you only have a small number of elements then this coin flip could just end up giving you a bad layout, additionally it makes for an inconsistent data structure where it's performance and memory usage will vary based on some random coin flip.
search in less than O(n) time
search time down to O(log N)
Big-O notation is not a great metric for measuring actual time, it only reprsents how that algorithm or data structure scales as the data set increases, it is rarely a good idea to compare two data structures or algorithms based solely on the Big-O notation, you should be using actual benchmarks.
Big-O notation does not indicate how well the hardware actually deals with those steps, some algorithms might have low latency steps but carry many dependencies so have low throughput, while others might have high latency steps but limited dependencies so have a higher throughput, and some might be like a linked list and have high latency and heavy dependencies so is slow all together.
The intersection between two different algorithms or data structures with O(log n) and O(n) might occur when n is 10, it might occur when n is 10,000 only benchmarking will truely tell you when this is, and you also need to be careful that your benchmarks are realistic as cold data and hot data can give you significantly different results.
12
u/infinitytacos989 1d ago
this is an insanely nitpicky response to an article that’s clearly supposed to be an introduction to a new data structure for people who haven’t heard of it, not an in depth performance review. most of the claims you take issue with are just trying to motivate the data structure for beginners.
2
1d ago
[deleted]
1
u/infinitytacos989 1d ago
it is basic stuff, which is why i’m confused that they felt the need to write an essay dunking on an article that has nothing to do with it.
4
1
u/ReDucTor 1d ago
It doesn't matter who the target audience is, when you claim one thing is faster then another you should include benchmarks.
The comment is the furthest thing from an in-depth performance review, its a critique of the post content and claims.
0
u/infinitytacos989 1d ago
“it doesn’t matter who the target audience is” please never make or critique educational content if you can’t understand that people at different levels of expertise require different educational content. this is like “critiquing” an elementary school math curriculum for saying you can’t take the square root of -1.
3
u/ReDucTor 1d ago
I will critique incorrect information regardless, someone claiming that a linked list is fast and an array is slow is setting up students to fail in the real world.
I have no issues with teaching people data structures and not covering the complexities of the CPU, my issue is teaching people bad content, the issue is claiming that an array is slow and a linked list or skip list is fast.
I would call out an elementary school math curriculum if they claimed that its faster to calculate 25*10 by adding 25 ten times, then doing an actual multiplication, when they already know multiplication.
0
u/Sopel97 14h ago edited 14h ago
this is like “critiquing” an elementary school math curriculum for saying you can’t take the square root of -1
which would be a valid critique. The correct way to phrase that is to say that a square root of -1 is not defined over real numbers
simplifying information to the point of incorrectness is harmful, it closes people's knowledge horizons and requires additional mental capacity to unlearn. In extreme cases it can cause trouble understanding new related concepts because they may clash with the ideas left by such prior incorrect information.
2
3
u/noahrichards 1d ago
The example of finding 70 requires touching/comparing approximately the same number of nodes as walking the original list, and the storage overhead of that list is like 2.5x the linked list, so it makes it look like this is a terrible data structure :) I suspect it’s because the example has more nodes at each level (above the lowest) on average than it should.
1
u/Electronic-Equal-616 15h ago
tbh i only found out about skip lists when our prof brought them up as an alternative to red-black trees. implementing rb trees in c++ gave me actual nightmares 😭 skip lists are definately so much more intuitive to code, even if the randomized part felt kinda like cheating at first lol.
1
u/barmic1212 1d ago
I don't understand why don't use a tree for same usage ? To keep the iteration in O(n) ?
8
u/helen_3410 1d ago
You can—balanced trees and skip lists solve the same ordered-set problem. Skip lists get expected O(log n) search and updates with simple pointer changes; balanced trees offer worst-case O(log n) guarantees. Both support O(n) ordered iteration.
1
u/AntimatterTNT 1d ago
is the random aspect really necessary? like you could argue it's to average out performance edge cases but really aren't you just making it so that sometimes you'd have much worse performance? (like a 0.1% deviation every 1000 runs)
1
1d ago
[removed] — view removed comment
1
u/programming-ModTeam 15h ago
No content written mostly by an LLM. If you don't want to write it, we don't want to read it.
0
1d ago
[removed] — view removed comment
1
u/programming-ModTeam 15h ago
No content written mostly by an LLM. If you don't want to write it, we don't want to read it.
0
-1
53
u/Aaron1924 1d ago
This article compares the skip list with a linked list, which is not very interesting, because those two data structures are designed for different usecases. The reason you can skip elements in the list is because you gain information about those elements from the layers above, e.g. because the list is sorted. For unordered data, skip lists fail completely, whereas linked lists do not care.
It would be much more interesting to discuss how a skip list compares to a binary search tree, for example.