On 4/7/2019 10:32 PM, Steven D'Aprano 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:
Does the CPython C-coded list structure have a unused bit that could be
used for this? (I realized that other implementations might have a
different answer.) Dunder names are not intended for directly use in
code. If __issorted__ is a property, it could instead by .is_sorted or
a new .is_sorted method, where is_sorted(bool) sets the property.
--
Terry Jan Reedy
_______________________________________________
Python-ideas mailing list
Python-ideas@python.org
https://mail.python.org/mailman/listinfo/python-ideas
Code of Conduct: http://python.org/psf/codeofconduct/
