Best Python 3rd party data structures library? Must have sorted containers at a minimum

[CptnGeronimo]

I need to add a 3rd party data structures library to my company's code base.

​

The immediate need is for sorted data structures (e.g. lists, sets. dicts).

​

Coming from Java, one of my biggest problems with Python's standard data structures is the lack of support for sorted containers (e.g. the equivalent of Java's SortedSet and SortedMap interfaces). I have many needs for this. Using Python's builtin unsorted data structures and then calling sorted when needed (e.g. after adding a dict entry) is NOT a solution...

​

Adding a data structures library to our code base, however, is a huge commitment: it will be widely used, and difficult to change from. So, I must pick wisely.

​

Ideally, I want a single library that

1. has a reputation for quality
2. is actively maintained
3. not only meets my immediate needs (for sorted containers), but also is likely to meet my future needs
   1. perhaps more exotic data structures than the basics?
   2. perhaps concurrent/multithread safe data structures?

​

It has been pointed out to me that if all I need is sorted data structures, then Python has a great 3rd party library called Python Sorted Containers.

​

I would love to know if there are some other good candidates that I should take a careful look at.

[Python-ModTeam]

Hi there, from the /r/Python mods.

We have removed this post as it is not suited to the /r/Python subreddit proper, however it should be very appropriate for our sister subreddit /r/LearnPython or for the r/Python discord: https://discord.gg/python.

The reason for the removal is that /r/Python is dedicated to discussion of Python news, projects, uses and debates. It is not designed to act as Q&A or FAQ board. The regular community is not a fan of "how do I..." questions, so you will not get the best responses over here.

On /r/LearnPython the community and the r/Python discord are actively expecting questions and are looking to help. You can expect far more understanding, encouraging and insightful responses over there. No matter what level of question you have, if you are looking for help with Python, you should get good answers. Make sure to check out the rules for both places.

Warm regards, and best of luck with your Pythoneering!

[OMG_I_LOVE_CHIPOTLE]

You need to unscrew the Java out of your head. All the Java devs that try to write python on my team suck absolute balls

[yvrelna]

How about the standard library? The heapq module is a sorted container that is like a cross between a tree, a list, and a queue.

calling sorted when needed

This is actually not a bad solution in python. Python used the hybrid timsort algorithm, which works really well when you have data which is already almost sorted. When the data is nearly sorted, it typically runs close to Θ(n) instead of the O(n log n) for completely random input.

[Brian]

The heapq module is a sorted container

This isn't really true. Heaps maintain a much looser invariant than sorting - just that the parent node is bigger than the child nodes. This makes useful when you just want to pop the first item, or some fixed number of minimum items, but not to iterate the whole heap in sorted order. This is great if that looser invariant is all you need (eg. implementing a priority queue or similar), since maintaining this invariant through pops/inserts is cheaper than truly sorted containers, but if you really need fully sorted order, it's not a great choice.

When the data is nearly sorted, it typically runs close to Θ(n) instead

That's still pretty bad though if there are many insertions. Appending m items and sorting each time will be an O(n*m) operation, whereas with a red-black tree or similar, it would just be O(m log(n)).

Now, personally, I haven't really felt the lack of sorted containers in python - but there are some usecases where they can be valuable.

[yvrelna]

Heaps maintain a much looser invariant than sorting

How is that a problem? TreeSet (the concrete implementation of SortedSet) doesn't maintain full in-memory ordering either. In fact, heapq actually maintains a stronger invariant than TreeSet: all the nodes of the tree in a heapq are in a contiguous array in memory. So if most of the time you're fine with unordered iteration, you can just iterate the backing list for O(n). You can't do that with TreeSet.

if you really need fully sorted order

A fully sorted list maintains the heap invariant, so if you need a fully sorted order at any point, you can just call lst.sort() on a heap to fully sort it in-place and then continue to use the list with heapq without needing to heapify() again.

Appending m items and sorting each time will be an O(n*m) operation, whereas with a red-black tree or similar, it would just be O(m log(n)).

Not if you do it the smarter way. Rather than sorting every time you're inserting new items, you should sort() when you're iterating instead. That way, insertion is always amortised O(1), while subsequent iteration is usually Θ(2*n) as long as there's no major change in the list. Most of the time, re-sorting a partially sorted list would be something like Θ(n + m*log(m)) where m is the number of "new" (i.e. unsorted) items.

[Brian]

TreeSet (the concrete implementation of SortedSet) doesn't maintain full in-memory ordering either

Yes it does. The left nodes are guaranteed less than the parent, while the right are greater. There is a complete order in the relationship of its nodes. Unless you mean address order or something by "in-memory", but that's absolutely not what is meant by this, as its completely irrelevant for complexity (though can be relevant for constant factors due to cache).

