# [Python-ideas] Sorted lists

Kirill Balunov kirillbalunov at gmail.com
Mon Apr 8 03:28:00 EDT 2019

```Basically, I like this idea and of course theoretically it has use cases. But
in the proposed form, it feels strongly curtailed. In practice, what does
it mean to be sorted?

[('a', 1),('b', 2),('bb', 4),('aaa', 3)]  # Is this list sorted?
[('a', 1),('aaa', 3),('b', 2),('bb', 4)]  # or this?
[('a', 1),('b', 2),('aaa', 3),('bb', 4)]  # or that?

The right answer is that they are all sorted by some means. So, if you
offer this __is_sorted__ attribute only for a very special case 1d list of
numbers - this makes no sense.  (Just re-read the recent thread, why .join
is the string method and not the *list *method). On the other hand If you
offer *some sort of a general protocol* storing a sort key or some other
useful information, then this is awesome! But is this achievable in
practice?

with kind regards,
-gdg

пн, 8 апр. 2019 г. в 05:38, Steven D'Aprano <steve at pearwood.info>:

> 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:
>
> - Empty lists, or lists with a single item, are created with
>   __issorted__ = True; lists with two or more items are created
>   with the flag set to False.
>
> - Appending or inserting items sets the flag to False.
>
> - Deleting or popping items doesn't change the flag.
>
> - Reversing the list doesn't change the flag.
>
> - Sorting it sets the flag to True. (The sort method should NOT
>   assume the list is sorted just because the flag is set.)
>
> Functions that require the list to be sorted can use the flag as a
> quick check:
>
>     if not alist.__issorted__:
>         alist.sort()
>     ...
>
> The flag will be writable, so that functions such as those in
> bisect can mark that they have kept the sorted invariant:
>
>
>     bisect.insort(alist, x)
>     assert alist.__issorted__
>
>
> Being writable, the flag is advisory, not a guarantee, and "consenting
> adults" applies. People can misuse the flag:
>
>     alist = [1, 4, 2, 0, 5]
>     alist.__issorted__ = True
>
> but then they have nobody to blame but themselves if they shoot
> themselves in the foot. That's no worse than the situation we have now,
> were you might pass an unsorted list to bisect.
>
> The flag doesn't guarantee that the list is sorted the way you want
> (e.g. biggest to smallest, by some key, etc) only that it has been
> sorted. Its up to the user to ensure they sort it the right way:
>
>     # Don't do this and expect it to work!
>     alist.sort(key=random.random)
>     bisect.insort(alist, 1)
>
>
> If you really want to be sure about the state of the list, you have to
> make a copy and sort it. But that's no different from the situation
> right now. But for those willing to assume "consenting adults", you
> might trust the flag and avoid sorting.
>
> Downsides:
>
> - Every list grows an extra attribute; however, given that lists are
>   already quite big data structures and are often over-allocated, I
>   don't think this will matter much.
>
> - insert(), append(), extend(), __setitem__() will be a tiny bit
>   slower due to the need to set the flag.
>
>
>
> Thoughts?
>
>
>
>
> --
> Steven
> _______________________________________________
> 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/
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.python.org/pipermail/python-ideas/attachments/20190408/4b35f231/attachment.html>
```