Python Sorted Container Types: Sorted List, Sorted Dict, and Sorted Set

Last update: Jan 04, 2023

Overview

Python Sorted Containers

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

Testimonials

Alex Martelli, Fellow of the Python Software Foundation

"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, author of Writing Idiomatic Python and Python Trainer

"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, Python and Django Trainer

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.

Mark Summerfield, a short plea for Python Sorted Collections

Python's "batteries included" standard library seems to have a battery missing. And the argument that "we never had it before" has worn thin. It is time that Python offered a full range of collection classes out of the box, including sorted ones.

Sorted Containers is used in popular open source projects such as: Zipline, an algorithmic trading library from Quantopian; Angr, a binary analysis platform from UC Santa Barbara; Trio, an async I/O library; and Dask Distributed, a distributed computation library supported by Continuum Analytics.

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 older blist and bintrees modules)
Feature-rich (e.g. get the five largest keys in a sorted dict: d.keys()[-5:])
Pragmatic design (e.g. SortedSet is a Python set with a SortedList index)
Developed on Python 3.7
Tested on CPython 2.7, 3.2, 3.3, 3.4, 3.5, 3.6, 3.7 and PyPy, PyPy3

https://api.travis-ci.org/grantjenks/python-sortedcontainers.svg?branch=master

https://ci.appveyor.com/api/projects/status/github/grantjenks/python-sortedcontainers?branch=master&svg=true

Quickstart

Installing Sorted Containers is simple with pip:

$ pip install sortedcontainers

You can access documentation in the interpreter with Python's built-in help function. The help works on modules, classes and methods in Sorted Containers.

>>> import sortedcontainers
>>> help(sortedcontainers)
>>> from sortedcontainers import SortedDict
>>> help(SortedDict)
>>> help(SortedDict.popitem)

Documentation

Complete documentation for Sorted Containers is available at http://www.grantjenks.com/docs/sortedcontainers/

User Guide

The user guide provides an introduction to Sorted Containers and extensive performance comparisons and analysis.

Community Guide

The community guide provides information on the development of Sorted Containers along with support, implementation, and history details.

API Documentation

The API documentation provides information on specific functions, classes, and modules in the Sorted Containers package.

Talks

Resources

Sorted Containers License

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

http://www.apache.org/licenses/LICENSE-2.0

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.

Comments

SortedContainers 2.0 broke compatibility with no warning

Hello, You may not view this as a bug, but it was a big surprise for me! SortedDict() .keys() used to return sets that could do .intersect() operations. It must now be converted from SortedKeysView (or something?) to a set() and this uses tons of memory and time. The iloc method was also removed. I only got that far before I realized the build I was troubleshooting had a newer version than dev and was broken because of it. Please put a "breaking changes" section into the documentation when making these sorts of things! Or better yet, don't go fixing what isn't broken and also remove functionality :-D

opened by ghost 20
How to do floor and ceiling lookups?
With bintrees being discontinued, and projects using it being urged to migrate to sortedcontainers, I have a feature question. In bintrees, you can look up the "floor" and "ceiling" items given a key that is either too big or too small. For example:

import bintrees x = bintrees.BinaryTree() x[10] = 'ten' assert x.floor_item(15) == (10, 'ten') assert x.ceiling_item(5) == (10, 'ten')

As far as I can tell, this isn't possible in sortedcontainers. Am I missing anything? If not, is it a planned feature to add? Alternatively, do you have any pointers for a direction toward implementing it?
opened by zardus 11
Feature Request: SortedDict key function based on values

I would like to be able to have a SortedDict where the sorting is determined by the value being added, or some combination of the key and the value. Basically, the ability for me to provide a key function that takes two arguments.

opened by smmalis37 11
Document total ordering requirement
The following code gives an exception in version 1.5.7:

import sortedcontainers class Simple(object): def __init__(self): self.code = 0 self.time = 0 def __lt__(self, other): return self.time < other.time o1 = Simple() o1.time = 3 o1.code = 12 o2 = Simple() o2.time = 3 o2.code = 18 l = sortedcontainers.SortedList() l.add(o1) l.add(o2) print(l[1] in l) #This prints "False" l.index(l[1])

