[Python-ideas] Sorted lists

Steven D'Aprano steve at pearwood.info
Mon Apr 8 05:32:49 EDT 2019


On Mon, Apr 08, 2019 at 03:18:53PM +1000, Cameron Simpson wrote:

> 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 don't mind that.


> 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

That's not practical unless the list remembers what sort of sort order 
it is supposed to have:

- sorted smallest to biggest;
- or biggest to smallest;
- using what key.

That might be appropriate for a dedicated SortedList class, but not for 
generic lists. But a SortedList class probably shouldn't support 
operations which break the sorted invariant.


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

Well, yes, somebody has to sort the list at least once, otherwise it 
won't be sorted :-)

Currently bisect simply trusts that the list is sorted and makes no 
effort to even check. The API basically says:

    Pass a sorted list, or you'll get garbage. 

With this check in place, it is *possible* to change the API to:

    Pass a sorted list, or I'll sort it for you; if you lie, 
    you'll get garbage.


(Whether the maintainer of bisect thinks this is a good API change, I 
don't know.)

The median (and soon, quantiles) API says:

    I'm going to sort the list for you, whether you need it or
    not, just in case you do.

It could become:

    I'm going to sort the list for you, if necessary. If you 
    lie about it already being sorted, you'll get garbage.



-- 
Steven


More information about the Python-ideas mailing list