Q for the old-timers: antecedents to the ST?

K

kj

This question is not about Perl per se, but about computer science
history.

In the Perl world, the term "Schwartzian Transform" (named after
Perl guru Randal Schwartz, author of the popular book Learning
Perl, among others, and numerous articles and internet postings)
is used to denote the tag-sort-untag strategy illustrated here:

my @sorted =
map $_->[0],
sort {$a->[1] cmp $b->[1]}
map [$_, expensive_function($_)],
@unsorted;

Now, I realize that Mr. Schwartz did not name this procedure after
himself, but rather someone else did. Still, I find it hard to
believe that he was the first person to make public the use of this
technique. After all, there is a very similar technique, which
I've seen referred to as "tag shuffling", for randomly shuffling
a list. In Perl it would be rendered like this:

my @shuffled =
map $_->[0],
sort {$a->[1] <=> $b->[1]}
map [$_, rand()],
@array;

This is basically an ST in which "expensive_function" is replaced
by rand().

I've seen mentions of this shuffling technique in sources much
older than Perl (maybe older than Mr. Schwartz). Given the similarity
of this technique with the general ST, I suspect that the credit
for inventing goes to some prior author. Can anyone confirm this
suspicion?

BTW, I have nothing but respect, admiration, and gratitude for
Randal Schwartz. From his writings and postings I know that he is
easily sharp and creative enough to have invented this technique
independently on his own, even if it had been invented earlier.
Moreover, as I've already pointed out, he did not give his own name
to the technique.

Nonetheless, I am intrigued by its origins.

kj
 
A

Anno Siegel

[posted to clpm and Cc'd to Randal Schwartz]

kj said:
This question is not about Perl per se, but about computer science
history.

In the Perl world, the term "Schwartzian Transform" (named after
Perl guru Randal Schwartz, author of the popular book Learning
Perl, among others, and numerous articles and internet postings)
is used to denote the tag-sort-untag strategy illustrated here:

my @sorted =
map $_->[0],
sort {$a->[1] cmp $b->[1]}
map [$_, expensive_function($_)],
@unsorted;

Now, I realize that Mr. Schwartz did not name this procedure after
himself, but rather someone else did. Still, I find it hard to
believe that he was the first person to make public the use of this
technique. After all, there is a very similar technique, which
I've seen referred to as "tag shuffling", for randomly shuffling
a list. In Perl it would be rendered like this:

my @shuffled =
map $_->[0],
sort {$a->[1] <=> $b->[1]}
map [$_, rand()],
@array;

This is basically an ST in which "expensive_function" is replaced
by rand().

It's not a very good algorithm as far a shuffling goes. An array can be
shuffled in linear time, sorting takes n*log n.
I've seen mentions of this shuffling technique in sources much
older than Perl (maybe older than Mr. Schwartz). Given the similarity
of this technique with the general ST, I suspect that the credit
for inventing goes to some prior author. Can anyone confirm this
suspicion?

BTW, I have nothing but respect, admiration, and gratitude for
Randal Schwartz. From his writings and postings I know that he is
easily sharp and creative enough to have invented this technique
independently on his own, even if it had been invented earlier.
Moreover, as I've already pointed out, he did not give his own name
to the technique.


Nonetheless, I am intrigued by its origins.

It's very simple. When Randal's method was discussed, it reminded someone
of the way Fourier- and Laplace transformations are used, for instance
in the area of solving differential equations: Transform the problem
into a space where the solution is easier, solve it there, then transform
back to arrive at a solution in the original space. So whoever it was,
half-jokingly called it "Schwartz Transform" and the name stuck. These
days it is used in all earnest to mean the sorting method in Perl that
was first described by Randal.

In my mind there is no claim involved to having invented the algorithm.
"Schwartz Transform" is only used in a Perl context, and it means a
particularly elegant way of sort-key caching that is possible in Perl,
no more no less.

I'm Cc-ing this reply to Randal, in case he wants to comment himself.

Anno
 
D

David H. Adler

Tom Christiansen, I'm pretty sure.

Yes, it was Tom. If memory serves, he didn't mean the eponymy as a
compliment... :)

dha
--
David H. Adler - <[email protected]> - http://www.panix.com/~dha/
"Well, to make this story the way it should be done we will
[need] technology that won't invented for 30 years and a budget that
could pay for a large south american country." "What have we got?" "25
cents and a block of wood." - Possible Dr. Who budget conference
 
R

Ron Savage

On Mon, 20 Jun 2005 04:47:03 +1000, kj wrote:

Hi kj
technique. After all, there is a very similar technique, which
I've seen referred to as "tag shuffling", for randomly shuffling a
list. In Perl it would be rendered like this:

It used to be called a 'tag sort', from the time when computer memory wastiny.

The algorithm was:
o Stockpile the key and the disk address for each record
o Sort the keys, dragging around the disk address with each key. This disk
address is no more than a (C-style) pointer to the data
o Retrieve the keys in sorted order, and with each key, get the disk addressand
from that the original record. So, you only need 1 record in memory at atime
o Write the records in sorted order

It's quite theoretical compared to most things students had to learn backthen,
and I can assure you getting the concept across was a painful process.

When I say theoretical, I don't mean difficult, but rather just that itrequired
a visualization manoeuvre students had simply never encountered before.
 
S

Sherm Pendley

Larry said:
Hmmm... I don't see what is so difficult about it. It seems that if
someone can't understand that algorithm

So difficult about what? What algorithm?

Please quote enough of the message you're replying to, so that your own
message makes sense.

sherm--
 
L

Larry

Hmmm... I don't see what is so difficult about it. It seems that if
someone can't understand that algorithm, they really don't understand
the concept of pointers and indirection, which is more fundamental
concept than any particular algorithm.
 

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Members online

No members online now.

Forum statistics

Threads
473,733
Messages
2,569,440
Members
44,830
Latest member
ZADIva7383

Latest Threads

Top