Beefy Boxes and Bandwidth Generously Provided by pair Networks
Pathologically Eclectic Rubbish Lister
 
PerlMonks  

Re^2: two order sort

by LanX (Canon)
on Mar 05, 2013 at 01:30 UTC ( #1021732=note: print w/ replies, xml ) Need Help??


in reply to Re: two order sort
in thread two order sort

you forgot to tell that your (Schwarzian) approach is not only better readable but much faster, because the sums are only calculated once per entry. =)

Cheers Rolf


Comment on Re^2: two order sort
Re^3: two order sort
by AnomalousMonk (Abbot) on Mar 05, 2013 at 02:25 UTC

    A decorate-sort-undecorate or GRT (Guttman-Rosler Transform) approach would be even faster, but I forgot how to decorate for descending sort. It's probably somewhere in A Fresh Look at Efficient Perl Sorting. Must look it up...

    Updates:

    1. See also Sort::Maker.
    2. According to the Wikipedia article linked by LanX herein, "decorate-sort-undecorate" is just another term for "Schwartzian Transform".

      I forgot how to decorate for descending sort.

      Just negate the field(s). Unary minus ('-') for numeric and boolean not ('~') for alpha:

      # Ascending numeric and ascending alpha print for map{ unpack 'x[Na4]a*', $_ } sort map{ local $^W; pack 'Na4a*', (0+$_), substr( $_, 1), $_ } @a;; 0cjlf 0dvys 0uvmu 1akkn 1imwi 1lpys 1pjzw 2uwep 3hiyn 3jrkx 3myrn 3ozcw 3rqhx 3vkon 6excm 7axqf 7lbhj 8klfd 9ijei 9klou # Descending numeric and ascending alpha print for map{ unpack 'x[Na4]a*', $_ } sort map{ local $^W; pack 'Na4a*', -(0+$_), substr( $_, 1), $_ } @a;; 0cjlf 0dvys 0uvmu 9ijei 9klou 8klfd 7axqf 7lbhj 6excm 3hiyn 3jrkx 3myrn 3ozcw 3rqhx 3vkon 2uwep 1akkn 1imwi 1lpys 1pjzw # Ascending numeric and descending alpha print for map{ unpack 'x[Na4]a*', $_ } sort map{ local $^W; pack 'Na4a*', (0+$_), ~substr( $_, 1), $_ } @a;; 0uvmu 0dvys 0cjlf 1pjzw 1lpys 1imwi 1akkn 2uwep 3vkon 3rqhx 3ozcw 3myrn 3jrkx 3hiyn 6excm 7lbhj 7axqf 8klfd 9klou 9ijei # Decending numeric and descending alpha print for map{ unpack 'x[Na4]a*', $_ } sort map{ local $^W; pack 'Na4a*', -(0+$_), ~substr( $_, 1), $_ } @a;; 0uvmu 0dvys 0cjlf 9klou 9ijei 8klfd 7lbhj 7axqf 6excm 3vkon 3rqhx 3ozcw 3myrn 3jrkx 3hiyn 2uwep 1pjzw 1lpys 1imwi 1akkn

      With the rise and rise of 'Social' network sites: 'Computers are making people easier to use everyday'
      Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error.
      "Science is about questioning the status quo. Questioning authority".
      In the absence of evidence, opinion is indistinguishable from prejudice.
        # Decending numeric and descending alpha ... pack 'Na4a*', -(0+$_), ~substr( $_, 1), $_ ... ;; 0uvmu 0dvys 0cjlf 9klou 9ijei 8klfd ... 1imwi 1akkn

        I think you fixed a  -substr( $_, 1) (- vice ~) that was there originally, but I was still puzzled by the sorting of 0 before 9 in an otherwise descending numeric sort. Looking at the bit fields in detail tells the tale: the  -(0+$_) expression should be  ~(0+$_) instead (in this particular case at least) to produce an effective descending numeric ordering from an actual ascending lexicographic sort.

        >perl -wMstrict -le "print unpack 'H*', pack 'N', -0; print unpack 'H*', pack 'N', -1; print unpack 'H*', pack 'N', -2; print unpack 'H*', pack 'N', -9; print unpack 'H*', pack 'N', -10; print ''; ;; print unpack 'H*', pack 'N', ~0; print unpack 'H*', pack 'N', ~1; print unpack 'H*', pack 'N', ~2; print unpack 'H*', pack 'N', ~9; print unpack 'H*', pack 'N', ~10; " 00000000 ffffffff fffffffe fffffff7 fffffff6 ffffffff fffffffe fffffffd fffffff6 fffffff5
        >perl -wMstrict -le "use List::Util qw(shuffle); ;; my @a = qw( 0uvmu 3rqhx 8klfd 2uwep 9klou 3jrkx 6excm 1imwi 7axqf 1lpys 0dvys 3ozcw 7lbhj 1pjzw 9ijei 3hiyn 3vkon 1akkn 0cjlf 3myrn ); ;; @a = shuffle @a; ;; print for map{ unpack 'x[Na4]a*', $_ } sort map{ local $^W; pack 'Na4a*', ~(0+$_), ~substr( $_, 1), $_ } @a " 9klou 9ijei 8klfd 7lbhj 7axqf 6excm 3vkon 3rqhx 3ozcw 3myrn 3jrkx 3hiyn 2uwep 1pjzw 1lpys 1imwi 1akkn 0uvmu 0dvys 0cjlf

        Hmmm...     This is trickier than it looks. And it looks kinda tricky. (And I don't say that my little fix is general.)

      > > your (Schwarzian) approach is not only better readable ...

      > A decorate-sort-undecorate or GRT approach would be even faster,

      I'm confused, IMHO "Schwartzian Transform" and "Decorate-Sort-Undecorate" are two names of the same thing ... right ???

      EDIT: see also Decorate-Sort-Undecorate in WP.

      UPDATE: OK I got it. You were referring to GRT beeing faster. =)

      (Advanced Sorting - GRT - Guttman Rosler Transform)

      Well in this case creating a float separating the two numeric values by a point should be fast enough.

      Cheers Rolf

        I'm confused, IMHO "Schwartzian Transform" and "Decorate-Sort-Undecorate" are two names of the same thing ...

        Actually, I had thought that "Decorate-Sort-Undecorate" and GRT were two names for the same thing. A look at the Wikipedia article you linked has undeceived me. (Apparently, even GRT is a misnomer. According to someone posting here at PM, the technique was first published back in the 60s or 70s and only relatively recently made widely known by Guttman and Rosler, for whom it is now named! Oh, well...)

      Thanks for the routine and the module (and the article - I'll have to read that). The code works great.

Log In?
Username:
Password:

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

How do I use this? | Other CB clients
Other Users?
Others exploiting the Monastery: (8)
As of 2014-11-27 16:12 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    My preferred Perl binaries come from:














    Results (186 votes), past polls