ValueError: <__main__.Simple object at 0x7f863f4c4a10> is not in list

The problem seems to be related with the definition of the __lt__ method, as in this case o1 ≮ o2, o2 ≮ o1, but o1 ≠ o2. From the docs, the index() function "Return the smallest k such that L[k] == x and i <= k < j", but that is not true in this case.
docs
opened by tomas-teijeiro 10
can SortedDict add support to quack like a Sequence when desired?

(I'm guessing you've thought about this already and decided against, but just wanted to make sure.)

The Python glossary defines sequence as:

An iterable which supports efficient element access using integer indices via the __getitem__() special method and defines a __len__() method that returns the length of the sequence. Some built-in sequence types are list, str, tuple, and bytes. Note that dict also supports __getitem__() and __len__(), but is considered a mapping rather than a sequence because the lookups use arbitrary immutable keys rather than integers.

The collections.abc.Sequence abstract base class defines a much richer interface that goes beyond just __getitem__() and __len__(), adding count(), index(),__contains__(), and __reversed__(). Types that implement this expanded interface can be registered explicitly using register().

SortedDicts have a well-defined ordering, and offer efficient element access using integer indices. So ideally a SortedDict would be able to be used anywhere a Sequence was required.

But because of the overloaded semantics of __getitem__, SortedDict of course has to choose to use it for the Mapping-style implementation rather than the Sequence-style, and thus probably gives up any right to claim that it implements Sequence. Seems like a shame!

