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
When I came from other programming languages to Python, I was missing trees, double-linked listes, sort-algos etc, too. But I quickly learned live being easier and me being more productive if I don't need to care about these.
Dicts are acceptable for most (of my) needs, being O(1) in average.
https://wiki.python.org/moin/TimeComplexity#dict
If I would dare for trees, I would checkout one of the many packages available https://pypi.org/search/?q=AVL+tree
(AVL being a real subset of red-black) or try numpy
@kirschwipfel I fail to see how lacking fundemental tools that not just improve performance but reduce the complexity of your own code somehow makes life easier.
@kirschwipfel hashtrees are only O(1) when looking up a specific value, they are far less efficient when you wish to traverse the keys of a hashmap in sorted order or to ask "which key comes after key X in the sort order"
Hashmaps are, and should be, the prefered choice when they suit the task. I am not implying we should have tree maps and not hash maps, that would be just as harmful.. but a good programmer (one who wants to keep their code efficient and minimal in complexity) needs both and both are used in different situations, and each is significantly more performant in their respective applications.
@kirschwipfel Thank you! when i come around again and am ready to address this issue (I shelved it for a much simpler approach that is 90% as good) I certainly will. Good to know they are out there.
@freemo I agree their might be use-cases where a tree actually makes sense.
Please check out some of the many (AVL) tree packages at PyPi. I'm quite confident there are well-maintained ones.