in reply to Re^2: Speeding permutation counting
in thread Speeding permutation counting

Cool... Guess I should've benchmarked my suggestion instead of just assuming it would be slower than the hash-based ideas.

Actually, unless I've severely mis-benchmarked it, it appears that my modest optimization (combined with blokhead's suggestion of using chop) even outdoes BrowserUK's bitwise version and still more so with fewer lines (based on BrowserUK's test code, I'm comparing every pair of lines): 

100 lines/100 iterations:
          Rate bitwise  ifchop
bitwise 33.1/s      --    -41%
ifchop  56.5/s     71%      --

10 lines/10000 iterations:
          Rate bitwise  ifchop
bitwise 3226/s      --    -57%
ifchop  7463/s    131%      --

1000 lines/5 iterations:
        s/iter bitwise  ifchop
bitwise   3.06      --    -23%
ifchop    2.37     29%      --

[download]
(I actually suspect I'm doing something wrong in my test because I don't see why the number of lines would affect the relative performance at all. Update: I was doing something wrong. I forgot to pull the strings out of the array and was just comparing indexes in my version. With my version fixed to actually do the comparisons, the bitwise version is much faster, as I had initially expected: 
          Rate  ifchop bitwise
ifchop  4.22/s      --    -87%
bitwise 33.3/s    690%      --

[download]
)

Benchmark code: 

#!/usr/bin/perl -w
use strict;
use Benchmark qw(cmpthese);

our $S ||= 1;
our $B ||= 32;
our $N ||= 100;

srand( 1 );

our @strings = map {
    unpack 'b'. $B, rand( 2**32 )
} 1 .. $N;

my $bitwise = <<'EOBW';
our @strings;
my ($c00, $c01, $c10, $c11) = (0, 0, 0, 0);
for my $i ( 0 .. $#strings ) {
    for my $j ( $i+1 .. $#strings ) {
            $c00 = (  $strings[ $i ] |  $strings[ $j ] ) =~ tr[0][0];
            $c01 = ( ~$strings[ $i ] &  $strings[ $j ] ) =~ tr[\1][\1]
+;
            $c10 = (  $strings[ $i ] & ~$strings[ $j ] ) =~ tr[\1][\1]
+;
            $c11 = (  $strings[ $i ] &  $strings[ $j ] ) =~ tr[1][1];
    }
}
EOBW

my $ifchop = <<'EOIFC';
our @strings;
my ($c00, $c01, $c10, $c11) = (0, 0, 0, 0); 
for my $i ( 0 .. $#strings ) {
  for my $j ( $i+1 .. $#strings ) {
    # Need copies because chop is destructive
    # Oops... my $test_str_1 = $i;
    # my $test_str_2 = $j;
    my $test_str_1 = $strings[$i];
    my $test_str_2 = $strings[$j];

    while ($test_str_1) {
      my $x = chop $test_str_1;
      my $y = chop $test_str_2;
      if ($x) {
        if ($y) {
          $c11++;
        } else {
          $c10++;
        }
      } else {
        if ($y) {
          $c01++;
        } else {
          $c00++;
        }
      }
    }
  } 
}
EOIFC

cmpthese(100,
         { bitwise => $bitwise,
           ifchop  => $ifchop,
         });

[download]

In Section Seekers of Perl Wisdom