Beefy Boxes and Bandwidth Generously Provided by pair Networks
Don't ask to ask, just ask

Re: Understanding transformation sorts (ST, GRT), the details

by merlyn (Sage)
on May 17, 2005 at 22:32 UTC ( #458021=note: print w/replies, xml ) Need Help??

in reply to Understanding transformation sorts (ST, GRT), the details

As I was reading through the article, I was anxiously awaiting the appearance of the Schwartzian Transform.

But alas, even though you mention it in the title, and once in the body, you never got to it. Just the GRT, and Tye's particular trick.

I still think that the ST is always clearer than the GRT, and that jumping to the GRT without careful consideration is a case of premature optimization—except for those rare cases where the work required to wiggle your data into a single sortable string isn't all that unobvious.

By contrast, here's "sort a list of IP addresses" using the ST:

my @sorted = map $_->[0], sort { $a->[1] <=> $b->[1] or $a->[2] <=> $b->[2] or $a->[3] <=> $b->[3] or $a->[4] <=> $b->[4] } map [$_, split /\./], @inputs;
Quite a bit shorter than your code, and far less trickery and magic.

So, it's too bad your title is a letdown. Good analysis, otherwise.

-- Randal L. Schwartz, Perl hacker
Be sure to read my standard disclaimer if this is a reply.

Replies are listed 'Best First'.
Re^2: Understanding transformation sorts (ST, GRT), the details
by 5mi11er (Deacon) on May 17, 2005 at 22:41 UTC
    Ah, yes, you're right. When I started, I had intended to better show that understanding this one instance, which is a specific form of the GRT, which is in turn a specialization of the Schwartzian Transform, it's fairly easy to generalize the understanding to cover the more general cases.

    But, I never quite made it that far.

    Thanks for the vote of confidence anyway!

    Update: Let's attempt to rectify this situation.

    The analysis on the root node is a very specific, sort transformation technique. I've only just scratched the surface, but I believe this technique is very powerful and should be useful for nearly any sorting job. However, it's not the only technique out there. I think that by understanding this technique, you should be able to easily generalize this to better understand the other transformations.

    Guttman Rosler Transformations

    The next step up are the Guttman Rosler Transformations. The core idea of the GRT is to use the built in perl ascii sorting. In order to use this, we need to create stringified representations of our data first, then sort, then get the original data back. In a lot of cases, the map functions do a lot of work to put the data in the correct form, and then undo that work after the sort to get the data back. An example of this can be found at this node by jdporter.
    my @files = <DATA>; chomp @files; @files = map { substr $_, 10 } sort map { sprintf "%10s%s", /(\d+\w{3}\d{4})/, $_ } @files; print join "\n", @files, ''; __DATA__ fwlog.14Mar2005.gz fwlog.15Mar2005.gz fwlog.16Mar2005.gz fwlog.1Mar2005.gz fwlog.2Mar2005.gz fwlog.20Mar2005.gz
    Slightly modified to replace original @a array with more descriptive @files array

    In this case the OP wanted to sort the files by date. So, the above code took the array of text data in @files, simply grabbed the date string as-is, and appended that onto the front of the original string, sorted, and then extracted the original string. At first glance the map after the sort (the encoding map) doesn't do enough work to sort properly since it doesn't appear to align the days when dealing with single digits. However, it works because the sprintf("%10s"...) right justifies the text which does align the dates.

    Schwarzian Transformations

    In the same thread, there are multiple versions of a Schwartzian Transformation. A Schwartzian Transformation generally creates an array of 'stuff'; part of that array is the original data, other parts are the pieces to sort against. And the call back sorting routine is specified. Probably the best ST answer given is this one by RazorbladeBidet.
    my @months = qw( Jan Feb Mar Apr May Jun Jul Aug Sep Oct Nov Dec ); my %months; my $i = 1; $months{$_} = sprintf( "%02d", $i++ ) for @months; print $_, "\n" for map { $_->[0] } sort { $a->[1] <=> $b->[1] or $a->[2] <=> $b->[2] or $a->[3] <=> $b->[3] } map { (split(/\./,$_,3))[1] =~ /^(\d+)([A-Za-z]+)(\d+)$/; [$_, $3, $months{$2}, sprintf("%02d", $1) ] } @files;
    This is slightly modified from the original to show the intent of the original author. The original had sprintf("%02d", $3), or against the 4 digit year, which ends up to not do anything. I believe he'd intended to use that on the date itself.

    Here, he goes through the trouble to map the month abreviations to numbers via a generated hash, and makes sure to sort by year then month then day. Let's see how this works.

    Again the map statement after the sort is executed first, and it looks pretty complicated. The split is matching the periods in the filenames, and is only keeping the 2nd part which is the date information. It then matches and returns the individual parts of the date in $1, $2 and $3 corresponding to the day, month, year. Then, an array of 4 items is created, the original string, the year, the month in numeric format, and finally the date with a leading zero if date is a single digit. This is done for every member of the @files array.

    The resulting array of arrays is sent to the sort routine which uses the supplied call back function to compare first the year, then the numeric version of the month, and finally the date.

    The map function before the sort then gets called to pull out only the original version of the data, which is then printed rather than stored.


    Hopefully between the original node, and this subsequent analysis of the other transformations, this has given you enough understanding to use these powerful sorting techniques for your own needs.


      (split(/\./,$_,3))[1] =~ /^(\d+)([A-Za-z]+)(\d+)$/; [$_, $3, $months{$2}, sprintf("%02d", $1) ]
      I guess this is my day to point out bad uses of $1 in the first stage of a ST. {grin}

      So, to repeat what I said there...

      You are using $1, $2, $3 without testing the success of the match. This means that you might possibly be getting the previous round's data, resulting in duplicated output. What you should be doing instead is skipping over the erroneous entries, or perhaps dieing. Just to be different from the previous node, let's do the die thing:

      (split(/\./,$_,3))[1] =~ /^(\d+)([A-Za-z]+)(\d+)$/ or die "improperly + formed data: $_"; [$_, $3, $months{$2}, sprintf("%02d", $1) ]

      -- Randal L. Schwartz, Perl hacker
      Be sure to read my standard disclaimer if this is a reply.

Log In?

What's my password?
Create A New User
Domain Nodelet?
Node Status?
node history
Node Type: note [id://458021]
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others contemplating the Monastery: (2)
As of 2021-10-28 00:47 GMT
Find Nodes?
    Voting Booth?
    My first memorable Perl project was:

    Results (95 votes). Check out past polls.