Sorting Index of An Array

[neversaint]

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.

[shmem]

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.

[salva]

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

[shmem]

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

[salva]

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);
}

[naikonta]

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.

[BrowserUk]

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?

[Anonymous Monk]

Hello, I found this code, algorithm and examples very useful and ultimate. Can I get c++ for the same? Thanks and Regards, Pradnya