[Python-Dev] Re: Having Sorted Containers in stdlib?

I started writing up a SortedDict use case I have, but it's very elaborate and I expect it would just end with endless pointless argument about other approaches I _could_ take. But I already know all those ;-) So let's look at something conceptually "dead easy" instead: priority queues. They're a

[Python-Dev] Re: Having Sorted Containers in stdlib?

On 12.11.2021 17:46, Bob Fang wrote: > > >> On 12 Nov 2021, at 16:32, Marc-Andre Lemburg > > wrote: >> >> Perhaps there's a reverse dependency graph we could use to find out >> why the package is downloaded this often. I remember having seen >> a project which does this,

[Python-Dev] Re: Having Sorted Containers in stdlib?

On 11/12/2021 11:31 AM, Chris Angelico wrote: I think that proves the value of download counts: very little. The highest on the list is a thing called botocore, which I've never heard of. What is it? It's a dependency of a number of Amazon web services. My guess is that it's a dependency of

[Python-Dev] Re: Having Sorted Containers in stdlib?

> On 12 Nov 2021, at 16:32, Marc-Andre Lemburg wrote: > > Perhaps there's a reverse dependency graph we could use to find out > why the package is downloaded this often. I remember having seen > a project which does this, but have lost the URL. I believe this is the URL we are looking for:

[Python-Dev] Re: Having Sorted Containers in stdlib?

Yeah, a datapoint I didn't see mentioned is searching on public github repos for import sortedcontainers (which includes from sortedcontainers import). Obviously it's just one datapoint but it shows a very small count compared to other packages mentioned when looking at many of the stats

[Python-Dev] Re: Having Sorted Containers in stdlib?

> And yet, nobody(?) admits to either using it or knowing what it could be > used for. How very curious :-/ trio (which IMHO is a somewhat high profile uses it): https://github.com/python-trio/trio/blob/master/trio/_core/_run.py#L27

[Python-Dev] Re: Having Sorted Containers in stdlib?

> And yet, nobody(?) admits to either using it or knowing what it could be > used for. How very curious :-/ trio (which IMHO is a somewhat high profile uses it): https://github.com/python-trio/trio/blob/master/trio/_core/_run.py#L27

[Python-Dev] Re: Having Sorted Containers in stdlib?

On 12.11.2021 17:10, Steven D'Aprano wrote: > On Fri, Nov 12, 2021 at 10:07:13AM -0500, Paul Ganssle wrote: > >> I knew about sortedcontainers and I also don't remember ever seeing a >> situation where I needed one or recommended its use. > > We have a very odd situation where apparently

[Python-Dev] Re: Having Sorted Containers in stdlib?

On Sat, Nov 13, 2021 at 3:20 AM Steven D'Aprano wrote: > > On Fri, Nov 12, 2021 at 10:07:13AM -0500, Paul Ganssle wrote: > > > I knew about sortedcontainers and I also don't remember ever seeing a > > situation where I needed one or recommended its use. > > We have a very odd situation where

[Python-Dev] Re: Having Sorted Containers in stdlib?

On Fri, Nov 12, 2021 at 10:07:13AM -0500, Paul Ganssle wrote: > I knew about sortedcontainers and I also don't remember ever seeing a > situation where I needed one or recommended its use. We have a very odd situation where apparently sortedcontainers is one of the most well-known, popular,

[Python-Dev] Re: Having Sorted Containers in stdlib?

I think Richard's point was two-fold: People usually don't want or need this kind of thing /except/ when they have some very specific performance requirements, in which case they probably want to also be very specific about the kind of container they are using rather than using an abstract

[Python-Dev] Re: Having Sorted Containers in stdlib?

On Thu, Nov 11, 2021 at 11:01:32AM -0800, Richard Levasseur wrote: > 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.

[Python-Dev] Re: Having Sorted Containers in stdlib?

On Thu, Nov 11, 2021 at 11:22 AM Antoine Pitrou wrote: > On Thu, 11 Nov 2021 11:01:32 -0800 > Richard Levasseur 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

[Python-Dev] Re: Having Sorted Containers in stdlib?

[Christopher Barker ] > Earlier in the thread, we were pointed to multiple implementations. > > Is this particular one clearly the “best”[*]? > > If so, then sure. > > -CHB > > [*] best meaning “most appropriate for the stdlib”. A couple folks have > already pointed to the quality of the code. But

[Python-Dev] Re: Having Sorted Containers in stdlib?

On Thu, 11 Nov 2021 12:39:50 + Bob Fang wrote: > > 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

[Python-Dev] Re: Having Sorted Containers in stdlib?

On Thu, 11 Nov 2021 20:58:29 + Bob Fang wrote: > Just want to mention that we do have this nice website to look at, although I > am not sure how up to date it is: > > https://www.wheelodex.org/projects/sortedcontainers/rdepends/?page=1 Wow, thank you, that is very nice! Best regards

