in reply to Speeding permutation counting

Other monks have already provided excellent optimizations for this particular case. I'd like to add a more modest optimization which applies to your original code and is more generally useful:

Don't make unnecessary comparisons.

In the original implementation, you're making eight comparisons on each pair of characters when you only need two. 

if (${$strings[$i]}[$k]) {
  if (${$strings[$j]}[$k]) {
    $c11++;
  } else {
    $c10++;
  }
} else {
  if (${$strings[$j]}[$k]) {
    $c01++;
  } else {
    $c00++;
  }
}

[download]

Replies are listed 'Best First'.
Re^2: Speeding permutation counting
by ikegami (Patriarch) on Jul 18, 2007 at 16:20 UTC

    I thougth a hash might be faster, but no. 

            Rate hash   if
hash  9329/s   -- -11%
if   10473/s  12%   --

        Rate hash   if
hash  9436/s   -- -11%
if   10599/s  12%   --

        Rate hash   if
hash  9341/s   -- -12%
if   10662/s  14%   --

    [download]

    Benchmark code: 

    use strict;
use warnings;

use Benchmark qw( cmpthese );

use constant INNER => $ARGV[0] || 10000;
use constant OUTER => $ARGV[1] || -3;

my $hash = <<'__EOI__';
   use strict;
   use warnings;
   my @x = our @data;
   my %c;
   while (@x) {
      my $i = shift(@x);
      my $j = shift(@x);
      ++$c{"$i$j"};
   }
__EOI__

my $if = <<'__EOI__';
   use strict;
   use warnings;
   my @x = our @data;
   my ($c00, $c01, $c10, $c11);
   while (@x) {
      my $i = shift(@x);
      my $j = shift(@x);
      if ($i) {
         if ($j) {
            $c11++;
         } else {
            $c10++;
         }
      } else {
         if ($j) {
            $c01++;
         } else {
            $c00++;
         }
      }
   }
__EOI__

our @data = map chr('' . int(rand(2))), 1..INNER;

cmpthese(OUTER, {
   'hash' => $hash,
   'if'   => $if,
});

    [download]

    A hash is definitely cleaner, though.

[reply]
[d/l]
[select]
      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:

      <Reveal this spoiler or all in this thread>
[reply]
[d/l]
[select]

In Section Seekers of Perl Wisdom