[Python-ideas] Optimizing list.sort() by checking type in advance

[Elliot Gorokhovsky]

It would still be stable. You would copy over {{x,1.0},{y,1.0},{x,1.0}},
and as long as a stable sort is used you would get out the same array,
using the cmp function left->key < right->key.  Then you would go in order,
copying back [x,y,x].

On Mon, Oct 10, 2016 at 9:49 PM Chris Angelico <rosuav at gmail.com> wrote:

> On Tue, Oct 11, 2016 at 2:41 PM, Elliot Gorokhovsky
> <elliot.gorokhovsky at gmail.com> wrote:
> > Oh no, the idea here is just you would copy over the floats associated
> with
> > the PyObject* and keep them in an array of such structs, so that we know
> > which PyObject* are associated with which floats. Then after the standard
> > library quicksort sorts them you would copy the PyObject* into the list.
> So
> > you sort the PyObject* keyed by the floats. Anyway, I think the copying
> back
> > and forth would probably be too expensive, it's just an idea.
>
> It also wouldn't work if you have more than one object with the same value.
>
> >>> x = 1.0
> >>> y = 2.0/2
> >>> x is y
> False
> >>> l = [x, y, x]
> >>> l.sort()
> >>> assert l[0] is x
> >>> assert l[1] is y
> >>> assert l[2] is x
>
> Python's sort is stable, so the three elements of the list (being all
> equal) must remain in the same order.
>
> ChrisA
> _______________________________________________
> 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/20161011/34c75ef1/attachment.html>