🇳🇱
holy hell python doesnt even have a built in red-black tree implementation, just a hashmap style Dict... There is a third party implementation but the best one is something like 8 months since the last release and the repo only has 6 commits...
How do people even survive in #python?
@freemo I don’t think I’ve ever needed such a thing, I suspect most people haven’t, which is why there’s nothing built-in.
You may find what you want by looking instead at how people solve similar problems in Python. Might be something out there that has a red-black tree or similar at its core but isn’t advertised as such.
@pganssle Depends what you mean by “need”. Obviously you could always roll your own Treemap so in the strictest sense you never truly “need” it.
But presuming you are relatively active coder I can guarantee you that you have been in positions where having it would have either (or both) made your code simpler and/or more efficient.
Chances are you accomplished the same end result by either using a hashmap (ordinary dictionary) or a hashset, and just repeatedly sorting it by calling a sort function every time you needed a sorted version of the data (which you may have even done after every new insert in some extreme cases). Which means inefficient code (often significantly so) and more lines of code and more logic than you might need. Not to mention the potential for all sorts of issues on top of that if it is a multithreaded environment.
I have used and needed Tree maps more times than I can count though could have hacked around it easy enough if i had really wanted to.
@pganssle And yes, Treemaps and Navigable maps in most languages are backed by balanced red-black trees underneath or something very similar. So if you’ve ever seen a sorted map/dict in a language it was likely a red-black tree.
@freemo I am a very active coder, what I mean to say is that I have basically never been in a situation where my code was slow enough that it was a problem (and I do a lot of low-level library programming so that’s often “slow at all”) and benchmarks showed that dictionary hash map lookup is the bottleneck and switching implementations would fix it.
Python has a huge amount of overhead for most operations, so often the way to get high performance when you need it is to basically call an API that is a wrapper around an optimized implementation in a low-level language (e.g. numpy).
Admittedly, it may also be that the kind of programming I do is not likely to hit this problem, but I imagine the fact that there’s not an obvious choice here means that it’s either not a very common problem or this is an XY problem and you are overlooking more idiomatic solutions to your overall problem.
@freemo I don’t know the specifics of your situation so I may be way off base, but I often find that when people start using a new language or ecosystem they reach for the familiar idioms from their more comfortable language and don’t realize that in this new language you are meant to structure things differently. I have been guilty of this myself many, many times.
