develooper Front page | perl.fwp | Postings from July 2003

Re: merlyn smeared by Python Johnnies' description of Schwartzian transform

Thread Previous | Thread Next
From:
Abigail
Date:
July 16, 2003 02:37
Subject:
Re: merlyn smeared by Python Johnnies' description of Schwartzian transform
Message ID:
20030716093751.GA991@abigail.nl
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

Thread Previous | Thread Next


nntp.perl.org: Perl Programming lists via nntp and http.
Comments to Ask Bjørn Hansen at ask@perl.org | Group listing | About