Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.python.announce > #1765 > unrolled thread

[ANN] pyskiplist-1.0.0

Back to article view | Back to comp.lang.python.announce

Contents

  [ANN] pyskiplist-1.0.0 Geert Jansen <geertj@gmail.com> - 2015-07-04 19:05 -0400

#1765 — [ANN] pyskiplist-1.0.0

PySkipList is a fast, pure Python implementation of an indexable skiplist. It
implements a SkipList data structure that provides an always sorted,
list-like data structure for (key, value) pairs. It efficiently supports the
following operations:

* Insert a pair in the list, maintaining sorted order.
* Find the value of a given key.
* Remove a given pair based on a key.
* Iterate over all pairs in sorted order.
* Find the position of a given key.
* Access a pair at a certain position.
* Delete a pair at a certain position.

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.

Performance wise, it does around 77K searches per second on 100K nodes,
and has an overhead at this node count of about 106 bytes per node.

Available on PyPI as "pyskiplist" and Github at:

https://github.com/geertj/pyskiplist

Regards,
Geert

[toc] | [standalone]

Back to top | Article view | comp.lang.python.announce

csiph-web