7 ms·
Skip lists are a hidden gem! I first learned about them from a GitHub developer at OSCon a few years ago, and at time they seemed like black magic. It's a sham
by reynoldsbd 10y ago
Skip lists are a hidden gem! I first learned about them from a GitHub developer at OSCon a few years ago, and at time they seemed like black magic.
It's a shame that universities (or at least mine) don't teach more interesting algorithms like this... it would make the algorithms/data structures coursework so much more interesting.
- nishs 10y agoUT Austin's multicore computing course had an optional project to benchmark concurrent skip lists or implement faster skip list algorithms. My group aimed to improve element access times by boosting the height of frequently accessed elements.
- ragnatest001 10y agoWUSTL does teach Skip List. We spent a good two weeks learning about it. Intro, analysis, lab, test about Skip List. It's very cool and hard to get right.
- pspeter3 10y agoYeah, I was just thinking about that 241 lecture. I do feel like we did the naive version though
- woodruffw 10y agoMy University (UMD) does, but that might only be because Bill Pugh teaches/taught here.
- superdaniel 10y agoGeorgia Tech definitely teaches it in the intro data structures and algorithms course. I don't remember if we had to implement it, but it definitely came up in lecture.
- BenTheElder 10y agoWe had to implement them when I took it with Dr. Waters at least (Summer 2015). CS 1332 is a pretty good intro course.
- blktiger 10y agoI'm pretty sure my program at KU covered skip lists in our data structures class.
- jychang 10y agoBerkeley did cover skip lists, along with a lot of other algorithms, both practical and esoteric.
- Glyptodon 10y agoIt was part of my normal university computer science data structures course. Was actually one of the structures we had to implement. Also, for all the "hard to get right" comments I remember them being much easier to write than RB Trees or B Trees.
- danaliv 10y agoIllinois covers them.