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 >>> 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.
- 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
SortedContainers_ is simple with
$ pip install sortedcontainers
You can access documentation in the interpreter with Python's built-in help
>>> from sortedcontainers import SortedList, SortedSet, SortedDict >>> help(SortedList)