Beefy Boxes and Bandwidth Generously Provided by pair Networks
Keep It Simple, Stupid
 
PerlMonks  

Sorting Index of An Array

by neversaint (Deacon)
on May 14, 2007 at 09:40 UTC ( #615254=perlquestion: print w/replies, xml ) Need Help??

neversaint has asked for the wisdom of the Perl Monks concerning the following question:

Dear Masters,
Suppose I have a SINGLE dimensional array, which always forms a 'matrix'. This array can always be seen as m x n matrix. In this example 9x9 matrix:
@sim = ( 1.0, 0.9, 0.3, 0.6, 0.3, 0.3, 0.2, 0.3, 0.3, 0.9, 1.0, 0.3, 0.5, 0.3, 0.1, 0.2, 0.3, 0.4, 0.3, 0.3, 1.0, 0.6, 0.3, 0.2, 0.2, 0.3, 0.4, 0.6, 0.6, 0.6, 1.0, 0.2, 0.2, 0.3, 0.4, 0.5, 0.3, 0.3, 0.3, 0.2, 1.0, 0.1, 0.3, 0.4, 0.5, 0.3, 0.2, 0.2, 0.2, 0.1, 1.0, 0.2, 0.3, 0.2, 0.1, 0.2, 0.2, 0.3, 0.3, 0.1, 1.0, 0.8, 0.6, 0.3, 0.3, 0.2, 0.4, 0.4, 0.3, 0.8, 1.0, 0.8, 0.3, 0.4, 0.4, 0.5, 0.5, 0.2, 0.6, 0.8, 1.0 );
The problem is how can we sort this SINGLE array into another SINGLE array, such that the index is sorted decreasingly according to similarity value in @sim. That it gives this array as an output:
@index_ordered = ( 0, 1, 3, 2, 5, 8, 4, 7, 6, 1, 0, 3, 8, 2, 4, 7, 5, 6, 2, 3, 8, 0, 1, 4, 5, 7, 6, 3, 0, 2, 1, 8, 7, 6, 4, 5, 4, 8, 7, 0, 1, 2, 6, 3, 5, 5, 0, 7, 2, 3, 1, 8, 6, 4, 6, 7, 8, 3, 4, 2, 1, 5, 0, 7, 8, 6, 3, 4, 1, 5, 2, 0, 8, 7, 6, 3, 4, 2, 1, 0, 5 ); # This is created manually
So for example the first 'row' of @sim contain this line:
1.0, 0.9, 0.3, 0.6, 0.3, 0.3, 0.2, 0.3,0.3, and the 'index' is: 0 1 2 3 4 5 6 7 8 #this index value is seen "as if" it is stored in one array, #and not the overall index in @sim
If we sort that 'first row' of @sim, it will give this 'first row' in @index_ordered
0, 1, 3, 2, 5, 8, 4, 7, 6,
So every 'row' in @sim correspond to the 'row' in @index_ordered and sorted. Thus the 'dimension' of @sim and @index_ordered is the same.

---
neversaint and everlastingly indebted.......

Replies are listed 'Best First'.
Re: Sorting Index of An Array
by shmem (Chancellor) on May 14, 2007 at 10:16 UTC

    Use a Schwartzian transform - like this: (update: but see salva's comment below for a better approach)

    @sorted = map {$_->[0]} map { $i=0; sort {$b->[1]<=>$a->[1]} map {[$i++,$_]} splice (@s +im,0,9) } 0..8; print "\@index_ordered =(\n"; for(0..8) { print " " x 4, join(', ', splice (@sorted,0,9) ),"\n"; } print ");\n";

    Output:

    @index_ordered =( 0, 1, 3, 2, 4, 5, 7, 8, 6 1, 0, 3, 8, 2, 4, 7, 6, 5 2, 3, 8, 0, 1, 4, 7, 5, 6 3, 0, 1, 2, 8, 7, 6, 4, 5 4, 8, 7, 0, 1, 2, 6, 3, 5 5, 0, 7, 1, 2, 3, 6, 8, 4 6, 7, 8, 3, 4, 1, 2, 0, 5 7, 6, 8, 3, 4, 0, 1, 5, 2 8, 7, 6, 3, 4, 1, 2, 0, 5 );

    For equal elements in each row of @sim the order of their indices is undetermined. Note that this is destructive to @sim - it will be empty after the sort.

    While the above code DWYM, you would have been better off having an array of arrays in the first place.

    --shmem

    _($_=" "x(1<<5)."?\n".q·/)Oo.  G°\        /
                                  /\_¯/(q    /
    ----------------------------  \__(m.====·.(_("always off the crowd"))."·
    ");sub _{s./.($e="'Itrs `mnsgdq Gdbj O`qkdq")=~y/"-y/#-z/;$e.e && print}
      Use a Schwartzian transform

      To sort lists of nine elements, applying the ST is probably counterproductive. And anyway, for that particular problem, using a Orcish Maneuver would be more suitable:

      my @index_sorted = map { my @row = splice @sim, 0, N; sort { $row[$b] <=> $row[$a] } 0..(N-1); } 0..(M-1);
        Just a nit - while your approach is far better than mine and less convoluted, there's no OR and no cache, so there's no Orcish (or-cache) Maneuver. That would be (from Shlomo Yona's Perl lectures 2002):

        The Orcish Maneuver -- example

        keys my %or_cache = @in; @out = sort { ($or_cache{$a} ||= KEY($a)) cmp ($or_cache{$b} ||= KEY($b)) } @in;

        The first part of the sortsub sees if the sortkey for $a is cached.

        If not, it extracts the value of the sortkey from the operand and caches it.

        The sortkey for $a is then compared to the sortkey for $b.

        Anyways, salva++ for simplifying things :-)

        --shmem

        _($_=" "x(1<<5)."?\n".q·/)Oo.  G°\        /
                                      /\_¯/(q    /
        ----------------------------  \__(m.====·.(_("always off the crowd"))."·
        ");sub _{s./.($e="'Itrs `mnsgdq Gdbj O`qkdq")=~y/"-y/#-z/;$e.e && print}
Re: Sorting Index of An Array
by salva (Canon) on May 14, 2007 at 11:25 UTC
    use constant M => 9; use constant N => 9; my @index_sorted; for my $m (0..(M-1)) { my $ix0 = $m * N push @index_sorted, sort { $sim[$ix0 + $b] <=> $sim[$ix0 + $a] } 0..(N-1); }
      Ooops!
      syntax error at /tmp/615254.pl line 41, near "N push"
      After some correction (and addition to print out the sorted array), here is the result:
      0 1 3 2 4 5 7 8 6 1 0 3 8 2 4 7 6 5 2 3 8 0 1 4 7 5 6 3 0 1 2 8 7 6 4 5 4 8 7 0 1 2 6 3 5 5 0 7 1 2 3 6 8 4 6 7 8 3 4 1 2 0 5 7 6 8 3 4 0 1 5 2 8 7 6 3 4 1 2 0 5
      This orcish manuever is really new to me. And I'm tempted to benchmark these two techniques. Here it goes:
      #!/usr/bin/perl use strict; use warnings; my @sim_st = qw( 1.0 0.9 0.3 0.6 0.3 0.3 0.2 0.3 0.3 0.9 1.0 0.3 0.5 0.3 0.1 0.2 0.3 0.4 0.3 0.3 1.0 0.6 0.3 0.2 0.2 0.3 0.4 0.6 0.6 0.6 1.0 0.2 0.2 0.3 0.4 0.5 0.3 0.3 0.3 0.2 1.0 0.1 0.3 0.4 0.5 0.3 0.2 0.2 0.2 0.1 1.0 0.2 0.3 0.2 0.1 0.2 0.2 0.3 0.3 0.1 1.0 0.8 0.6 0.3 0.3 0.2 0.4 0.4 0.3 0.8 1.0 0.8 0.3 0.4 0.4 0.5 0.5 0.2 0.6 0.8 1.0 ); my @sim_om = @sim_st; use Benchmark 'cmpthese'; my $count = shift || -1; cmpthese $count, { sort_with_st => \&sort_st, sort_with_om => \&sort_om, }; sub sort_st { my @sim = @sim_st; my @sorted = map { $_->[0] } map { my $i = 0; sort { $b->[1] <=> $a->[1] } map { [$i++, $_] } splice (@sim, 0, 9) } 0..8; } use constant { M => 9, N => 9 }; sub sort_om { my @index_sorted; for my $m (0..(M-1)) { my $ix0 = $m * N; push @index_sorted, sort { $sim_om[$ix0 + $b] <=> $sim_om[$ix0 + $a] } 0..(N-1); } }
      And here is the benchmark, kinda speaks for itself:
      $ perl benchmark-sort.pl Rate sort_with_st sort_with_om sort_with_st 3011/s -- -61% sort_with_om 7724/s 156% --
      Thanks and ++ goes to shmem and salva for the lessons.

      Open source softwares? Share and enjoy. Make profit from them if you can. Yet, share and enjoy!

Re: Sorting Index of An Array
by BrowserUk (Pope) on May 14, 2007 at 10:04 UTC

    Unless I'm being dense (quite possible), I think that you are going to have to explain what you mean by

    ... the index is sorted decreasingly according to similarity value in @sim.

    because I can see no corrolation between the values in those two arrays?

    The identical values (1.0) along the main (tl/br) diagonal are mapped to 5 different values (0,1,2,5,8) in the result? You have 9 "indexes" (0..8) in the result, and there are 9 unique values in the input which seems to indicate something, but how the same value in the input results in different indexes in the output completely eludes me.

    I'm guessing that the "according to similarity value" is the key, but it's going right over my head at the moment?


    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: Sorting Index of An Array
by Anonymous Monk on Jul 15, 2008 at 11:43 UTC
    Hello, I found this code, algorithm and examples very useful and ultimate. Can I get c++ for the same? Thanks and Regards, Pradnya

Log In?
Username:
Password:

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

How do I use this? | Other CB clients
Other Users?
Others exploiting the Monastery: (7)
As of 2021-06-22 18:01 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?
    What does the "s" stand for in "perls"? (Whence perls)












    Results (108 votes). Check out past polls.

    Notices?