[Python-Dev] Re: Having Sorted Containers in stdlib?

Just want to mention that we do have this nice website to look at, although I am not sure how up to date it is: https://www.wheelodex.org/projects/sortedcontainers/rdepends/?page=1 > On 11 Nov 2021, at 19:20, Antoine Pitrou wrote: > > Unfortunately, PyPI doesn't seem to offer a way to query

[Python-Dev] Re: Having Sorted Containers in stdlib?

I'll join Christopher Barker and Chris Angelico in voicing scepticism -- personally, I feel like I'm yet to be persuaded that the use case is strong enough. sortedcontainers is a wonderful package, and I would completely support a prominent link to the library in the Python documentation. But the

[Python-Dev] Re: Having Sorted Containers in stdlib?

> 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. So I suppose we can take a poll on this? If majority

[Python-Dev] Re: Having Sorted Containers in stdlib?

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

[Python-Dev] Re: Having Sorted Containers in stdlib?

On Thu, 11 Nov 2021 11:01:32 -0800 Richard Levasseur 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:

[Python-Dev] Re: Having Sorted Containers in stdlib?

On Thu, Nov 11, 2021 at 4:30 AM Paul Moore wrote: > On Thu, 11 Nov 2021 at 11:51, Antoine Pitrou wrote: > > > > On Wed, 10 Nov 2021 21:12:17 -0600 > > Tim Peters wrote: > > > [Bob Fang ] > > > > This is a modest proposal to consider having sorted containers > > > >

[Python-Dev] Re: Having Sorted Containers in stdlib?

Serhiy Storchaka wrote: > From my C++ and Java experience, hashtable-based containers are much > more useful than tree-based containers. They are more compact and fast. > In most cases the only reason of using sorted container is supporting > deterministic iteration order, but often it is enough

[Python-Dev] Re: Having Sorted Containers in stdlib?

Earlier in the thread, we were pointed to multiple implementations. Is this particular one clearly the “best”[*]? If so, then sure. -CHB [*] best meaning “most appropriate for the stdlib”. A couple folks have already pointed to the quality of the code. But my understanding is that different

[Python-Dev] Re: Having Sorted Containers in stdlib?

On Thu, 11 Nov 2021 at 11:51, Antoine Pitrou wrote: > > On Wed, 10 Nov 2021 21:12:17 -0600 > Tim Peters wrote: > > [Bob Fang ] > > > This is a modest proposal to consider having sorted containers > > > (http://www.grantjenks.com/docs/sortedcontainers/) in standard library. > > > > +1 from me,

[Python-Dev] Re: Having Sorted Containers in stdlib?

On Wed, 10 Nov 2021 21:12:17 -0600 Tim Peters wrote: > [Bob Fang ] > > 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. > >

[Python-Dev] Re: Having Sorted Containers in stdlib?

I agree with Tim. Subject, of course, to the same caveat Tim mentions: does the creator want this? I haven't used the library much, but it's obviously top quality, and adding pure-Python code is less burden than C implementations. On Wed, Nov 10, 2021, 10:19 PM Tim Peters wrote: > [Bob Fang ]

[Python-Dev] Re: Having Sorted Containers in stdlib?

[Bob Fang ] > 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

[Python-Dev] Re: Having Sorted Containers in stdlib?

On Tue, Nov 9, 2021 at 11:05 PM Paul Bryan wrote: > On Tue, Nov 09, 2021 at 10:01:35PM -0800, Christopher Barker wrote: > > What are use cases for sorted dicts? > > Good question :-) It could be handy for deterministic iteration of its values, for example to > allow serialized values to be

[Python-Dev] Re: Having Sorted Containers in stdlib?

[Christopher Barker ] > Maybe a stupid question: > > What are use cases for sorted dicts? > > I don’t think I’ve ever needed one. For example, for some mappings with totally ordered keys, it can be useful to ask for the value associated with a key that's not actually there, because "close to the

[Python-Dev] Re: Having Sorted Containers in stdlib?

IMO if someone is motivated to get a new container type in Python, a PEP is required. A PEP has been written for the new removeprefix() and removesuffix() methods which are way simpler ;-) I expect many questions on corner cases for a sorted container type. Having a reference implementation,

[Python-Dev] Re: Having Sorted Containers in stdlib?

Hi Steve and all, Thanks! > Before we could even consider adding the sortedcontainers library to the > standard library, we would need to hear from the maintainer(s) of the > library that they agree to the move and would be able to continue > maintaining the library under our release

[Python-Dev] Re: Having Sorted Containers in stdlib?

10.11.21 01:47, Bob Fang пише: > 1) Some mainstream language support them out of box: C++ for example > have set/map which are sorted by the key order, and Java has TreeMap > which is internally a Red-black tree. >From my C++ and Java experience, hashtable-based containers are much more useful

