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)