Beefy Boxes and Bandwidth Generously Provided by pair Networks
We don't bite newbies here... much
 
PerlMonks  

Re^2: Ultra compact set searching

by jimt (Chaplain)
on Nov 22, 2006 at 18:34 UTC ( #585590=note: print w/ replies, xml ) Need Help??


in reply to Re: Ultra compact set searching
in thread Ultra compact set searching

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.


Comment on Re^2: Ultra compact set searching
Select or Download Code

Log In?
Username:
Password:

What's my password?
Create A New User
Node Status?
node history
Node Type: note [id://585590]
help
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others browsing the Monastery: (6)
As of 2015-07-08 00:58 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    The top three priorities of my open tasks are (in descending order of likelihood to be worked on) ...









    Results (93 votes), past polls