in reply to Comparing two arrays

How about turning the arrays into strings and then using boolean & on them, using tr to count the 1s? 

my @x = qw( 0 0 0 0 1 1 0 0 0 0 1 0 );
my @y = qw( 1 0 0 0 1 0 1 0 1 0 1 0 );

my $x = join '', @x;
my $y = join '', @y;

my $compare = $x & $y;
my $joint = $compare =~ tr/1/1/;
print "$joint\n";

[download]

Can you throw this into your benchmarking? @x obviously would need to be turned into a string only once.

Replies are listed 'Best First'.
Re^2: Comparing two arrays
by baxy77bax (Deacon) on Dec 15, 2013 at 11:04 UTC
    Hi, thank you making a suggestion. Correct me if I'm wrong but if i turn array into string what i am basically doing is creating a character array (1 byte per character ) boolean & will then rewrite my two arrays into one consensus array which means number of computational steps that equal to the size of the smaller array(best case). but shouldn't that be slower then doing: the number of random access array checkups that equal to the total number of 1's in y array (which is ca. 500 times smaller then the size of smaller array (between the two)). It would definitely reduce my memory but don't see how would this increase speed. Basically what you are suggesting is equal to converting my arrays into bit-arrays and then computing the intersect. And i truly don't see why would this be faster. could someone maybe discuss this approach with me a bit further before i start creating bit/character arrays.

    Thank you so much for engaging the conversation (++)

[reply]

      You are right. See the following benchmarks: 

      use strict;
use warnings;
use Benchmark 'cmpthese';

sub create { map {rand() < $_[1] ? 1 : 0} 1..$_[0] }

sub compare1 { # naive
  my $x = shift;
  my $n = shift;
  return map { my $y=$_; scalar grep { $y->[$_] == 1 and $x->[$_] == 1
+ } 0..$n-1 } @_;
}

sub compare2 { # first find 1s in x, then check in ys
  my $x = shift;
  my $n = shift;
  my @nxs = grep { $x->[$_] } 0..$n-1;
  return map { my $y=$_; scalar grep { $y->[$_] == 1 } @nxs } @_ ;
}

sub compare3 { # stringify
  my $x = shift;
  $x = join '', @$x;
  return map { my $j = $x & join'',@$_; $j =~ tr/1/1/ } @_;
}

my $n  = 15000;
my $p  = 0.005;
my $ny = 10;
my @x = create $n, $p;
my @ys = map { [ create $n, $p ] } 1..$ny;

my @r1 = compare1 \@x, $n, @ys;
my @r2 = compare2 \@x, $n, @ys;
my @r3 = compare3 \@x, @ys;
print "compare1: @r1\n";
print "compare2: @r2\n";
print "compare3: @r3\n";

cmpthese( -5, { compare1 => sub{ compare1 \@x, $n, @ys },
                compare2 => sub{ compare2 \@x, $n, @ys },
                compare3 => sub{ compare3 \@x, @ys },
              }
        );

      [download]
      Results: 
                 Rate compare1 compare3 compare2
compare1 48.8/s       --     -81%     -91%
compare3  253/s     420%       --     -53%
compare2  537/s    1002%     112%       --

      [download]
[reply]
[d/l]
[select]

In Section Seekers of Perl Wisdom