Pathologically Eclectic Rubbish Lister PerlMonks

### Re^2: two order sort

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

in reply to Re: 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

Replies are listed 'Best First'.
Re^3: two order sort
by AnomalousMonk (Chancellor) 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...

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

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

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://1021732]
help
Chatterbox?
 [Corion]: Meh, first round of escalations for me not wanting to fix in production what a project has mismanaged. Now another project, which eats up all the resources until end of this year wants to take that task and put it on my list of things as well. [Corion]: So now there will be the fun of me explaining to the project that \$other_project had low priority because \$project has high priority. If \$project picks up the task from \$other_project, they also will need to reprioritize my tasks to get that done... [Corion]: ... of course at the cost of something else on my list of tasks for \$project, as there only is a finite amount of days until \$deadline.

How do I use this? | Other CB clients
Other Users?
Others scrutinizing the Monastery: (8)
As of 2017-08-17 12:22 GMT
Sections?
Information?
Find Nodes?
Leftovers?
Voting Booth?
Who is your favorite scientist and why?

Results (287 votes). Check out past polls.

Notices?