A pure Python skiplist.
Project description
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
Project details
Release history Release notifications | RSS feed
Download files
Download the file for your platform. If you're not sure which to choose, learn more about installing packages.
Source Distribution
Built Distribution
Hashes for pyskip-0.9.0-py2.py3-none-any.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 21f678cbefa8507cb45f28e27c7bf108551bd27856a63a013e31c3a503e30e9e |
|
MD5 | f167078a42c700b7d729bd93919d5877 |
|
BLAKE2b-256 | 219a2350e7d0ab8418c20fd1bb9ab61f03f08ed15ffa5884535659fef4f4bb4d |