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

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

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

use List::Util qw{ first };
use Test::More;
use Benchmark qw{ cmpthese };

my @haystack = 1 .. 1_000_000;
my $needle = 999_000;

sub frst {
    my $w = shift;
    first { $haystack[$_] == $w } 0 .. $#haystack
}

sub loop {
    my $w = shift;
    for my $i (0 .. $#haystack) {
        return $i if $haystack[$i] == $w;
    }
}

{   my %h;
    sub hash {
        my $w = shift;
        @h{@haystack} = 0 .. $#haystack unless %h; # This could go out
+side the sub, too.
        $h{$w}
    }
}


cmpthese(-3,
         { frst => sub { frst($needle) },
           loop => sub { loop($needle) },
           hash => sub { hash($needle) },
         });

is(frst($needle), loop($needle), 'first == loop');
is(frst($needle), hash($needle), 'first == hash');
done_testing(2);
[download]

          Rate      frst      loop      hash
frst    19.6/s        --       -3%     -100%
loop    20.2/s        3%        --     -100%
hash 4074780/s 20814138% 20170060%        --
[download]

لսႽ† ᥲᥒ⚪⟊Ⴙᘓᖇ Ꮅᘓᖇ⎱ Ⴙᥲ𝇋ƙᘓᖇ

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

Replies are listed 'Best First'.
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]

Replies are listed 'Best First'.

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]