(Can't help but wonder if some fancier version of register could allow SortedDict to specify iloc as its __getitem__ implementation when being treated as a Sequence, and wonder whether e.g. Haskell or Clojure would never have a problem like this.)

In any case, we're out of luck right? The Keys-, Values-, and ItemsViews that SortedDict offers are as much Sequence support as SortedDict can provide?

Curious to get your thoughts. And wonder if it's worth adding any takeaways from this to the SortedDict docs. e.g. "Because of limitations in Python, SortedDict cannot implement the Sequence interface even though it took all the right vitamins. Instead you must use a SortedDict's KeysView, ValuesView, or ItemsView anywhere you'd want to use a SortedDict as a Sequence."

opened by jab 10

TypeError when adding two incomparable items with same key to SortedListWithKey

On Python 3.4.1:

>>> l = SortedListWithKey(key=lambda x: 1)
>>> class A: pass
... 
>>> l.add(A())
>>> l.add(A())
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
  File "/home/muon/kirmvenv2/lib/python3.4/site-packages/sortedcontainers/sortedlistwithkey.py", line 21, in add
    self._list.add(pair)
  File "/home/muon/kirmvenv2/lib/python3.4/site-packages/sortedcontainers/sortedlist.py", line 51, in add
    pos = bisect_right(self._maxes, val)
TypeError: unorderable types: A() < A()

This is because in Python 3 comparing incomparable types dies horribly instead of returning True.

opened by Muon 10

Fix update() ordering to be more consistent with add() ordering

This pull request fixes #158 by prepending existing elements to new ones (to stick with the same ordering as the add() method).

I have run the included tox tests and benchmarks offline and have not seen any noticeable difference in performance after looking at the benchmark plots.

opened by bamartin125 9

Provide reduce for more robust pickling

It seems that SortedList doesn't implement support for pickling except by inheriting object.__reduce__. The pickle output therefore contains field that are implementation details of the class.

Consider the result of calling __reduce__() on SortedList([1, 2, 3]):

>>> sortedcontainers.SortedList((1, 3, 2)).__reduce__()
(<function _reconstructor at 0x7f566564c268>, (<class 'sortedcontainers.sortedlist.SortedList'>, <class 'object'>, None), {'_len': 3, '_lists': [[1, 2, 3]], '_maxes': [3], '_index': [], '_load': 1000, '_twice': 2000, '_half': 500, '_offset': 0})

Pickling and unpickling presently works with this implementation, but this approach has two issues:

it is not optimal wrt space, since it includes unnecessary data. Ideally it would only pickle the sequence of 1, 2, 3, and the fact that it's stored in a SortedList. The __reduce__ protocol is designed with such usage in mind.
it leaks private fields, which are clearly implementation details, into the peristent format. Even a slight change in the implementation would likely cause unpickling to fail.

An implementation that resolves both issues might look like this, in the case of SortedList:

    def __reduce__(self):
        return type(self), (), None, iter(self)

Here is a small comparison of the two:

class X(sortedcontainers.SortedList):
    def __reduce__(self):
        return type(self), (), None, iter(self)

class Y(sortedcontainers.SortedList):
  pass

>>> x, y = X([1, 2, 3]), Y([1, 2, 3])
>>> x.__reduce__()
(<class '__main__.X'>, (), None, <itertools.chain object at 0x7f5665d444a8>)
>>> pickle.dumps(x, protocol=pickle.HIGHEST_PROTOCOL)
b'\x80\x04\x95\x1d\x00\x00\x00\x00\x00\x00\x00\x8c\x08__main__\x94\x8c\x01X\x94\x93\x94)R\x94(K\x01K\x02K\x03e.'
>>> pickle.loads(_)
X([1, 2, 3], load=1000)
>>> pickle.dumps(y, protocol=pickle.HIGHEST_PROTOCOL)
b'\x80\x04\x95\x80\x00\x00\x00\x00\x00\x00\x00\x8c\x08__main__\x94\x8c\x01Y\x94\x93\x94)\x81\x94}\x94(\x8c\x04_len\x94K\x03\x8c\x06_lists\x94]\x94]\x94(K\x01K\x02K\x03ea\x8c\x06_maxes\x94]\x94K\x03a\x8c\x06_index\x94]\x94\x8c\x05_load\x94M\xe8\x03\x8c\x06_twice\x94M\xd0\x07\x8c\x05_half\x94M\xf4\x01\x8c\x07_offset\x94K\x00ub.'
>>> pickle.loads(_)
Y([1, 2, 3], load=1000)

opened by hniksic 9

Sorting order of SortedList?

SortedList objects don't compare the same way lists do, or in any way that I could make sense of.

>>> SortedList([1, 2]) < [3]
False
>>> SortedList([1, 2]) < [0]
False
>>> SortedList([1, 2]) < [0, 4]
False
>>> SortedList([1, 2]) > [0, 4]
False

opened by remram44 9

Move ValueSortedDict into SortedContainers (was: Support for SortedBidict)
Hi Grant,

I'm the author of bidict. I just came across SortedContainers and it looks excellent. Kudos on the great work! I'm delighted to have found another high-quality Python collections library, and look forward to studying it further.

In the meantime, thanks to finding this project, I've already made a tiny change to the development version of bidict that I'm excited about: now users can make a SortedBidict type (backed by your SortedDict) in just a few lines of code:

>>> import bidict, sortedcontainers >>> >>> class sortedbidict(bidict.bidict): ... _dict_class = sortedcontainers.SortedDict >>> >>> b = sortedbidict({'Tokyo': 'Japan', 'Cairo': 'Egypt', 'Lima': 'Peru'}) >>> >>> list(b.items()) # b stays sorted by its keys [('Cairo', 'Egypt'), ('Lima', 'Peru'), ('Tokyo', 'Japan')] >>> >>> list(b.inv.items()) # b.inv stays sorted by *its* keys (b's values!) [('Egypt', 'Cairo'), ('Japan', 'Tokyo'), ('Peru', 'Lima')] >>> >>> b.index('Lima') # passes through to SortedDict's implementation 1 >>> b.iloc[-1] 'Tokyo' >>> b.peekitem(index=-1) ('Tokyo', 'Japan') >>> b.inv.peekitem(index=-1) ('Peru', 'Lima') >>> b.popitem(last=False) ('Cairo', 'Egypt') >>> list(b.items()) [('Lima', 'Peru'), ('Tokyo', 'Japan')] >>> list(b.inv.items()) [('Japan', 'Tokyo'), ('Peru', 'Lima')]

Documented more here.

Always interested to hear more ideas for fruitful interop and in collaboration in general. In case of interest!

Thanks for reading and best wishes.

Josh

P.S. Hope you don't mind my using your tracker for this. Please of course feel free to close / migrate to anywhere else you prefer. bidict has a (mostly inactive) channel at https://gitter.im/jab/bidict in case you'd ever like to chat there.
opened by jab 8
Why does this code take 123 ms vs the excpected 12 ms?

#This is running in Pycharm and Conda

from sortedcontainers import SortedList, SortedSet, SortedDict import timeit import random

def test_speed(data,sorted_data): for val in data: #Accessing this is not an issue sorted_data.add(val)

data = [] numpts = 10 ** 5 for i in range(numpts): data.append(random.random()) print(f'Num of pts:{len(data)}')

sorted_data = SortedList() n_runs=10 result = timeit.timeit(stmt='test_speed(data,sorted_data)', globals=globals(), number=n_runs) print(f'Speed is {1000*result/n_runs:0.0f}ms')

opened by layssi 7
Feature Proposal: Introduce Higher Level APIs like ceil / floor
Motivation

Other programming languages support high-level APIs like

Get next smaller value (or item)

Get floor value (or item)

Get ceil value (or item)

Get next larger value (or item) In Tree data structure.

We can achieve this by using bisect method + index range check, but providing higher-level API would help users to avoid writing wrapper code every time.

API Definition

SortedList

def next_smaller(self, value: object) -> Optional[object]

def floor (self, value: object) -> Optional[object]

def ceil (self, value: object) -> Optional[object]

def next_greater(self, value: object) -> Optional[object]

SortedSet

def next_smaller(self, value: Hashable) -> Optional[object]

def floor (self, value: Hashable) -> Optional[object]

def ceil (self, value: Hashable) -> Optional[object]

def next_greater(self, value: Hashable) -> Optional[object]

SortedDict

def next_smaller_item(self, key: Hashable) -> tuple[Optional[Hashable], Optional[object]]

def floor_item (self, key: Hashable) -> tuple[Optional[Hashable], Optional[object]]

def ceil_item (self, key: Hashable) -> tuple[Optional[Hashable], Optional[object]]

def next_greater_item(self, key: Hashable) -> tuple[Optional[Hashable], Optional[object]]

Prototype Code (Implementation / Tests)

https://github.com/grantjenks/python-sortedcontainers/pull/206

P.S

If this idea sounds good to you, I'd love to discuss API design (including naming), testing strategy, etc.

Thank you so much for your attention and participation.
opened by Asayu123 2
Feature request: parameterize SortedList used in SortedDict through inheritance

Hi, thanks for your work :)

