Hacker Newsnew | comments | show | ask | jobs | submit login

You're right to be skeptical about the value of skip lists in comparison to other O(log n) type data structures like balanced trees and the like. Skip lists trade ease of implementation for probabilistic bounds, and have some minor cache advantages over balanced binary trees owing to the data structure generally not changing shape all that much, and it's hard to say whether these differences would materialize in Python.

However if I had no O(log n) structures at all and needed to implement some, I'd have to be a maniac to want to do balanced binary trees, which have notoriously delicate balancing algorithms, over skip lists which are very sweet and simple.




Guidelines | FAQ | Support | API | Security | Lists | Bookmarklet | DMCA | Apply to YC | Contact

Search: