SortedContainers

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

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.

Testimonials

Alex Martelli, Wikipedia

Good stuff! ... I like the simple, effective implementation idea of splitting the sorted containers into smaller “fragments” to avoid the O(N) insertion costs.

Jeff Knupp, Review of SortedContainers

That last part, “fast as C-extensions,” was difficult to believe. I would need some sort of performance comparison to be convinced this is true. The author includes this in the docs. It is.

Kevin Samuel, Formations Python

I’m quite amazed, not just by the code quality (it’s incredibly readable and has more comment than code, wow), but the actual amount of work you put at stuff that is not code: documentation, benchmarking, implementation explanations. Even the git log is clean and the unit tests run out of the box on Python 2 and 3.

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 CPython 2.6, 2.7, 3.2, 3.3, 3.4 and PyPy 2.2

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)

User Guide

For those wanting more details, this part of the documentation describes introduction, implementation, performance, and development.

API Documentation

If you are looking for information on a specific function, class or method, this part of the documentation is for you.

Indices and Utilities

Apache2 License

A large number of open source projects you find today are GPL Licensed. A project that is released as GPL cannot be used in any commercial product without the product itself also being offered as open source.

The MIT, BSD, ISC, and Apache2 licenses are great alternatives to the GPL that allow your open-source software to be used freely in proprietary, closed-source software.

SortedContainers is released under terms of Apache2 License.

SortedContainers License

Copyright 2014 Grant Jenks

Licensed under the Apache License, Version 2.0 (the “License”); you may not use this file except in compliance with the License. You may obtain a copy of the License at

Unless required by applicable law or agreed to in writing, software distributed under the License is distributed on an “AS IS” BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the License for the specific language governing permissions and limitations under the License.

SortedContainers provides sorted container types, written in pure-Python and fast as C-extensions.

Give Support

If you or your organization uses SortedContainers, consider financial support:

Give to Sorted Containers

Useful Links

This Page