Skip Lists. Seem handy for increasing access times on ordered lists... Any Lispers care to comment?
what's your method for quickly searching an ordered list? Binary search falls apart since you don't have free random access.
Skip Lists Done Right
41–50 of 87 posts
Re: Skip Lists Done Right
#42Might anyone familiar with both data structures be able to briefly explain how this actually differs from a B-tree?
Re: Skip Lists Done Right
#43Skip 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.
WUSTL 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.
Yeah, I was just thinking about that 241 lecture. I do feel like we did the naive version though
Re: Skip Lists Done Right
#44Skip 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.
My University (UMD) does, but that might only be because Bill Pugh teaches/taught here.
Re: Skip Lists Done Right
#45Skip 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.
Georgia 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.
Re: Skip Lists Done Right
#46Skip 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.
I'm pretty sure my program at KU covered skip lists in our data structures class.
Re: Skip Lists Done Right
#47Earlier quoted context omitted.
Data structures in Redis have evolved a bit in the last 7 years. One of the main workhorses is indeed something called a "ziplist". The implementation (especially the format description at the top) is worth a read: https://github.com/antirez/redis/blob/90a6f7fc98df849a9890ab... For those who are familiar with pre-2.6 Redis code, there used to be something called zipmap, but it was deprecated in favor of ziplist.
I have not looked at Redis code in eons, but I think it's not exactly true - all the structures are there, it's just that redis will favor ziplist for the very small ones. A ziplist is a list of compact varying length integers (or strings) where only the bits that make a difference are stored (I contributed the 24-bit version to Redis[1]). The argument is that a sequential search over a small data structure always wi…
Yes, that is correct. The code checks the encoding at runtime ( https://github.com/antirez/redis/blob/8444b46d20ef9c8de3f7e2... ) and converts between the structures as needed (see calls to `zsetConvert`). The alternative (for large zsets) is called zskiplist, the manipulation code is directly in t_zset.c and the structure is defined at https://github.com/antirez/redis/blob/8444b46d20ef9c8de3f7e2...
Re: Skip Lists Done Right
#48Excellent article, I really love algorithm and datastructure. if anyone else is interested like me, I recommend this book https://www.amazon.com/Introduction-Algorithms-3rd-MIT-Press...
I'm not a big fan of that book. For all its weight its still surprisingly informal.
Re: Skip Lists Done Right
#49I was set to do some effects on After Effects anyone about this experience yourself more questions. Here are some things I can do (https://goo.gl/Ada79j)
Re: Skip Lists Done Right
#50I just came across skip lists as part of a sliding-window aggregator in Apache Samza's metrics system[0]. So cool! Being able to work with a range of values in somewhere between O(1)and O(log n) time, while still providing ordered key/value mappings, is great. Dug through java.util.concurrent looking for more structures, but this seems to be the most interesting of the bunch.
[0] https://github.com/apache/samza/blob/master/samza-api/src/ma...