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

Discussion in 'Perl Misc' started by kj, Jun 19, 2005.

  1. kj

    kj Guest

    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

    --
    NOTE: In my address everything before the first period is backwards;
    and the last period, and everything after it, should be discarded.
     
    kj, Jun 19, 2005
    #1
    1. Advertising

  2. kj

    Anno Siegel Guest

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

    kj <> wrote in comp.lang.perl.misc:
    >
    >
    >
    > 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
     
    Anno Siegel, Jun 19, 2005
    #2
    1. Advertising

  3. Anno Siegel <-berlin.de> wrote:


    > So whoever it was,



    Tom Christiansen, I'm pretty sure.


    > half-jokingly called it "Schwartz Transform" and the name stuck.



    --
    Tad McClellan SGML consulting
    Perl programming
    Fort Worth, Texas
     
    Tad McClellan, Jun 19, 2005
    #3
  4. On 2005-06-19, Tad McClellan <> wrote:
    > Anno Siegel <-berlin.de> wrote:
    >
    >
    >> So whoever it was,

    >
    >
    > Tom Christiansen, I'm pretty sure.
    >
    >
    >> half-jokingly called it "Schwartz Transform" and the name stuck.


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

    dha
    --
    David H. Adler - <> - 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
     
    David H. Adler, Jun 20, 2005
    #4
  5. kj

    Ron Savage Guest

    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.
     
    Ron Savage, Jun 20, 2005
    #5
  6. "Larry" <> writes:

    > 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--
     
    Sherm Pendley, Jun 20, 2005
    #6
  7. kj

    Larry Guest

    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.
     
    Larry, Jun 20, 2005
    #7
  8. kj

    kj Guest

    In <200562020035.916307@ron> Ron Savage <> writes:

    >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 was=
    > tiny.


    <snip>

    Thanks, Ron. Your account is what I was looking for.

    kj

    --
    NOTE: In my address everything before the first period is backwards;
    and the last period, and everything after it, should be discarded.
     
    kj, Jun 20, 2005
    #8
    1. Advertising

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

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Stephen Inkpen

    Timers in application web programming

    Stephen Inkpen, Jul 16, 2003, in forum: ASP .Net
    Replies:
    1
    Views:
    351
    Ken Cox [Microsoft MVP]
    Jul 16, 2003
  2. Kelsang Wangchuk

    System.Timers.Timer vs. System.Threading.Timer

    Kelsang Wangchuk, Jul 31, 2003, in forum: ASP .Net
    Replies:
    0
    Views:
    756
    Kelsang Wangchuk
    Jul 31, 2003
  3. Jim Hill
    Replies:
    3
    Views:
    425
    Jim Hill
    Feb 12, 2007
  4. *Prot3anThr3ad*

    old repository for old C++ source code

    *Prot3anThr3ad*, Sep 29, 2006, in forum: C++
    Replies:
    6
    Views:
    395
    *Prot3anThr3ad*
    Oct 2, 2006
  5. John Henry
    Replies:
    24
    Views:
    1,040
    alex23
    May 30, 2008
Loading...

Share This Page