Re: Ultra compact set searching

[radiantmatrix]

I can't see your and_maker, but based on its interface, I'm guessing you're actually building a sub. I suppose that works, but instead, what about:

sub multi_and {
   my $result = shift;
   while (@_) { $result &= shift; }
   $result;
}

That might be used like:

my $results1 = multi_and(1,2,3);             # 3 args
my $results2 = multi_and(5,6,7);             # 3 args
my $results3 = multi_and(12,13,14,15,16);    # 5 args

No code generation, should be pretty fast. If the repeated shift is a problem, then this should work, too:

sub multi_and {
  my $result = shift;
  for (@_) { $result &= $_ }
  $result
}

[jimt]

I'll give you one very good reason to build the sub - performance.

The whole point of building the sub is not to do any iterating. You build the sub with a set number of arguments, then you don't need to loop. As I'd said, performance is twitchy, but for my test cases, it blew the iterative multi_and out of the water.

#!/usr/bin/perl

use Benchmark;

sub multi_and {
  my $result = shift;
  for (@_) { $result &= $_ }
  $result
}

my %dispatch = ();
sub and_maker {

    my $num_args = shift;

    return $dispatch{$num_args} if $dispatch{$num_args};

    my $built = join '&', map {'$_[' . $_ . ']'} (0..$num_args - 1);
    return $dispatch{$num_args} = eval "sub { $built }";
}

# I'll go ahead and pre-cache these
my $and_maker_5 = and_maker(5);
my $and_maker_50 = and_maker(50);
my $and_maker_500 = and_maker(500);
my $and_maker_5000 = and_maker(5000);
my $and_maker_50000 = and_maker(50000);

my @list_5 = (1..5);
my @list_50 = (1..50);
my @list_500 = (1..500);
my @list_5000 = (1..5000);
my @list_50000 = (1..50000);

timethese(1000000, {
  'and_maker 5 elements' => sub {
    $and_maker_5->(@list_5);
  },
  'multi_and 5 elements' => sub {
    multi_and(@list_5);
  },
});
print "----\n";
timethese(100000, {
  'and_maker 50 elements' => sub {
    $and_maker_50->(@list_50);
  },
  'multi_and 50 elements' => sub {
    multi_and(@list_50);
  },
});
print "----\n";
timethese(10000, {
  'and_maker 500 elements' => sub {
    $and_maker_500->(@list_500);
  },
  'multi_and 500 elements' => sub {
    multi_and(@list_500);
  },
});
print "----\n";
timethese(1000, {
  'and_maker 5000 elements' => sub {
    $and_maker_5000->(@list_5000);
  },
  'multi_and 5000 elemets' => sub {
    multi_and(@list_5000);
  },
});
print "----\n";
timethese(100, {
  'and_maker 50000 elements' => sub {
    $and_maker_50000->(@list_50000);
  },
  'multi_and 50000 elemets' => sub {
    multi_and(@list_50000);
  },
});

And the results:

Benchmark: timing 1000000 iterations of and_maker 5 elements, multi_an
+d 5 elements...
and_maker 5 elements:  0 wallclock secs ( 0.95 usr +  0.00 sys =  0.95
+ CPU) @ 1052631.58/s (n=1000000)
multi_and 5 elements:  2 wallclock secs ( 2.33 usr +  0.01 sys =  2.34
+ CPU) @ 427350.43/s (n=1000000)
----
Benchmark: timing 100000 iterations of and_maker 50 elements, multi_an
+d 50 elements...
and_maker 50 elements:  0 wallclock secs ( 0.47 usr +  0.00 sys =  0.4
+7 CPU) @ 212765.96/s (n=100000)
multi_and 50 elements:  1 wallclock secs ( 1.06 usr +  0.01 sys =  1.0
+7 CPU) @ 93457.94/s (n=100000)
----
Benchmark: timing 10000 iterations of and_maker 500 elements, multi_an
+d 500 elements...
and_maker 500 elements:  1 wallclock secs ( 0.68 usr +  0.00 sys =  0.
+68 CPU) @ 14705.88/s (n=10000)
multi_and 500 elements:  1 wallclock secs ( 0.94 usr +  0.00 sys =  0.
+94 CPU) @ 10638.30/s (n=10000)
----
Benchmark: timing 1000 iterations of and_maker 5000 elements, multi_an
+d 5000 elemets...
and_maker 5000 elements:  1 wallclock secs ( 0.87 usr +  0.00 sys =  0
+.87 CPU) @ 1149.43/s (n=1000)
multi_and 5000 elemets:  1 wallclock secs ( 0.94 usr +  0.00 sys =  0.
+94 CPU) @ 1063.83/s (n=1000)
----
Benchmark: timing 100 iterations of and_maker 50000 elements, multi_an
+d 50000 elemets...
and_maker 50000 elements:  1 wallclock secs ( 0.97 usr +  0.01 sys =  
+0.98 CPU) @ 102.04/s (n=100)
multi_and 50000 elemets:  1 wallclock secs ( 0.96 usr +  0.00 sys =  0
+.96 CPU) @ 104.17/s (n=100)

The iterative multi_and didn't overtake it until I reached a list with 50,000 elements. Performance may vary with the elements in the list, though, I suppose. You may be able to improve performance by having it bow if it &s down to 0, but the added overhead of the conditional may negate the improvement on average.