would it be possible to add a new function to the SortedDict (and therefore also SortedList) which sets a key a new value and returns the index position in one go? Eg.: index = sorteddict.setitem_returnindex(key,value)

Usecase: I want to add a new key,value to the SortedDict and I want to know at which total index this key was sorted in. Since performance is important, I assume that such a combined method would be much faster than sorting it in and then again search the key to get the index.

I assume that when sorting the new key into the SortedDict, we already search for the correct index to insert it. So we should be able to simply return this index and then there is no need to search for it twice. I already read the source code and tried to add it myself, but: 1) sortedcontainers is still frequently updated, I don't want to overwrite eg. the init of SortedDict to make it use a custom SortedList, because this might mess with future updates. 2) I did not fully understand the internal structure with lists and maxes yet :D And it seems bisect "insort" also does not return the index, which makes it more difficult =/ (I really don't understand why "insort" does not return the index, it would be so easy -.- )

opened by Serpens66 5
unpickling very slow

Hi,

I have some code where unpickling SortedLists and SortedSets takes a significant amount of the runtime of my program (I have a lot of them!)

The problem is, I think, that as __reduce__ just says that set and key should be passed to init, then the iterable values then get fed into self._update one at a time.

Would it be possible to speed things up, as the iterable is already known to be sorted? I wasn't sure of the best way to do this, one option would be to add a constructor method issorted, but then that might get used by other people (and maybe incorrectly), and you might not want that?

opened by ChrisJefferson 3
add GitHub URL for PyPi

Warehouse now uses the project_urls provided to display links in the sidebar on this screen, as well as including them in API responses to help automation tool find the source code for Requests.

opened by andriyor 3
add SortedArray

Support for a sorted container based off the standard library array.array class.

Enables compact storage of numerical values saving times fold in memory required.

Time performance is en par with the List based implementation below 1M size, and marginally better at 10M and 100M size, as tested on M1 Max 64GB RAM

opened by bsamedi 2