[Python-Dev] Drastically improving list.sort() for lists of strings/ints (original) (raw)
Raymond Hettinger raymond.hettinger at gmail.com
Sun Sep 11 15:16:22 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 Sep 11, 2016, at 11:58 AM, Mark Dickinson <dickinsm at gmail.com> wrote:
So I suppose the thing to do is to benchmark stable radix sort against timsort and see if it's still worth it. Agreed; it would definitely be interesting to see benchmarks for the two-array stable sort as well as the American Flag unstable sort. (Indeed, I think it would be hard to move the proposal forward without such benchmarks.)
In the meantime, can I suggest moving this discussion to python-ideas.
There are many practical issues to be addressed:
- sort stability
- detecting whether you're dealing with a list of strings
- working with unicode rather than inputs limited to a one-byte alphabet
- dealing with the multiple compact forms of unicode strings (i.e. complex internal representation)
- avoiding degenerate cases
- cache performance
The referenced article tells us that "troubles with radix sort are in implementation, not in conception".
Raymond
- 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 ]