Open Collective
Open Collective
Loading

Python Sorted Containers

Sorted Containers is an Apache2 licensed sorted collections library, written in pure-Python, and fast as C-extensions.

Contribute


Become a financial contributor.

Financial Contributions

Recurring contribution
Backer

Become a backer for $5.00 per month and support us

Starts at
$5 USD / month

Latest activity by


Recurring contribution
Sponsor

Become a sponsor for $100.00 per month and support us

Starts at
$100 USD / month

Latest activity by


Be the first one to contribute!
Custom contribution
Donation
Make a custom one-time or recurring contribution.

Latest activity by


+ 2

Top financial contributors

Individuals

1
Grant Jenks

$100 USD since Jan 2019

2
Daniel Burfoot

$100 USD since Feb 2019

3
Jacob Brazeal

$50 USD since Feb 2019

4
Sam Marrable

$35 USD since Dec 2019

5
Ethan Estrada

$25 USD since Nov 2019

Organizations

1
Triplebyte

$310 USD since Jan 2019

Python Sorted Containers is all of us

Our contributors 6

Thank you for supporting Python Sorted Containers.

Grant Jenks

Admin

$100 USD

Triplebyte

backer

$310 USD

Jacob Brazeal

backer

$50 USD

Budget


Transparent and open finances.

Credit from Sam Marrable to Python Sorted Containers using a Gift Card from Triplebyte

+$35.00USD
Completed
Contribution #60128

Credit from Ethan Estrada to Python Sorted Containers using a Gift Card from Triplebyte

+$25.00USD
Completed
Contribution #57112
+$50.00USD
Completed
Contribution #41068
$
Today’s balance

$183.82 USD

Total raised

$268.50 USD

Total disbursed

$84.68 USD

Estimated annual budget

--.-- USD

About


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, sorted dict, or sorted 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!

>>> from sortedcontainers import SortedList
>>> sl = SortedList(['e', 'a', 'c', 'd', 'b'])
>>> sl
SortedList(['a', 'b', 'c', 'd', 'e'])
>>> sl *= 10_000_000
>>> sl.count('c')
10000000
>>> sl[-3:]
['e', 'e', 'e']
>>> from sortedcontainers import SortedDict
>>> sd = SortedDict({'c': 3, 'a': 1, 'b': 2})
>>> sd
SortedDict({'a': 1, 'b': 2, 'c': 3})
>>> sd.popitem(index=-1)
('c', 3)
>>> from sortedcontainers import SortedSet
>>> ss = SortedSet('abracadabra')
>>> ss
SortedSet(['a', 'b', 'c', 'd', 'r'])
>>> ss.bisect_left('c')
2

All of the operations shown above run in faster than linear time. The above demo also takes nearly a gigabyte of memory to run. When the sorted list is multiplied by ten million, it stores ten million references to each of "a" through "e". Each reference requires eight bytes in the sorted 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.

Sorted Containers 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.

Our team