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