laziness, impatience, and hubris PerlMonks

Re^3: two order sort

by AnomalousMonk (Canon)
 on Mar 05, 2013 at 02:25 UTC ( #1021736=note: print w/ replies, xml ) Need Help??

in reply to Re^2: two order sort

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...

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

Replies are listed 'Best First'.
Re^4: two order sort
by BrowserUk (Pope) on Mar 05, 2013 at 03:49 UTC
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.)

You're right of course. You need ~ for both. (Seems I also forgot the details :)

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.
Re^4: two order sort
by LanX (Chancellor) on Mar 05, 2013 at 09:41 UTC

> 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 ???

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

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...)

Re^4: two order sort
by ag4ve (Monk) on Mar 07, 2013 at 16:11 UTC
Thanks for the routine and the module (and the article - I'll have to read that). The code works great.

Create A New User
Node Status?
node history
Node Type: note [id://1021736]
help
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others scrutinizing the Monastery: (8)
As of 2016-07-28 18:30 GMT
Sections?
Information?
Find Nodes?
Leftovers?
Voting Booth?
What is your favorite alternate name for a (specific) keyboard key?

Results (255 votes). Check out past polls.