[Python-ideas] Sorted lists

[Alex Chamberlain]

On Mon, 8 Apr 2019 at 06:19, Cameron Simpson <cs at cskk.id.au> wrote:
>
> 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>
> _______________________________________________
> Python-ideas mailing list
> Python-ideas at python.org
> https://mail.python.org/mailman/listinfo/python-ideas
> Code of Conduct: http://python.org/psf/codeofconduct/

Morning all,

I think a better abstraction for a sorted list is a new class, which
implements the Sequence protocol (and hence can be used in a lot of
existing list contexts), but only exposed mutation methods that can
guarantee that sorted order can be maintained (and hence is _not_ a
MutableSequence). AFAICT that means adding an `insert` method on top
of the standard read-only methods of a list and can be implemented
easily using the `bisect` module. I think this is a better option, as
it allows you to rely on that sorted order, rather than it being a
convention.

Thanks,

Alex