A pure Python skiplist.
A pure Python skiplist implementation.
A skiplist provides a quickly searchable structure (like a balanced binary tree) that also updates fairly cheaply (no nasty rebalancing acts). In other words, it’s awesome.
See http://en.wikipedia.org/wiki/Skip_list for more information.
Written mostly an exercise for myself, it turns out skiplists are really useful. It also comes with a (mostly-underdocumented) linked-list implementation (+ a sorted variant), if that’s useful.
- Python 3.3+ (should work on Python 2.6+ as well, as well as PyPy 2.0+)
- nose>=1.30 for running unittests
Using it looks like:
>>> import skiplist >>> skip = skiplist.Skiplist() >>> len(skip) 0 >>> 6 in skip False >>> skip.insert(0) >>> skip.insert(7) >>> skip.insert(3) >>> skip.insert(6) >>> skip.insert(245) >>> len(skip) 5 >>> 6 in skip True >>> skip.remove(245) >>> len(skip) 4 >>> skip.find(3) <Skiplist: 3>
Performance is alright, though I’m sure there’s room for improvement. See the bench.py script for more information.
Run pip install nose (preferrably within a virtualenv) to install nose.
Then run nosetests -s -v tests.py to exercise the full suite.
A more performant implementation of remove (still O(N))
More performance testing
- Loading data seems slow
Download the file for your platform. If you're not sure which to choose, learn more about installing packages.
|Filename, Size & Hash SHA256 Hash Help||File Type||Python Version||Upload Date|
(6.1 kB) Copy SHA256 Hash SHA256
|Wheel||2.7||Dec 3, 2013|
(5.2 kB) Copy SHA256 Hash SHA256
|Source||None||Oct 17, 2013|