sortedcontainers looks great! I very much appreciate it if such well-done library have type hints (embedded or at least in form of types-sortedcontainers pypi package).
>From my experience of multidict library support, it is not a super-hard challenge but something that needs attention and time resource from the library maintainers or third-party volunteers. On Thu, Nov 11, 2021 at 9:06 PM Richard Levasseur <richard...@gmail.com> wrote: > > > On Thu, Nov 11, 2021 at 4:30 AM Paul Moore <p.f.mo...@gmail.com> wrote: > >> On Thu, 11 Nov 2021 at 11:51, Antoine Pitrou <anto...@python.org> wrote: >> > >> > On Wed, 10 Nov 2021 21:12:17 -0600 >> > Tim Peters <tim.pet...@gmail.com> wrote: >> > > [Bob Fang <boyuf...@bytedance.com>] >> > > > This is a modest proposal to consider having sorted containers >> > > > (http://www.grantjenks.com/docs/sortedcontainers/) in standard >> library. >> > > >> > > +1 from me, but if and only if Grant Jenks (its author) wants that >> too. >> > > >> > > It's first-rate code in all respects, including that it's a fine >> > > example _of_ Python programming (it's not written in C - in Python). >> > >> > Agreed with Tim. This is a perfect example of some basic and perennial >> > facility that would fit very well in the stdlib. >> >> I agree as well. Is anyone interested enough to ask the library author >> if he supports doing this? That seems to be the main unanswered >> question here. >> >> But if anyone wants to argue the "the stdlib should be shrinking, not >> growing" position, I suggest they do so *before* someone reaches out >> to the module author. No point in us making the suggestion and then >> being forced to withdraw it. >> > > A couple 2 cents and IMHO. > > ----- > The tldr is not so much "don't put it in the standard lib", but that the > stdlib would be better having particular implementations instead of a > one-size-fits-all e.g. SortedList. > > Should the stdlib have e.g. SortedList? Probably not, because the use > cases of such data types are too niche to a one-size-fits-all > implementation, and there are too many implementations with too many of > their own settings. > Should it have e.g. BTree, RedBlackTree, SortedArrayList, etc? Probably > so, because those are somewhat fundamental data structures and > implementing, testing, and verifying them is very much non-trivial. While > niche, having them at your immediate disposal is very powerful. > ----- > > Last year, for fun, after wishing there was a SortedSet in the standard > lib, I ended up implementing a Red-Black Tree and BTree based sorted > dictionary/set[1]. After then trying to use them for my use case[2], I > found that, in order to fully and truly exploit their benefits, the basic > Sequence/Collection/Set/Dict APIs didn't really suffice. I needed APIs that > would let me, e.g. binary search to a particular spot and then iterate, or > give me a range between two points, etc. Such apis tend to be pretty > specialized to exploit their under data structure (which isn't to say an > abstract API can't be created, see Java's NavigableMap, but that level of > abstraction deserves careful consideration). > > 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: > 1. 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(). > 2. 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. > > 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. IME, > Python's sort algorithm is just really good, so it's hard to beat simply > calling sorted() when you're done processing in both runtime performance > and effort-spent-optimizing. I struggle to think of or remember a > particular case where dropping in a sorted collection would be a clear and > obvious win. Maybe a more memory constrained case where sorted() creating a > new list is too much? IDK. > > [1] As an aside, RB didn't perform nearly as well as sortedcontainers for > the majority of cases, but the naive BTree was about on par. IIRC, > sortedcollections is basically a specialized BTree. > [2] A wish that came about because I had sorted sets of exact/prefix > strings of 1,000 to 10,000 elements and needed them to interact in various > ways and wanted to preserve their sortedness. > > ----- > > re: "Is this particular one clearly the “best”[*]?" > > Performance wise, it's probably about the best insofar as a BTree of > depth=2 and high fanout (10,000 or something? I forget what > sortedcontainers defaults to) is. In my limited experience, it's docs and > claims about its performance were pretty accurate[3]. > > API wise, it has its share of idiosyncrasies like anything else. e.g. > SortedList claims to implement MutableSequence, but actually raises errors > when calling e.g. append(), which is a bit misleading / wrong to some > extent (to be fair, given MutableSequence's api contract, it's not like > there's particularly clear/right/good choice one can make here). > > (disclaimer: i've minimal experience with sortedcontainers; when I looked > at it, it was really only for comparing my own toy BTree/RBT > behavior/performance with a known implementation) > > [3] The exception being a claim that its (supposedly) better cache > locality is a significant factor. I think the underlying BTree algorithm is > the dominant factor. But someone who actually knows how to measure cache > locality would be a better judge of that than me, who doesn't know how. > > >> Paul >> _______________________________________________ >> Python-Dev mailing list -- python-dev@python.org >> To unsubscribe send an email to python-dev-le...@python.org >> https://mail.python.org/mailman3/lists/python-dev.python.org/ >> Message archived at >> https://mail.python.org/archives/list/python-dev@python.org/message/5SURNB4C5FGJ6LSXUPVW2EFP22ERKSGB/ >> Code of Conduct: http://python.org/psf/codeofconduct/ >> > _______________________________________________ > Python-Dev mailing list -- python-dev@python.org > To unsubscribe send an email to python-dev-le...@python.org > https://mail.python.org/mailman3/lists/python-dev.python.org/ > Message archived at > https://mail.python.org/archives/list/python-dev@python.org/message/HVZCFPKI7TY6WVLFK43KLVVDTEPIXFFQ/ > Code of Conduct: http://python.org/psf/codeofconduct/ > -- Thanks, Andrew Svetlov
_______________________________________________ Python-Dev mailing list -- python-dev@python.org To unsubscribe send an email to python-dev-le...@python.org https://mail.python.org/mailman3/lists/python-dev.python.org/ Message archived at https://mail.python.org/archives/list/python-dev@python.org/message/F6I4AR735TYIJ2WNAC4C43BEQJQPDJKZ/ Code of Conduct: http://python.org/psf/codeofconduct/
