On Wed, Jul 16, 2003 at 07:25:20PM +1000, Andrew Savige wrote:
> Perhaps I am posting this to wrong list, but that has become the norm
> lately. :-)
>
> I noticed on this page:
> http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/52234
> titled "a guaranteed-stable sort with the decorate-sort-undecorate
> idiom (aka Schwartzian transform)"
> --------------------------------------------------------------------
> "decorate-sort-undecorate" is a general and common idiom that allows
> very flexible and speedy sorting of Python sequences. An auxiliary
> list is first built (the 'decorate' step) where each item is made
> up of all sort-keys (in descending order of significance) of the
> corresponding item of the input sequence (must include all of the
> information in the whole corresponding item, and/or an index to it
> so we can fetch it back [or reconstruct it] in the third step).
> This is then sorted by its builtin sort method without arguments.
> Finally, the desired sorted-list is extracted/reconstructed by
> "undecorating" the now-sorted auxiliary-list.
> [This idiom is also known as "Schwartzian transform" by analogy with
> a similar Perl idiom (which, however, implies using map and grep and
> performing the whole sequence inside one single statement)].
> --------------------------------------------------------------------
>
> So these Python Johnnies think the Schwartzian transform uses grep,
> eh? I wish they gave an example.
>
> I may regret this, but I was just wondering if it would be more
> accurate to describe this Python decorate-sort-undecorate (DSU)
> thingy as a Guttman-Rosler transform? I suggest this because they
> state that using the builtin sort method without arguments is
> essential for performance reasons. My understanding is that the GR
> transform always uses the bald sort without arguments while the
> Schwartzian transform always uses a sort block. Is that right?
Yes. GRT usually have the form:
@sort = map { ... }
sort
map { ... } @unsorted;
with often pack/unpack in the map blocks, while an ST is usually
structured as:
@sort = map {$_ -> [0]}
sort { ... }
map {[$_ => ...]} @unsorted;
Abigail
