Skip to main content

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


Download files

Download the file for your platform. If you're not sure which to choose, learn more about installing packages.

Source Distribution

pyskip-0.9.0.tar.gz (5.2 kB view details)

Uploaded Source

Built Distribution

pyskip-0.9.0-py2.py3-none-any.whl (6.1 kB view details)

Uploaded Python 2 Python 3

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

Hashes for pyskip-0.9.0.tar.gz
Algorithm Hash digest
SHA256 aa107ee1cce4dae596533b2fc616bffc7c34aa27246347203f07e7e27cff4f82
MD5 870d89c32dfcb096be41b6e6c1581f40
BLAKE2b-256 d93c87b6f0ca9740a3409baa5e9cedb5b1f9cdacbff036fcf5e6c7d84dd65638

See more details on using hashes here.

Provenance

File details

Details for the file pyskip-0.9.0-py2.py3-none-any.whl.

File metadata

File hashes

Hashes for pyskip-0.9.0-py2.py3-none-any.whl
Algorithm Hash digest
SHA256 21f678cbefa8507cb45f28e27c7bf108551bd27856a63a013e31c3a503e30e9e
MD5 f167078a42c700b7d729bd93919d5877
BLAKE2b-256 219a2350e7d0ab8418c20fd1bb9ab61f03f08ed15ffa5884535659fef4f4bb4d

See more details on using hashes here.

Provenance

Supported by

AWS AWS Cloud computing and Security Sponsor Datadog Datadog Monitoring Fastly Fastly CDN Google Google Download Analytics Microsoft Microsoft PSF Sponsor Pingdom Pingdom Monitoring Sentry Sentry Error logging StatusPage StatusPage Status page