5 ms·
One of our projects in the algorithms class back at uni was to implement a skiplist and assess its performance. While skiplists are indeed simple to implement
by hassy 18y ago
One of our projects in the algorithms class back at uni was to implement a skiplist and assess its performance.
While skiplists are indeed simple to implement and do have log(n) average time for most operations, they're an example of theory and practice being the same in theory but not in practice.
The real-world performance of skiplists is worse than that of B-trees, especially when you have costly comparisons. They also don't maintain as much locality and will thrash the cache more.
- aston 18y agoSkiplists are for most CS students their first and maybe only introduction to a data structure where the theoretical math comes out beautifully (impossibly?) small, and gets beaten by some variation of the binary tree if you actually try it in real life. There are a ton more, many of which I learned about from that same lecturer. Fun to talk about and toy with, but you'll never need Y-fast Tries in your day-to-day.