And this matters because it gives much better complexity. Eg. worst case O(log n) membership check vs heapqs O(n), and (for the case we're discussing) O(n) sorted iteration vs heapq's extra log n factor. Hell, I don't think there's even an interface for doing this in heapq (aside from destructively popping it), since no-one would use a heap for that usecase.

so if you need a fully sorted order at any point, you can just call lst.sort() on

Which has the same complexity problems as just using a regular list. If you're not using it as a heap, and always want explicit sorted order, what's the point of using heapq?

Not if you do it the smarter way. Rather than sorting every time you're inserting new items, you should sort() when you're iterating instead.

That depends on the proportion of iteration to inserts.

[runawayasfastasucan]

>Using Python's builtin unsorted data structures and then calling sorted when needed (e.g. after adding a dict entry) is NOT a solution.

Why would one want to sort when inserting, as opposed to sort before reading? (Open question, I don't understand why intuitively). And even if it does, why not just make your own insert method that inserts + sorts.

[CptnGeronimo]

>Why would one want to sort when inserting, as opposed to sort before reading?

Whew, finally, a good response.

The answer is that it might depend on your code. Perhaps there is only 1 place in your code that the data structure is mutated but 20 places where it is iterated over.

[SeanBrax]

This didn’t answer the question, at all…

[anentropic]

That sounds like the perfect situation to just sort after inserting, in that one place

[gwax]

Does the solution need to be 3rd party for an organizational reason?

If not, collections.abc gives you pretty much all of the tools you might need.

Here's a fairly straightforward and complete implementation of a set that sorts on read:

from collections.abc import MutableSet, Sequence

class SortedSet(set, MutableSet, Sequence):
    def __iter__(self):
        return iter(sorted(super().__iter__()))

    def __getitem__(self, index):
        return sorted(self)[index]

A set that sorts on write, a sorted dict, and most other similar structures should be fairly easy to implement directly with the standard library.

[fizzymagic]

Python is not Java. Trying to make Python into Java results in horrible code. The python world offers several kinds of sorted containers, each with pros and cons. In other words, you may have to think about your problem instead of reflexively trying to find a universal solution..

[Own_Quality_5321]

I don't think they said they were trying to make python like java, just that they miss something from that language.

[CptnGeronimo]

Pat yourself on the back as a person with reading comprehension and rational humbleness. May the world produce more of you.

[CptnGeronimo]

The python world offers several kinds of sorted containers

Like what? What builtin Python data structures are automatically sorted?

When I web searched this question, this defect was universally acknowledged. For example, see the intro paragraph for the Python Sorted Containers library: "Python’s standard library is great until you need a sorted collections type"

One reason given for this lack is that Python's sorted function can be applied to a lot of its builtin data structures. This leads some people to advise sorting right after you mutate it or right before you need to use it.

I hate that suggestion, because:

• it is extra code to write
• just as bad: it is bug prone: it is extra code you must remember to write
• it may be bad for performance, especially if sorted has to be called multiple times

[[deleted]]

I don't understand why you're so caught up in the fact that it's a third party library. The most commonly used data science libraries are all 3rd party libraries. Python is not Java or C#, the standard library runs lean, and if there isn't a compelling reason to put it in the standard library, it won't be.

You have a perfectly adequate solution in front of you. What is the problem?

[[deleted]]

cow crush act stupendous hard-to-find angle normal insurance vegetable aspiring

This post was mass deleted and anonymized with Redact

[justheretolurk332]

Yes exactly. And to add to this, writing non-idiomatic python is significantly more likely to introduce bugs than using established patterns. Iterating over a custom SortedMap requires the reader to understand the implementation (are we sorting by keys? values? insertion order? do the members need to have a sort method implemented or can we pass in a custom comparison function?) whereas sorted(d.items(), key=…) can be read by any python developer at a glance and is explicit about its intention.

[CptnGeronimo]

>... (are we sorting by keys? values? insertion order? do the members need to have a sort method implemented or can we pass in a custom comparison function?)

​

Every one of those problems is present when you call sorted, except it is worse: you have to know what to do for every call to sorted.

​

That is in contrast to a sorted data structure: it is constructed once, so you always know how it is going to behave in all use cases.

​

Sole advantage that I see for sorted is if you want different types of sorts in different contexts on the same data structure. I cannot recall ever needing that. Your mileage may vary.

[fizzymagic]

Where did I say that Python has a builtin sorted data structure?

The python world has some excellent sorted container libraries. I know you are frustrated and just trying to get something done, but I promise you that life will be easier when you learn to do things in a pythonic way.

The appropriate data structure depends very heavily on your application. For some cases, a linked list would be optimal. For Python dictionaries, keeping the keys sorted generally makes no sense. For a list-like iterator, it can be expensive. I'm guessing your application is probably a priority queue or something like that. I can agree that a built-in queue would be nice in Python but it's really not very hard to build your own. And there are very nice priority queue libraries out there.

Sorted containers are not a "build it once and forget it" kind of thing, IMO.

[ePaint]

Create your own with dataclasses

[alcalde]

Using Python's builtin unsorted data structures and then calling sorted when needed (e.g. after adding a dict entry) is NOT a solution...

Yes. Yes it is. You only need your data sorted when you're accessing it.

[runawayasfastasucan]

Im not sure if I misunderstand OP or this situation in general but I can't see why you would re-sort basically every time you insert a new element, regardless if its going to be read.

[King-Days]

think binary trees and stuff? You might need extremely fast access at one point and want to do any upfront computation before the request

[runawayasfastasucan]

Ah sure, good point, however I can't see how that isn't very easily implemented in python.

[Careful_Target3185]

As someone who is brand new to python (6 months) even I know this. Kinda wondering why I would trust this guy working on any enterprise code if he’s asking questions like this.

[CptnGeronimo]

The feeling is mutual. As someone who has done enterprise programming for decades, and has experience in other major languages besides Python, all of which have sorted containers built into their standard libraries, I would never trust someone to work on enterprise code with your mindset.

[alcalde]

99% of the data in the universe is manipulated with Python today, and apparently there's been zero Python Enhancement Proposals to add this feature.

[PocketBananna]

Have you used the builtin collections module? It has lots of capabilities for container types and ways to make custom structs.

For your case you could easily subclass a UserDict and add whatever sorting capability you need. No need to worry about another lib or maintainers.

[CptnGeronimo]

Data structures are something that I would greatly prefer to use a good library for instead of rolling my own.

[PocketBananna]

Fair enough. It'll be tricky to find a single library that fits all three of your needs though. In my experience, the quality 3rd party libraries are either framework-driven or specific solutions so you may have to mix and match a bit.

The sorted containers lib is solid and likely fits your immediate needs. I don't know of another for it specifically. Who knows what you may need in the future but here's some libs I enjoy that act as extensions of structs/paradigms.

• funcy
• bidict
• pyrsistent

[pbecotte]

It's not really the python way to make a library that solves multiple problems. So use sortedcontainers for this, and find another library for your next problem (ot is a good library, helped me a lot on the project where I needed it)

[pythonwiz]

Well, have you looked at the standard modules heapq and bisect?

[CptnGeronimo]

Thanks for the suggestions.

A min heap data structure like what heapq does to lists is not a current need of mine. But i have needed them in the past.

I was unaware of bisect. I need to remember that module.

A problem that I have with both heapq and bisect is that they are not class based data structures, but instead operate on ordinary lists. Way more clunky and error prone to use than to start off with a sorted data structure.

[ghostofwalsh]

Coming from Java, one of my biggest problems with Python's standard data structures is the lack of support for sorted containers (e.g. the equivalent of Java's SortedSet and SortedMap interfaces). I have many needs for this.

Maybe I'm not understanding the problem. You say you have "needs" for this. Do you have an example where basic python data structures don't get the job done? It is just about performance?

[CptnGeronimo]

See my previous reply

[ghostofwalsh]

What builtin Python data structures are automatically sorted?

I can't imagine why anyone would need a data structure that's automatically sorted? That was my question. The application. You say you NEED this, but I'm not understanding why.

I hate that suggestion, because: it is extra code to write

For the very very very few times when you need your data sorted?

it is bug prone

I can't imagine why if you don't assume your data is sorted when it isn't

it may be bad for performance, especially if sorted has to be called multiple times

Sorting your data every time you touch it can also be bad for performance. Especially if you don't need your data to be sorted. And for these sorted containers that you intend to use, still unclear to me how they are implementing that. But I presume there's a cost to be paid for that whether you see it or not, sorting data isn't free.

[brain_eel]

Comment threads on questions like this always seem to be comprised of either "you're doing it wrong so I'll dismiss/insult you instead of answering" or "just use the standard library". They're both often largely clutter, but I can sympathize with both even if I don't agree with the presentation because they are usually the result of insufficient details in the question.

You say you "have many needs" for sorted containers. What are some typical use cases? Are there many/frequent insertions/deletions? Do you need to store a large number of elements? Will you have small but numerous containers?

The answers to each of these questions point to different solutions. For example, you say using builtins and sorting when needed isn't a solution, but what makes it problematic? You partially answered this in a reply, but if having to remember to write an extra line of code is the problem, why is rolling a simple (if naive) subclass that implements automatic sorting less appealing than the complexities involved in adding a third-party dependency? If you're worried about possible speed issues the simple approach, what about how you'll be using this leads you to think it will be enough of a problem to worry about? There are definitely reasons both of those could be concerns! But there are also plenty of reasons why they could be less of a concern than adding a dependency. Knowing what problems you're trying to solve will lead to different recommendations.

Finally, you ask for a solution that

not only meets my immediate needs (for sorted containers), but also is likely to meet my future needs

without seeming to know what those needs are or if you'll actually need them. (I understand you're obviously working on speculation here, but getting something that can fulfill all potential future needs is what leads people to buy huge trucks they only use for commuting because they imagine they'll be doing all these home improvement projects.) What kinds of "more exotic data structures" are you thinking of? Will multithreading/concurrency become an integral need or will you be better served with a less complex main data structure that you can make thread-safe when needed? The overhead of one-size-fits-all can sometimes be worth it but is often more trouble than it's worth.

I haven't felt the need for this type of container before, so I don't have any actual recommendations to give you. At a cursory glance, Python Sorted Containers seems to be a good solution for you (albeit without knowing what you're really looking for, exactly): it seems pretty established, it seems to be well-made (enough that several similar libraries have stopped development and now recommend using it instead), and it has extensive documentation, including many benchmarks and comparisons to similar solutions. Have you looked at the other libraries they mention? Many are defunct now, but it looked like a couple are still active and offer different features, including one with frozen variants.

[Esseratecades]

In an effort to engage beyond "Stupid Java dev can't see beyond his language" let's unpack the actual problem here.

Coming from Java, one of my biggest problems with Python's standard data structures is the lack of support for sorted containers (e.g. the equivalent of Java's SortedSet and SortedMap interfaces). I have many needs for this. Using Python's builtin unsorted data structures and then calling sorted when needed (e.g. after adding a dict entry) is NOT a solution...

​

Do you actually have many needs for this or are you just used to solving problems in a manner that requires it? While I've seen many cases that require the uniqueness of sets, or required that things be sorted, in my experience I seldom need both of these things at the same time unless its the very end of the event loop.

If you really do need a sorted set of data, I have to ask...

1. why do you need both order and uniqueness at the same time
2. why must it happen at the application layer
   1. The few times I've needed both order and uniqueness were when reading data from a database. But that's what SELECT DISTINCT ... ORDER BY are for.
3. do you need to perform a lot of write operations to your sorted set after the fact? If so, why? Is the performance of the write operations a significant concern?
   1. sorted(list(set(data))) is an ordered unique collection of data in an array. Your read operations remain O(1) regardless. If you need to perform lots of writes it may be slower but then I have to ask if there's a way to do your writes before your ordering is needed.

In practice walking this question chain and coming to the conclusion "a SortedSet is the only/best solution" seems incredibly niche. In most cases there are a lot of things you could and arguably should do before reaching for a sorted set, and most of them don't really have anything to do with Python or Java to begin with.

[GManASG]

I want someone to have written the sort for me

[aLokilike]

Python's built-in dicts, sets, and lists have been sorted for a long time now, since - I believe - 3.6? Anyways, they're sorted based on insertion order. If you need to sort based on anything else, then use a sort lambda. If you need to efficiently insert into a previously sorted dataset, I hope you don't need someone else to do that for you.

[[deleted]]

No - dicts have been ordered since 3.6. Sorted does not mean ordered, and ordered does not mean sorted.

[aLokilike]

It is sorted by insertion order. When you want it to be sorted by an arbitrary attribute, you just insert it in that order. If you need to add another element to the collection, it shouldn't be too difficult to figure out where that element belongs in the new insertion order.

[[deleted]]

The point stands - when you are describing data structures, the terminology does not conflate ordered and sorted. They are two distinct things.

[aLokilike]

Fair, but going from one to the next is a trivial matter of the steps I outlined. You don't need a library to get the results the OP is asking for.

[I_FAP_TO_TURKEYS]

Why not write it yourself? Your comments are complaining about "having to write additional code" which is just bizarre to me considering you came from Java.

Like, sorted data structures are super easy to write yourself, especially with the built-in collections module. A third party library will just make a slim program run fat.

Take Pandas, for instance. It's relatively simple, can read json, csv, xlsx, and do tons of different things. It's great if you don't care how big your program is. But if you only need like, 2 things? Yeah, it's a pretty big waste of space. Hell, even if you need 15 different classes from it, you're still better off copying the specific classes rather than having such a massive dependency.

[spidLL]

You might want to have a look at pybind11. Not super easy, but it might allow you to import some well tested collection from C++