skip to navigation
skip to content

pyskip 0.9.0

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.

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
 
File Type Py Version Uploaded on Size
pyskip-0.9.0-py2.py3-none-any.whl (md5) Python Wheel 2.7 2013-12-03 5KB
pyskip-0.9.0.tar.gz (md5) Source 2013-10-17 5KB