[Python-Dev] Having Sorted Containers in stdlib?

[Bob Fang]

Hi All,

This is a modest proposal to consider having sorted containers 
(http://www.grantjenks.com/docs/sortedcontainers/ 
) in standard library. I know 
that usually adding stuff to standard library requires some strong arguments, 
so I will try my best to give my reasons here:

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. I understand languages might target different 
audiences, but I think Python’s standard library is quite extensive compared to 
peers. Consider we even have a sqlite driver in the stdlib, I do not think it 
is outrageous to have sorted containers. 
2) These containers are not really easy to implement correctly, and usually is 
out of the scope of day-to-day projects. Especially considering we have a large 
audience of non-hardcore programmers in Python community. They may have the 
need to use these structures, but they do not necessarily have the 
skill/knowledge to implement it. 
3) Granted, people can just pip install this library, but that is one extra 
step and less fraction is better for user experience.
4) These structures are very useful in competitive programming, I know at least 
in Leetcode this library is installed for Python.
5) The said library is of high implementation quality.

I might be stupid here as I am not the maintainer of this library and I might 
be not even in a position to submit it to Python as part of stdlib, but here 
are some of my personal thoughts and would love to hear your opinion!

Thanks!
Bob 

___
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/YB2JD477TKPB2HTXDW6ZXUBD6NFFFHHJ/
Code of Conduct: http://python.org/psf/codeofconduct/

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

