On Thu, 11 Nov 2021 11:01:32 -0800 Richard Levasseur richardlev@gmail.com wrote:
In the end, it was a fun exercise, but in practice a dictionary and sorted() got me 90% of the way there and sufficed. Optimizing that last 10% wasn't worth the effort.
Anyways, I came to two particular, IMHO, conclusions:
- Sorted collections are very niche. I *could* have used one, but probably
would have spent as much time fiddling with them as using a dict/sorted().
So the fact that sorted collections did not help for one single use case leads you to conclude that "sorted collections are very niche"? I don't find this very convincing.
Unfortunately, PyPI doesn't seem to offer a way to query the reverse dependencies of a package, otherwise we could know how many packages depend on the "sortedcontainers" package.
[...]
- If you're in a niche use case, especially for performance, then
abstractions aren't really helpful. Using e.g. a BTree and knowing the particulars of the implementation are going to be more helpful than having an abstract SortedList and working out how to use its special APIs for particular actions.
You don't have "an abstract SortedList", you have a concrete SortedList with a well-defined implementation with stable performance characteristics. So, again, this seems to be a red herring.
This basically echos Christopher Baker's sentiment of "whats the use case" and "why doesn't a sorted() call at the end suffice" to some extent.
The use case is obviously when you have to *maintain* sorting at all times. Yes, there are such situations. Some rather high-profile Python packages, such as dask/distributed, rely on this for rather elaborate algorithmic work (dask/distributed is a distributed task scheduler, you may also think of it as a replacement for Spark).
I won't go over your performance considerations, but I'll just mention that the "sortedcontainers" documentation has not one but *several* sections exploring performance characteristics in several dimensions. It is extremely rare for Python packages to provide such a detailed insight on the matter (even the built-in `dict` is much less thoroughly characterised). http://www.grantjenks.com/docs/sortedcontainers/#user-guide
Regards
Antoine.