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

[David Mertz, Ph.D.]

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 ]
> > 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).
>
> People often say "well, put a thing on PyPI first, and see whether
> people really want it!".
>
> SortedContainers has been on PyPI for years straight now, and still
> gets hundreds of thousands of downloads from there every day:
>
> https://pypistats.org/packages/sortedcontainers
>
> So it's already widely adopted in the community. What else would it
> need to prove?
>
> If it still doesn't qualify, "well, put a thing on PyPI first" is just
> obstructionism ;-)
> ___
> 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/SE6YOVJQI6OEWNM5SAQL3X5VPEFGVZAA/
> 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/5NOGVTADSSSWPEWNHAMR35QYJJA7JDXH/
Code of Conduct: http://python.org/psf/codeofconduct/

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

[Tim Peters]

[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).

People often say "well, put a thing on PyPI first, and see whether
people really want it!".

SortedContainers has been on PyPI for years straight now, and still
gets hundreds of thousands of downloads from there every day:

https://pypistats.org/packages/sortedcontainers

So it's already widely adopted in the community. What else would it
need to prove?

If it still doesn't qualify, "well, put a thing on PyPI first" is just
obstructionism ;-)
___
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/SE6YOVJQI6OEWNM5SAQL3X5VPEFGVZAA/
Code of Conduct: http://python.org/psf/codeofconduct/

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

[Christopher Barker]

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 easily compared, or to generate and verify a
> signatures.
>

Yup -- I've done that. But for that, it's fine to sort when you are doing
the comparing / serialization. What I haven't been able to imagine is a use
case for keeping a
Mapping sorted constantly as you insert / remove items. For that you'd need
a use case where you were making sorted queries of various sorts. I
noticed, for instance, that the Java implementation posted earlier had
methods like "all the items after this one" (can't remember how that was
spelled).

I'm sure there are use cases for this, I'm probably lacking imagination :-)

-CHB


-- 
Christopher Barker, PhD (Chris)

Python Language Consulting
  - Teaching
  - Scientific Software Development
  - Desktop GUI and Web Development
  - wxPython, numpy, scipy, Cython
___
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/X7CGUBYQ3PEIYNMYAG3Z4SMXWILR5BKT/
Code of Conduct: http://python.org/psf/codeofconduct/

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

[Tim Peters]

[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 key is good enough".

A SortedDict supports several ways of doing that efficiently,
depending on what - exactly - an app means by "good enough". For
example, it's easy to find _the_ closest key. Or the k closest keys.
Or the two single keys <= and >=. Or ... Pick one; take some form of
average of their values; use a domain-specific interpolation function
on their keys & values; ...

To make it concrete, suppose you're running a COVID-19 app where
reports of new cases are coming in around the clock. One SortedDict
may be used to map latitude to the number of confirmed cases reported.
If a researcher asks for the number at a specific latitude, but no
exact match is found, fine, you can still efficiently show them the
results across the smallest known interval containing the latitude of
interest. Or if they want the results broken into buckets of latitudes
in 15-degree (N-degree - any N they ask for) intervals, also easy:
enumerating all entries in a given key range also goes fast. Or ...

A sorted list supports all sorts of membership queries efficiently.
Under the covers, a SortedDict _is_ a SortedList, plus a regular
Python dict to associate values with the list's elements.
___
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/FVDQZ4FJMSPYYTKNDRGLUXMOE226YIDK/
Code of Conduct: http://python.org/psf/codeofconduct/

[Python-Dev] The Steering Council elections.

[Thomas Wouters]

(Not sending this out as a SC member, just as myself.)

Because we're half-way through the nomination period, I want to remind
people about the Steering Council elections, and the fact that *you do not
have to be a Core Developer to be nominated*, just to nominate someone
(including yourself). If you know someone who you think would be a good
person to have on the Steering Council, Core Developer or not, talk to
them. Offer to nominate them, if you're a Core Developer, or talk to a Core
Developer to do it.

For more information, see PEP 13 (Python Language Governance)
, PEP 8103 (2022 Term steering
council election) , and Ee's
announcement

on
how to nominate.

We still have about a week left, and I know there's several people who are
planning to nominate, so I'm not worried about the number of nominations...
But I would personally like a good, sizable pool of candidates, because
it's much better for the health and longevity of the SC model. (I will also
be nominating myself, I just haven't gotten around to making the actual
post yet.)

Electably-y'rs,
-- 
Thomas Wouters 

Hi! I'm an email virus! Think twice before sending your email to help me
spread!
___
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/GWOWFYMNCQVYAYCO63A2WGN5KHLRTEDL/
Code of Conduct: http://python.org/psf/codeofconduct/

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

[Victor Stinner]

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, even written in Python, would be helpful.

Victor

On Wed, Nov 10, 2021 at 1:00 AM Bob Fang  wrote:
>
> 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/



-- 
Night gathers, and now my watch begins. It shall not end until my death.
___
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/X5AXOUUHN7HBTMIQZQTR5LCNSQJGY27B/
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/