How do I find the index of a specific array value?

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

<SOLVED!! (not the index lookup but the actual problem from my original example). Reversal is possible with almost no time difference.> I also was looking for a method to do this, preferably the fastest possible. With a relatively small array (256), the use List::Util qw(first); method was actually significantly slower than simply iterating through the array and breaking(last) out once the match was found. In my test example on a 2.5MB (2560000bytes) file doing a sort of Sbox type lookup, the iterating took about 3m45s on my old Atom netbook where as the use List::Util qw(first); method required over 5m. Does anyone know the fastest way to perform these index lookups? A few of the examples shown appear to be basically identical. Hashing an array(did I say that right?) is a concept I am not yet familiar with.

I just tried the index hashing method described in the original post I found info on this as well and on the same file went at a grueling pace...Around 15mins. Is there really no other way to perform this operation faster than simply iterating through the array?

Looks like I solved the timing issue in my posted code by re-ordering the array by it's own values. Fixed code shown below.

#!/usr/bin/env perl
use strict; #use warnings;

my $key="a5e0d57354e5fb898a44a979582536141ca3819d1c457db21e3cdf64bdc90
+01d1903ea7d9814649b2e6edee9674d57a5e47a3b0fcb5dbc8de3181c617c88650a88
+f9ff4a9852538087dabf35a596d657c86715d89701edefee55453302488ec3aae6a53
+20319a13ffbd11eb31a7e5c921421a4728b86523889fa20a44f19c4d4abf302490e39
+b5fa50619a18acf9785b6f1bd55158e1405776fb0ee2f3fa5f56aa828b8c22bd6f4e6
+70c23edefb08add86cc5d3415aaa64a4fcf677d2198f1801d800c6762a84e7b0e1053
+b95c38c94fdd637757c2f0ef5d0c628ddf1e83e4f178a00cefd41f58c3b4c2fa71c5e
+d56bfa6aa321120978fbe6f8dfa7fc2b5f109";
$key=pack('H*',$key);

my @sbase;
for my $i (0..255){$sbase[$i]=chr($i)};

my @sbox=sbox_gen(@sbase);

if ( $ARGV[2] eq "fwd" ) {
    swap(@sbox);
} elsif ( $ARGV[2] eq "rev" ) {
    @sbox=sbox_reindex(@sbox);
    swap(@sbox);
}

sub swap {
my ($n,$infile,$buf,$data,$outfile,$tmp); my @sbox=@_;
open($infile,"<",$ARGV[0]) or die $!; binmode($infile);
open($outfile,">",$ARGV[1]) or die $!; binmode($outfile);
while (($n=sysread $infile,$buf,256)!=0){
    for my $i (0..255) {
        $tmp=ord(substr($buf,$i,1));
        $data.=$sbox[$tmp];
    }
    print $outfile $data;$data="";
}
close($outfile);
close($infile);
}

sub sbox_gen {
my @sbox; my @sary=@_;
for my $i (0..255) {
    my $tmp=ord(substr($key,$i,1))**3;
    $tmp=$tmp%scalar(@sary);
    push @sbox,$sary[$tmp];
    splice(@sary,$tmp,1);
}
return @sbox;
}

sub sbox_reindex {
my @sbox=@_; my @out;
for my $i (0..255) {
    my $a=ord($sbox[$i]);
    $out[$a]=chr($i);
}
return @out;
}
[download]

Timings now:

$ time ./sbox.pl testfile outfile fwd real 0m3.424s user 0m3.330s sys 0m0.073s

$ time ./sbox.pl outfile revfile rev real 0m3.529s user 0m3.413s sys 0m0.083s

$ diff testfile revfile

Comment on How do I find the index of a specific array value? Download Code

