/ Patterns

Fast and pure-Python implementation of SortedList

Fast and pure-Python implementation of SortedList

Python SortedContainers

SortedContainers is an Apache2 licensed sorted collections library, written in pure-Python, and fast as C-extensions.

Python's standard library is great until you need a sorted collections type. Many will attest that you can get really far without one, but the moment you really need a sorted list, dict, or set, you're faced with a dozen different implementations, most using C-extensions without great documentation and benchmarking.

In Python, we can do better. And we can do it in pure-Python!


    >>> sl = sortedcontainers.SortedList(xrange(10000000))
    >>> 1234567 in sl
    True
    >>> sl[7654321]
    7654321
    >>> sl.add(1234567)
    >>> sl.count(1234567)
    2
    >>> sl *= 3
    >>> len(sl)
    30000003

Note: don't try this without at least a half gigabyte of memory. In Python
an integer requires about 24 bytes. SortedList will add about 8 bytes per
object stored in the container. That's pretty hard to beat as it's the cost of
a pointer to each object. It's also 66% less overhead than a typical binary
tree implementation (e.g. red-black tree, avl tree, aa tree, splay tree, treap,
etc.) for which every node must also store two pointers to children nodes.

SortedContainers_ takes all of the work out of Python sorted collections -
making your deployment and use of Python easy. There's no need to install a C
compiler or pre-build and distribute custom extensions. Performance is a
feature and testing has 100% coverage with unit tests and hours of stress.

Features

  • Pure-Python
  • Fully documented
  • Benchmark comparison (alternatives, runtimes, load-factors)
  • 100% test coverage
  • Hours of stress testing
  • Performance matters (often faster than C implementations)
  • Compatible API (nearly identical to popular blist and rbtree modules)
  • Feature-rich (e.g. get the five largest keys in a sorted dict: d.iloc[-5:])
  • Pragmatic design (e.g. SortedSet is a Python set with a SortedList index)
  • Developed on Python 2.7
  • Tested on CPython 2.7, 3.2, 3.3, 3.4, 3.5, 3.6 and PyPy, PyPy3

Quickstart

Installing SortedContainers_ is simple with
pip <http://www.pip-installer.org/>_::

$ pip install sortedcontainers

You can access documentation in the interpreter with Python's built-in help
function:


    >>> from sortedcontainers import SortedList, SortedSet, SortedDict
    >>> help(SortedList)

GitHub