Hi,
I find myself reaching for sortedcontainers pretty often, and it made me wonder why it isn’t in the stdlib. Looking at pypistats, it gets ~9.8M downloads/day (as of July 1), so I’m clearly not the only one using it 
I think the backend ds for the implementation of SortedDict or Set are well known (B-trees, red-black trees, …).
Do you think Python could adopt SortedDict/SortedSet into collections at this point? Anyone know if this has been proposed before?
Thanks
I believe some wouldn 't do bad - and up to Python 3.17, people could have fun reaching good enough designs, once several trade-offs are taken into account, to land into the stdlib.
I believe the second step (the first is your very post), is getting more motivation into it: your post is nice, but can we get the idea even more compelling?
Then, once we have a motivated mass of people willing to do it, we can bikeshed on which structures, and draft a pep.
I remember in the old mailing list days proposing just a small class wrapper around the heapq functions (so, we’d get a sorted data-structure ready to use), and got hit by “not every small 10 liner need to become a stdlib class” reply that basically ended the thread there (even because I immediately agreed on it). Some 10 years later, though, lessons learned: it is not only just 10-extra lines: there is a lot of edge cases and extra functionality (make operators work, for example), that could go in a well crafted such wrapper-class around heapq.* - what happens is that people just reach for the “raw” heapq functions which results in code that is longer, harder to read, and “stays in the path between the programmer and his idea” in a “less Pythonic way” than ideal.
What’s the advantage of having it in collections rather than fetching sortedcontainers?
Note that for simple cases we do have something in the stdlib:
>>> l = []
>>> for w in ["x", "foo", "yy", "foobar", ""]:
... bisect.insort(l, w, key=len)
... print(l)
...
['x']
['x', 'foo']
['x', 'yy', 'foo']
['x', 'yy', 'foo', 'foobar']
['', 'x', 'yy', 'foo', 'foobar']
>>>
Depending on use case, there’s also heapq.
sortedcontainers is a marvel - generally better than anything that came before or after it. Its author gave a PyCon talk on it about a decade ago:
Near the end, he expressed mixed feelings about folding it into the core. Yes, its absence is conspicuous by its absence, but he was skeptical that key design decisions could survive the seemingly endless bikeshedding that comes with any public design debate. His own decisions were driven by extensive testing and benchmarking, nothing about fashion or social maneuvering.
So it’s a kind of a poster child for a shift in core development: in the very early “batteries included” days, Guido woiuld have likely said “sure, fold it in!”. But now it’s an illustration of a repeated Catch-22: “Put irt on PyPI first” to demonstrate real demand. “Ah, it giot tremendous uptake on P:yPI - so no need to put into the core”.
Grant (Jenks - the author) appears to have moved on to other things. So I expect not8ng will change,.While licensing allows for it, there is no precedent for putting something into the core without the author’s active cooperation
The very capable and popular regex extension module is in a similar boat, but in that case I believe (but don’t know) that its author doesn’t want to be tied to CPython’s release cycle and pretty elaborate workflows. Grant appears to be more put off by the low signal-to-noise ratio of the the public core design process.
Possible example: a predecessor of sortedcontainers had its version of sortedilst.pop() remove the first element of a list. To Grant “it was obvious” that it should remove the last element instead. So that’s what he did. In a public debate, it’s thoroughly predictable that someone would passionately argue to have two different methods to pick which, and someone else argue for an optional keyword argument to pick which. Some loon 
may then go to on to argue that a module-level flag should control the default, and then a thread-level default, and then a context manager ,..,. these things can go on for years, In the meantime, Grant applied his time instead to researching and achieving factor-of-10 speedups in plausible large workloads,.There’s an art to knowing when to say “good enough!” and move on, which comes hard to purists To my eyes, Grant was exceptionally skilled at that (for example, there are reasons to imagine that a Fenwick tree may do better than a “Jenks index” at speeding indexing by position, but best I know that wasn’t explored},
That’s what inspired sortedcontainers, in fact. Grant noticed that this very simple code ran much faster than eleaborte C-coded extension modules implementing assorted “asymptotically superior” tree structures.
The constant factor of the O(n) dead-simple approach is so small (mostly thanks to modern CPUs being blazing fast at moving pointers in L1 cache) that the list generally has to grow to over a thousand elements before O(\log{n}) tree structures repay their higher fixed costs.
Under the covers, a sortedcontainers.SortedList is just a list of Python lists. The sublists are magically kept small enough so that native bisect() and insort() operations remain very fast. Each sublist changes length on its own as needed, rarely requriring splitting, or merging with adjacent lists, when a sublist grows “too large” or “too small”, The devil in the details, of course,
Fair point! In my opinion it’s more about not needing an extra dependency for something this common, and having one implementation instead of everyone picking their library (in this case there are several high quality library with different backend structure).
Everyone thinks that their one dependency is extremely common. Got some stats on how common it is?
Do they have different benefits? Is there advantage to be had from the distinction?
Besides pypistats (~9 Million downloads/day), it’s used in projects like Dask distributed, Trio , and Angr just to cite a few. It’s also packaged in Debian and conda-forge.
Actually, they do. sortedcontainers isn’t a tree, it’s a list-of-sublists by design, it is tuned for cache locality. B-tree/RB-tree implementations trade some of that for guaranteed O(log n) worst-case and less memory overhead per element. I would say that different workloads favor different backends.
That’s a good reason NOT to have it in the stdlib then; if different workloads favour different modules, then it’s usually best that they all be on PyPI. (Unless there’s one very obvious default and the others are specialties or something.)
I see your point, but if the sorted-list-of-sublists design is this good, why hasn’t it shown up as standard approach in other languages? Rust chose a B-tree, C++ an RB-tree, I’m curious whether there’s something Python-specific making this approach shine, might it be interesting to try a C-extension B-tree implementation and benchmark it against sortedcontainers directly?
Besides pypistats (~9 Million downloads/day), it’s used in projects like Dask distributed, Trio , and Angr just to cite a few. It’s also packaged in Debian and conda-forge.
From my point of view it can be useful a proof of concept as a C-extension implementing a sorted set for example. Do you have any other ideas?
That’s hardly a lot, compared to (say) requests, which is used far more often and is also not in the stdlib. And Debian and conda-forge package huge numbers of Python libraries, so they aren’t really good indicators of whether something is worth including in the stdlib (quite the opposite, actually - because it’s provided by common distributors, it’s easily obtainable and so there’s less need for sortedcontainers to be in the stdlib).
My couple of cents is that it would make more sense to focus on more general “fast insertion/random access” data structure as opposed to “sorted container”.
Once you have one, making sorted structure is as trivial as SortedCollection « Python recipes « ActiveState Code.
If later we want full batteries for sorted container, optimized methods obj.bisect_[left|right] / obj.insort_[left|right] can be added later (fyi - these can also be made adaptive to similar degree that TimSort is).
The point is that it will be very awkward having SortedList, but being unable to use underlying structure for anything else.
So if this is desirable, I would suggest a technical thread where people can share and compare different list implementations that fit this profile, such as blist, sortedcontainers approach, tiered vector, etc.
I have done a fair bit of work on this exploration and would have some stuff to contribute to such thread, but haven’t yet arrived at something that I would be comfortable proposing to stdlib. Reason being is that, at least to me, implementing several of them is non-trivial effort and it is hard to commit until the landscape is fully explored and tested.
Also, note that implementing this in C is non-trivial endeavour and could be a large chunk of code and complexity - committing to something that proves sub-optimal later would be a big shame.
While if one is ok with Python implementation - sortedcontainers is your answer. If it is unmaintained and you want maintained - you can fork and maintain.
Do read the extensive sortedcontainrs docs. Grant did major testing against all available alternatives (including C extensions for B trees, AVL tress, red-black trees, …). sortedlist did as well as any, on speed and memory overhead, and better than most. It was a “category killer”, and especially effective under PyPy. The CPythion speed comes from that bisectalready does search and “insort” on plain Python lists in efficient C
Approaches to sorted dicts and sets are open to other tradeoffs. Grant’s version of a sorted dict uses a sortellist and a Python dict under the covers, and his version of a sorted set similarly uses a sortellist and a Python set under the covers. That’s not memory-efficient, but preserves expected O(1) lookup times.
O(1) indexing by position isn’t as important for sorted lists. The code does special-case indices of 0 and -1 (actually a bit more general than just that) so that uses as a priority queue (single or double ended!) do lookups in O(1) time.
Grant also rented time on “giant machines” to test performance at scale on containers with dozens of billions of elements. The results are also written up in the docs.
They did very well too, but for “very large” containers it can pay to increase the default “load factor”.. Most applications won’t care. For very, very large containers, the two-level structure of sortlist can become a hard bottleneck. It’s basically a very shallow but very broad B+-tree structure. In return for not scaling well “in theory” to unbounded sizes, practical sizes benefit from simpler (and faster) code.
Its attention to pragmatics is also impressive. For example, it’s apparently faster than anything else at initializing a large sorted list. Under the covers it uses list.sort() to leverage on Python’s “supernatural” sorting speed in cases of pre-existing order. Then it just chops the result up into contiguous sublists, a very fast linear-time operation,
I have no doubt that at a time it was A class work.
And indeed - there is nothing faster out there - I was surprised how it surpassed things implemented in C.
What I am saying is that my new digs suggest that there might be better alternatives.
For example. Tiered-vector (2nd order) based sort (fully in-place) has resulted in only 2x slower performance than TimSort with the same level of optimization. And my benchmarks of sortedcontainers don’t give an indication that it can do better without at least coding it up in C - especially for sizes up to 100K, where pure Python constants are quite high.
Even if sortedcontainers turn out to be the best approach, there are opportunities to optimize - both macro and micro. e.g. my alternative implementation has 10x faster __getitem__.
I don’t mind elaborating more on my findings / share code if there was a technical thread to push this. And if someone is going to push it - please make such thread first - at worst (or best - depending on POV) you will prove me wrong.
My point is that both ‘bisect’ and heapq could use a nice class wrapper - so one doesn’t need the external “l” and have to worry about nobody shuffling it around. That is even doubly truth in these days of static type checking - and maybe it can be the most compelling argument here: static type checkers have no way to know a list being kept to be used with bisect or heapq should not be modified by methods other than those. Having a wrapper class with “push” “pop” (and maybe some other amenities) instantly solves that.
+1! @rhettinger was agreeable at the time, so if’s surprisig nothing came of it then.,
@guido never subscribed to “OO religion”, so “it could be more OO” never carried much weight. There was a long tradition of coding heaps in C as plain old vectors, and that’s adequate for most real uses.
But Python only supported min heaps, and the “plain old list” API became error-prone when it went on to support max heaps too. Now that’s dealt with via tedious name near-duplication, like heappush() for (the original) min heaps, and heappusg_max() for (the newer) max heaps, Life would be better all around if the type of heap wanted were established at initialization time, with the same method names used for all.
But there’s also that heaps are rarely the best choice.. For example, priority queues are generally better handled by SortedList (which requires fewer comparisons, and is equally good at handling min- and max-queues), and n-way merging by some form of tournament tree (which some versions oif PyPy use to implement heaoq.merge(), not using heaps at all).
Heaps remain the best choice in one application aree: sorting when
But that’s become quite a niche use case too.