On 08Apr2019 12:32, Steven D'Aprano <st...@pearwood.info> wrote:
There are quite a few important algorithms which require lists to be
sorted. For example, the bisect module, and for statistics median and
other quantiles.
Sorting a list is potentially expensive: while Timsort is very
efficient, it is still ultimately an O(N log N) algorithm which limits
how efficient it can be. Checking whether a list is sorted is O(N).
What if we could check that lists were sorted in constant time?
Proposal: let's give lists a dunder flag, __issorted__, that tracks
whether the list is definitely sorted or not:
[...specifics, all looking pretty sane for a hand maintained advisory
flag...]
- insert(), append(), extend(), __setitem__() will be a tiny bit
slower due to the need to set the flag.
__setitem__ concerns me, along with other modification methods: what
about subclasses(*)? Every existing subclass which overrides __setitem__
now needs to grow code to maintain __issorted__ if they do not
themselves call list.__setitem__.
Also, should this imply an issorted() builtin to consult an instance's
__issorted__ dunder flag? Should such a builtin return False for
instances without an __issorted__ flag? I'm thinking yes since the flag
is intended to mean known-to-be-sorted.
Cheers,
Cameron Simpson <c...@cskk.id.au>
* I _know_ subclassing builtins is discouraged, but it is supported and
can be done if one is conservative.
_______________________________________________
Python-ideas mailing list
Python-ideas@python.org
https://mail.python.org/mailman/listinfo/python-ideas
Code of Conduct: http://python.org/psf/codeofconduct/
