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

merlyn smeared by Python Johnnies' description of Schwartzian transform

Thread Next
July 16, 2003 02:25
merlyn smeared by Python Johnnies' description of Schwartzian transform
Message ID:
Perhaps I am posting this to wrong list, but that has become the norm
lately. :-)

I noticed on this page:
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?

Some links on Perl sorting:

/-\ - Yahoo! Mobile
- Check & compose your email via SMS on your Telstra or Vodafone mobile.

Thread Next Perl Programming lists via nntp and http.
Comments to Ask Bjørn Hansen at | Group listing | About