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 >>> 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.
- 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
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)
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.
If you or your organization uses SortedContainers, consider financial support: Give to Sorted Containers
Complete documentation including performance comparisons is available at http://www.grantjenks.com/docs/sortedcontainers/.
Collaborators are welcome!
- 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.
- Fork the repository on GitHub and start making your changes to a new branch.
- Write a test which shows that the bug was fixed.
- Send a pull request and bug the maintainer until it gets merged and published.