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
|Filename, size||File type||Python version||Upload date||Hashes|
|Filename, size pyskip-0.9.0-py2.py3-none-any.whl (6.1 kB)||File type Wheel||Python version 2.7||Upload date||Hashes View hashes|
|Filename, size pyskip-0.9.0.tar.gz (5.2 kB)||File type Source||Python version None||Upload date||Hashes View hashes|
Hashes for pyskip-0.9.0-py2.py3-none-any.whl