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 -- https://mail.python.org/mailman/listinfo/python-announce-list Support the Python Software Foundation: http://www.python.org/psf/donations/
