[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