[Python-ideas] Sorted lists

[Cameron Simpson]

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
>>sorted. [...]
>>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 
method.

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 
attribute?

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:

  if self.__issorted__:
    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.

Cheers,
Cameron Simpson <cs at cskk.id.au>