[Bob Fang]

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  <mailto:boyuf...@bytedance.com>> wrote:
> This is a modest proposal to consider having sorted containers 
> (http://www.grantjenks.com/docs/sortedcontainers/ 
> <https://t.mailpgn.com/l/?u=5264d942-a595-49ac-a64a-986ce181d7fb&fl=https%3A%2F%2Ft.mailpgn.com%2Fl%2F%3Fu%3Da3e560c9-4417-427b-b976-19746738d8e5%26amp%3Bfl%3Dhttp%253A%252F%252Fwww.grantjenks.com%252Fdocs%252Fsortedcontainers%252F>)
>  in standard library. I know that usually adding stuff to standard library 
> requires some strong arguments, so I will try my best to give my reasons here:
> 
> As of 3.7. dicts are sorted[1], but I'm unsure if the order can be 
> overridden. Indeed:
> 
> >>> Boys = {'Tim': 18,'Charlie':12,'Robert':25}
> Girls = {'Tiffany':22}  
> 
> >>> print(cmp(Girls, Boys))
> Traceback (most recent call last):
>   File "", line 1, in 
> NameError: name 'cmp' is not defined
> >>> Girls.__gt__(Boys)
> NotImplemented
> 
> -- H
> -- 
> OpenPGP: https://hasan.d8u.us/openpgp.asc 
> <https://t.mailpgn.com/l/?u=b8770bd0-a9ef-411d-8c87-1636e6d9b77a&fl=https%3A%2F%2Ft.mailpgn.com%2Fl%2F%3Fu%3D5a3f5883-7b16-4b11-80ad-be68170836a1%26amp%3Bfl%3Dhttps%253A%252F%252Fhasan.d8u.us%252Fopenpgp.asc>
> If you wish to request my time, please do so using 
> bit.ly/hd1AppointmentRequest 
> <https://t.mailpgn.com/l/?u=8467f9a6-914d-4d6d-8c00-dd503e667146&fl=https%3A%2F%2Ft.mailpgn.com%2Fl%2F%3Fu%3D20c36f1d-4104-40d6-8c5e-b8bee61caaa4%26amp%3Bfl%3Dhttp%253A%252F%252Fbit.ly%252Fhd1AppointmentRequest>.
> Si vous voudrais faire connnaisance, allez a bit.ly/hd1AppointmentRequest 
> <https://t.mailpgn.com/l/?u=be22c143-79b8-4a2b-b7f9-cb7a95a8e7e4&fl=https%3A%2F%2Ft.mailpgn.com%2Fl%2F%3Fu%3D143cb038-fda7-4317-aef6-37d17da9dfde%26amp%3Bfl%3Dhttp%253A%252F%252Fbit.ly%252Fhd1AppointmentRequest>.
> 
>  
> <https://t.mailpgn.com/l/?u=b065018c-6b50-41c8-9881-508f9f2f30fa&fl=https%3A%2F%2Ft.mailpgn.com%2Fl%2F%3Fu%3D9c5843eb-43ed-470a-83fc-1ca514c43810%26amp%3Bfl%3Dhttps%253A%252F%252Fsks-keyservers.net%252Fpks%252Flookup%253Fop%253Dget%2526amp%253Bsearch%253D0xFEBAD7FFD041BBA1>Sent
>  from my mobile device
> Envoye de mon portable
> 1. https://softwaremaniacs.org/blog/2020/02/05/dicts-ordered/ 
> <https://t.mailpgn.com/l/?u=e7d71732-691a-421f-b43a-a9cdb3c2b9d0&fl=https%3A%2F%2Fsoftwaremaniacs.org%2Fblog%2F2020%2F02%2F05%2Fdicts-ordered%2F>___
> 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/RNXTH3JRUZ5WH33AKHVOSZF34FGNMS6S/
> 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/IQGAYFVN7556YUN3JE2EQA4TOSOVCNIE/
Code of Conduct: http://python.org/psf/codeofconduct/

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

[Bob Fang]

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 schedule and backwards 
> compatibility guarantees.

Totally agree. And as others mentioned in this thread, I agree the use cases 
for Sorted Containers are weak to make it worthwhile to be added to stdlib. I 
was more thinking about the completeness of the stdlib when I was proposing, 
but I do agree there is a cost/benefit analysis need to be done and it is great 
to see all the responses. 
As other pointed out this is mainly useful to implement some kind of cache, but 
since we already have lru_cache a lower level sorted dict may not be needed. 

Thanks for all the responses. 

Best,
Bob

___
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/TCCZZYGREV77OG6JBE3YWYE7NXOVZL4G/
Code of Conduct: http://python.org/psf/codeofconduct/

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

[Bob Fang]

> 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 of us agree then I am 
happy to reach out to the author since I am the one who started this thread.

Thanks,
Bob

> On 11 Nov 2021, at 12:28, Paul Moore  wrote:
> 
> On Thu, 11 Nov 2021 at 11:51, Antoine Pitrou  <mailto:anto...@python.org>> 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, 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.
> 
> Paul
> ___
> Python-Dev mailing list -- python-dev@python.org 
> <mailto:python-dev@python.org>
> To unsubscribe send an email to python-dev-le...@python.org 
> <mailto:python-dev-le...@python.org>
> https://mail.python.org/mailman3/lists/python-dev.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/
>  
> <https://mail.python.org/archives/list/python-dev@python.org/message/5SURNB4C5FGJ6LSXUPVW2EFP22ERKSGB/>
> Code of Conduct: http://python.org/psf/codeofconduct/ 
> <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/UUAFSF2JMWVVMUXV2QGXGJOFPPQJSFMH/
Code of Conduct: http://python.org/psf/codeofconduct/

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

[Bob Fang]

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 the reverse
> dependencies of a package, otherwise we could know how many packages
> depend on the "sortedcontainers" package.

___
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/44V6343BQQJQJP4CCFBIZAI5JQOM3XB7/
Code of Conduct: http://python.org/psf/codeofconduct/

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

[Bob Fang]

> 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 


And so if I am not mistaken any project that depends on trio will automatically 
need to have sortedcontainers as its dependency? I am not saying this alone 
will explain why sortedcontainers have large number of downloads, but with one 
or two projects like this it will push the number up maybe?

Best,
Bob


___
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/VW6ZJWGZZEBDHN4VQ4RSXJTUEUPOQHOV/
Code of Conduct: http://python.org/psf/codeofconduct/

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

[Bob Fang]

> 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 


And so if I am not mistaken any project that depends on trio will automatically 
need to have sortedcontainers as its dependency? I am not saying this alone 
will explain why sortedcontainers have large number of downloads, but with one 
or two projects like this it will push the number up maybe?

Best,
Bob

___
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/UWZ2S7UDXIBV4P4UEQIS2ZB7BLBKY6ZX/
Code of Conduct: http://python.org/psf/codeofconduct/

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

[Bob Fang]

> 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: 

https://www.wheelodex.org/projects/sortedcontainers/rdepends/?page=1 



Best,
Bob___
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/IT6XF34TJQQANG24AKPEC6RSWMA7BPSR/
Code of Conduct: http://python.org/psf/codeofconduct/