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
File details
Details for the file pyskip-0.9.0.tar.gz
.
File metadata
- Download URL: pyskip-0.9.0.tar.gz
- Upload date:
- Size: 5.2 kB
- Tags: Source
- Uploaded using Trusted Publishing? No
File hashes
Algorithm | Hash digest | |
---|---|---|
SHA256 | aa107ee1cce4dae596533b2fc616bffc7c34aa27246347203f07e7e27cff4f82 |
|
MD5 | 870d89c32dfcb096be41b6e6c1581f40 |
|
BLAKE2b-256 | d93c87b6f0ca9740a3409baa5e9cedb5b1f9cdacbff036fcf5e6c7d84dd65638 |
Provenance
File details
Details for the file pyskip-0.9.0-py2.py3-none-any.whl
.
File metadata
- Download URL: pyskip-0.9.0-py2.py3-none-any.whl
- Upload date:
- Size: 6.1 kB
- Tags: Python 2, Python 3
- Uploaded using Trusted Publishing? No
File hashes
Algorithm | Hash digest | |
---|---|---|
SHA256 | 21f678cbefa8507cb45f28e27c7bf108551bd27856a63a013e31c3a503e30e9e |
|
MD5 | f167078a42c700b7d729bd93919d5877 |
|
BLAKE2b-256 | 219a2350e7d0ab8418c20fd1bb9ab61f03f08ed15ffa5884535659fef4f4bb4d |