pyskip 0.9.0
Last updated:
0 purchases
Description:
pyskip 0.9.0
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.
Requirements
Python 3.3+ (should work on Python 2.6+ as well, as well as PyPy 2.0+)
nose>=1.30 for running unittests
Usage
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
Performance is alright, though I’m sure there’s room for improvement. See the
bench.py script for more information.
Running Tests
Run pip install nose (preferrably within a virtualenv) to install nose.
Then run nosetests -s -v tests.py to exercise the full suite.
TODO
A more performant implementation of remove (still O(N))
More performance testing
Loading data seems slow
Meta
author:
Daniel Lindsley
license:
BSD
version:
0.9.0
License:
For personal and professional use. You cannot resell or redistribute these repositories in their original state.
Customer Reviews
There are no reviews.
