[Python-ideas] Sorted lists
cs at cskk.id.au
Mon Apr 8 01:18:53 EDT 2019
On 08Apr2019 00:17, Terry Reedy <tjreedy at udel.edu> wrote:
>On 4/7/2019 10:32 PM, Steven D'Aprano wrote:
>>There are quite a few important algorithms which require lists to be
>>Proposal: let's give lists a dunder flag, __issorted__, that tracks
>>whether the list is definitely sorted or not:
>[...] 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.
Dunders are ok to use in implementation code (class internal). I agree
it's not nice to access from outside the class.
I was imagining a builtin that calls somethings .__issorted__ method.
But Steven's suggesting a flat dunder attribute rather than a callable
If this is a publicly queriable value, is there any need to have a
dunder name at all? Why not just give lists a public is_sorted
I'm also not convinced the cost to every insert/append is worth the
(subjectively to me) highly infrequent use.
I imagine one could increase the utility of the flag by implementing
insert/append with a bit of logic like:
check-previous/next elements to see if sortedness is preserved
so that a list constructed in sorted order may keep the flag. However,
it seems to me that such a list would accrue an O(n) cost with all of
those O(1) checks over the whole construction, and so not be cheaper
than just checking for sortedness aonce at the end before use.
Conjecture: anything that requires a sorted list but _accepts_ an
unsorted list (eg outer code which uses bisect or median) needs to check
for sortedness and sort if not already sorted.
So it feels to me like we've got an minimum O(n) cost regardless in most
circumstances, including constructing a list in sorted order from
scratch. And therefore the additional complexity added to
insert/append/__setitem__ probably outweigh the value of valuing an O(1)
check at the end; especially since while True is supposed to imply
sortedness, False doesn't imply out-of-order, just that we need to check
when sortedness is required.
Cameron Simpson <cs at cskk.id.au>
More information about the Python-ideas