pyskiplist 1.0.0

Example

The following provides a few examples on how to use the SkipList API:

>>> from pyskiplist import SkipList
>>> sl = SkipList()
>>> sl.insert('foo', 'bar')
>>> sl.insert('baz', 'qux')
>>> sl
SkipList((('baz', 'qux'), ('foo', 'bar')))
>>> sl.search('foo')
'bar'
>>> sl[0]
('baz', 'qux')
>>> sl.remove('foo')  # remove by key
>>> del sl[0]  # remove by position

Asymptotic Complexity

Below are the Big-O complexities of the various operations implemented by pyskiplist:

Performance

Below are the results of some performance tests. These are for Python 3.4.2 on my Linux laptop:

Memory usage

PySkipList tries to be efficient with regards to memory usage. The numbers below are for Python 3.4.2 on my Linux laptop. This specific test stores pairs of integer keys and an integer values in a skiplist. The total size of the two integers on this Python version is 56 bytes.

Implementation notes

Reference papers on skiplists:

• ftp://ftp.cs.umd.edu/pub/skipLists/skiplists.pdf (original paper)

• http://drum.lib.umd.edu/bitstream/1903/544/2/CS-TR-2286.1.pdf (cookbook)

This implementation uses a novel (as far as I know) technique where it stores just a single link width per node, and only in nodes with level > 0. The link corresponds to the number of nodes skipped by the highest incoming link. Other implementations that I’ve seen all store a width for every link. This approach saves a lot of memory. The overhead should just be 1/e (0.37) integers per node. It makes an indexable skiplist almost as memory efficient as its non-indexable cousin.

Duplicate keys are allowed in this implementation, and insertion order is maintained.

Skiplist nodes are implemented as plain lists instead of objects. This saves memory. Kudos to http://pythonsweetness.tumblr.com/post/45227295342 for the idea.

The built-in Mersenne Twister is used as the random source. This is preferable over SystemRandom since it doesn’t require a system call and there is no need for cryptographically secure numbers.