2 ms·
Out of curiousity, what made you pick skip-lists over a trie structure, such as crit-bit trees?
by aidenn0 14y ago
Out of curiousity, what made you pick skip-lists over a trie structure, such as crit-bit trees?
- _wmd 14y agoPrimarily because I knew from previous research that they were easy to implement. Secondarily because unlike most trees, they're amenable to concurrent update (although this is mostly irrelevant to a Python application) and I wanted to get some foundational experience. Locking a skip list is very straightforward, and slightly less intuitive lockless versions also exist.
- mzl 14y agoI'm wondering if "slightly less intuitive" is a deliberate understatement or not :) I recently read through the concurrent skip list map implementation in Java that is lockless. That code is definitely quite tricky, and the comments refer to three PhD thesis's one should read to understand how it works.