[Python-Dev] decorate-sort-undecorate
Tim Peters
tim.one at comcast.net
Tue Oct 14 16:08:59 EDT 2003
[Neil Schemenauer]
>>>> Clever idea I think. You don't need a special tuple, just a little
>>>> wrapper object that holds the key and the original value and uses
>>>> the key for tp_richcompare.
[Tim]
>>> That could work well. If a comparison function was specified too,
>>> it would only see the key (addressing one of Raymond's concerns).
[Raymond Hettinger, in darkness]
>> Don't you still need a tie-breaker index to preserve stability?
[Raymond, in light]
> Arghh! I see it now.
In case everyone doesn't, "the trick" is that the core sorting algorithm is
already stable. The only reason it needs a "cheap tie breaker" in
hand-rolled DSU is to stop (key, object) tuple comparison from falling back
to whole-object comparison when two keys tie. Falling back to whole-object
comparison is what can break stability (and chew up an enormous # of
cycles). If comparison is never handed the objects (only the keys), those
potential problems vanish, and stability is inherited.
More information about the Python-Dev
mailing list