[Python-Dev] Re: Having Sorted Containers in stdlib?

On Wed, 2021-11-10 at 17:16 +1100, Steven D'Aprano wrote: > On Tue, Nov 09, 2021 at 10:01:35PM -0800, Christopher Barker wrote: > > Maybe a stupid question: > > > > What are use cases for sorted dicts? > > > > I don’t think I’ve ever needed one. > > Good question :-) It could be handy for

[Python-Dev] Re: Having Sorted Containers in stdlib?

On Wed, Nov 10, 2021 at 5:45 PM Steven D'Aprano wrote: > > On Wed, Nov 10, 2021 at 05:11:33PM +1100, Chris Angelico wrote: > > > Nothing's technically new. You could make an inefficient sorted dict like > > this: > > > > class SortedDict(dict): > > def __iter__(self): return

[Python-Dev] Re: Having Sorted Containers in stdlib?

On Wed, Nov 10, 2021 at 05:11:33PM +1100, Chris Angelico wrote: > Nothing's technically new. You could make an inefficient sorted dict like > this: > > class SortedDict(dict): > def __iter__(self): return iter(sorted(self.keys())) You would need more than that. You would want to ensure

[Python-Dev] Re: Having Sorted Containers in stdlib?

On Tue, Nov 09, 2021 at 10:01:35PM -0800, Christopher Barker wrote: > Maybe a stupid question: > > What are use cases for sorted dicts? > > I don’t think I’ve ever needed one. Good question :-) > Also, I can’t quite tell from the discussion If a “sorted dict” implements > something new, or

[Python-Dev] Re: Having Sorted Containers in stdlib?

On Wed, Nov 10, 2021 at 5:03 PM Christopher Barker wrote: > > Maybe a stupid question: > > What are use cases for sorted dicts? > > I don’t think I’ve ever needed one. Me neither, tbh. > Also, I can’t quite tell from the discussion If a “sorted dict” implements > something new, or is an

[Python-Dev] Re: Having Sorted Containers in stdlib?

A quick Google for "treap python github" yielded https://github.com/TheAlgorithms/Python/blob/master/data_structures/binary_tree/treap.py . On Tue, 9 Nov 2021 at 21:49, Dan Stromberg wrote: > > On Tue, Nov 9, 2021 at 9:00 PM Steven D'Aprano > wrote: > >> Sorting dicts has been discussed on the

[Python-Dev] Re: Having Sorted Containers in stdlib?

Maybe a stupid question: What are use cases for sorted dicts? I don’t think I’ve ever needed one. Also, I can’t quite tell from the discussion If a “sorted dict” implements something new, or is an internal data structure that gives better performance for particular use cases. I.e. is a sorted

[Python-Dev] Re: Having Sorted Containers in stdlib?

On Tue, Nov 9, 2021 at 9:00 PM Steven D'Aprano wrote: > Sorting dicts has been discussed on the Python-Ideas mailing list, it is > too hard and expensive to justify for the limited use-cases for it. If > you want to sort a dict, you are best to sort the dict's keys, then > create a new dict. Or

[Python-Dev] Re: Having Sorted Containers in stdlib?

Hi Bob and welcome, Before we could even consider adding the sortedcontainers library to the standard library, we would need to hear from the maintainer(s) of the library that they agree to the move and would be able to continue maintaining the library under our release schedule and backwards

[Python-Dev] Re: Having Sorted Containers in stdlib?

On Tue, Nov 09, 2021 at 04:23:50PM -0800, Hasan Diwan wrote: > As of 3.7. dicts are sorted[1], but I'm unsure if the order can be > overridden. Dicts are not sorted, they are kept in insertion order. >>> d = {3: 'a', 4: 'b', 1: 'c', 2: 'd'} >>> d {3: 'a', 4: 'b', 1: 'c', 2: 'd'}

[Python-Dev] Re: Having Sorted Containers in stdlib?

On Tue, 9 Nov 2021, 17:05 Bob Fang, wrote: > But that’s in insertion order, not in key order right? I think we need > data structure that are key-ordered. > According to the tests, it seems to be key-ordered. It also appears that the ordering cannot be changed (yet?). -- H

[Python-Dev] Re: Having Sorted Containers in stdlib?

But that’s in insertion order, not in key order right? I think we need data structure that are key-ordered. > On 10 Nov 2021, at 00:23, Hasan Diwan wrote: > > > On Tue, 9 Nov 2021 at 16:01, Bob Fang > wrote: > This is a modest proposal to consider having

[Python-Dev] Re: Having Sorted Containers in stdlib?

On Tue, 9 Nov 2021 at 16:01, Bob Fang wrote: > This is a modest proposal to consider having sorted containers ( > http://www.grantjenks.com/docs/sortedcontainers/ >