Python sortedcontainers Module

Python sortedcontainers Module

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

Python’s standard library is great until you need a sorted container 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.

Things shouldn’t be this way. Not in 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 at home without at least a gigabyte of memory. In Python an integer requires at least 12 bytes. SortedList will add about 4 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 for which every node must also store two pointers to children nodes.

Python SortedContainers takes all of the work out of Python sorted types – 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
  • 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 mostly a Python set with a SortedList index)
  • Developed on Python 2.7
  • Tested on Python 2.6, 2.7, 3.2, and 3.3

Quickstart

Installing SortedContainers is simple with pip:

> 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)

Thank You

This project was inspired and encouraged by the writings and open-source contributions of many people. A few in particular were:

  • Kenneth Reitz – Thanks for your samplemod project and for creating a beautiful API with requests. Your encouragement in various blog posts about contributing to open-source inspired me to try giving back to Python.
  • Armin Ronacher – Thanks for your many contributions to open-source. In particular thanks for Flask and the beautiful template for documentation.
  • Daniel Stutzbach – Thanks for blist which became my API reference for implementing the list, dict, and set types.

I also want to thank the rbtree, treap, bintrees, and skiplistcollections developers for performance comparisons.

Give Support

If you or your organization uses SortedContainers, consider financial support: Give to Sorted Containers

Documentation

Complete documentation including performance comparisons is available at http://www.grantjenks.com/docs/sortedcontainers/.

Contribute

Collaborators are welcome!

  1. Check for open issues or open a fresh issue to start a discussion around a bug. There is a Contributor Friendly tag for issues that should be used by people who are not very familiar with the codebase yet.
  2. Fork the repository on GitHub and start making your changes to a new branch.
  3. Write a test which shows that the bug was fixed.
  4. Send a pull request and bug the maintainer until it gets merged and published.

Useful Links