[Python-Dev] Drastically improving list.sort() for lists of strings/ints (original) (raw)
Random832 random832 at fastmail.com
Tue Sep 13 13:35:10 EDT 2016
- Previous message (by thread): [Python-Dev] Drastically improving list.sort() for lists of strings/ints
- Next message (by thread): [Python-Dev] Drastically improving list.sort() for lists of strings/ints
- Messages sorted by: [ date ] [ thread ] [ subject ] [ author ]
On Tue, Sep 13, 2016, at 13:24, Nikolaus Rath wrote:
On Sep 11 2016, Terry Reedy <tjreedy at udel.edu> wrote: > Tim Peters investigated and empirically determined that an > O(n*n) binary insort, as he optimized it on real machines, is faster > than O(n*logn) sorting for up to around 64 items.
Out of curiosity: is this test repeated periodically on different architectures? Or could it be that it only ever was true 10 years ago on Tim's Power Mac G5 (or whatever he used)?
Binary insertion sort is still O(n*logn) in comparisons, so it's likely that this is due to short memmoves being sufficiently fast due to cache effects as not to matter. The number might have gotten larger or smaller, though. I wonder if it's something that could be tuned dynamically, at compile time or install time.
- Previous message (by thread): [Python-Dev] Drastically improving list.sort() for lists of strings/ints
- Next message (by thread): [Python-Dev] Drastically improving list.sort() for lists of strings/ints
- Messages sorted by: [ date ] [ thread ] [ subject ] [ author ]