Replies are listed 'Best First'.
Re: How do I find the index of a specific array value? by choroba (Cardinal) on Sep 15, 2015 at 09:43 UTC
The difference in speed of a loop and first is usually much smaller than you report. In the code below, it's about 3%. What you get in return, though, is readability. Hashing is useful if you're going to search the same array repeatedly many times. Special care is needed if the values in the original array are not unique (not handled in my example). Read more... (1111 Bytes) `Rate frst loop hash frst 19.6/s -- -3% -100% loop 20.2/s 3% -- -100% hash 4074780/s 20814138% 20170060% --` [download] لսႽ† ᥲᥒ⚪⟊Ⴙᘓᖇ Ꮅᘓᖇ⎱ Ⴙᥲ𝇋ƙᘓᖇ	[reply] [d/l] [select]
Re^2: How do I find the index of a specific array value? by SM177Y (Initiate) on Sep 15, 2015 at 10:01 UTC
Thanks for your reply. I ran my test on this crappy netbook so the differences are a lot more obvious. The array I used has all distinct values and was static. However, in a random order. I just generated bytes 00 to FF using a random hex string I set as a variable, cubing the bytes and performing modulus based on the length of the 00-FF sequence as it was reduced with splice. Basically the forward operation of swapping the input bytes from the binary file with the corresponding bytes from the random ordered array is exponentially faster than performing the reverse operation which requires an index lookup. This was my little test. The commented out lines were from the two methods other than iteration I had tried and timed with Linux's built in time cmd. (the file I generated for the test was randomly generated and divisible by 256bytes just for the test) Times of rev:(fwd operation is a matter of seconds(approx 3-4s) Index hash -> real 17m13.164s user 16m45.100s sys 0m1.027s Find -> real 5m17.808s user 5m10.527s sys 0m0.343s Iteration w/last -> real 3m50.843s user 3m47.683s sys 0m0.303s #!/usr/bin/env perl use strict; #use warnings; use List::Util qw(first); my $key="a5e0d57354e5fb898a44a979582536141ca3819d1c457db21e3cdf64bdc90 +01d1903ea7d9814649b2e6edee9674d57a5e47a3b0fcb5dbc8de3181c617c88650a88 +f9ff4a9852538087dabf35a596d657c86715d89701edefee55453302488ec3aae6a53 +20319a13ffbd11eb31a7e5c921421a4728b86523889fa20a44f19c4d4abf302490e39 +b5fa50619a18acf9785b6f1bd55158e1405776fb0ee2f3fa5f56aa828b8c22bd6f4e6 +70c23edefb08add86cc5d3415aaa64a4fcf677d2198f1801d800c6762a84e7b0e1053 +b95c38c94fdd637757c2f0ef5d0c628ddf1e83e4f178a00cefd41f58c3b4c2fa71c5e +d56bfa6aa321120978fbe6f8dfa7fc2b5f109"; $key=pack('H',$key); my @sbase; for my $i (0..255){$sbase[$i]=chr($i)}; my @sbox=sbox_gen(@sbase); if ( $ARGV[2] eq "fwd" ) { fwd(); } elsif ( $ARGV[2] eq "rev" ) { rev(); } sub fwd { my ($n,$infile,$buf,$data,$outfile,$tmp); open($infile,"<",$ARGV[0]) or die $!; binmode($infile); open($outfile,">",$ARGV[1]) or die $!; binmode($outfile); while (($n=sysread $infile,$buf,256)!=0){ for my $i (0..255) { $tmp=ord(substr($buf,$i,1)); $data.=$sbox[$tmp]; } print $outfile $data;$data=""; } close($outfile); close($infile); } sub rev { my ($n,$infile,$buf,$data,$outfile,$tmp); open($infile,"<",$ARGV[0]) or die $!; binmode($infile); open($outfile,">",$ARGV[1]) or die $!; binmode($outfile); while (($n=sysread $infile,$buf,256)!=0){ for my $i (0..255) { $tmp=substr($buf,$i,1); #my $index=first { $sbox[$_] eq $tmp } 0 .. $#sbox; #$data.=chr($index); for my $j (0..255) { if ($tmp eq $sbox[$j]){$data.=chr($j);last}; } #my %index; #@index{@sbox} = (0..$#sbox); #my $index = $index{$tmp}; #$data.=chr($index); } print $outfile $data;$data=""; } close($outfile); close($infile); } sub sbox_gen { my @sbox; my @sary=@_; for my $i (0..255) { my $tmp=ord(substr($key,$i,1))*3; $tmp=$tmp%scalar(@sary); push @sbox,$sary[$tmp]; splice(@sary,$tmp,1); } return @sbox; } [download]	[reply] [d/l]