I'm just curious ... why are you using a hash? Hashes are great for string-based indexes or for sparse arrays. But here we have a contiguous array from 1 to 20,000. An array would not only be smaller, but faster. Lots faster. Even with your hash, we could get a bit more out of looping less. In your print, I'm not sure why you grep from the map. You could easily combine them as:
print join(', ', map { $lights{ $_ } ? $_ : () }
( 1..20_000)
)."\n";
Even that is sub-optimal. After all, you want the original number - so you could just grep it out. I've put it as duckyd2 in my benchmark. And, for good measure, I've also added tanktalus as just the rewrite to use arrays.
#!/usr/bin/perl
use strict;
use warnings;
use Benchmark qw(cmpthese);
my $duckyd_answer;
sub duckyd {
my %lights = map { $_ => 1 } ( 1..20_000 );
foreach my $flipper ( 2..20_000) {
for( my $i = $flipper; $i <= 20_000; $i += $flipper ){
$lights{ $i } = !$lights{ $i };
}
}
$duckyd_answer = join(', ', grep { defined $_ }
map { $lights{ $_ } ? $_ : undef }
( 1..20_000)
);
}
my $duckyd2_answer;
sub duckyd2 {
my %lights = map { $_ => 1 } ( 1..20_000 );
foreach my $flipper ( 2..20_000) {
for( my $i = $flipper; $i <= 20_000; $i += $flipper ){
$lights{ $i } = !$lights{ $i };
}
}
$duckyd2_answer = join(', ', grep { $lights{ $_ } }
( 1..20_000)
);
}
my $tanktalus_answer;
sub tanktalus {
my @lights = (1) x 20_000;
foreach my $flipper ( 2..20_000) {
for( my $i = $flipper; $i <= 20_000; $i += $flipper ){
$lights[$i-1] = !$lights[$i-1];
}
}
$tanktalus_answer = join(', ', grep { $lights[$_-1] } 1..20_000);
}
cmpthese(-1,
{
duckyd => \&duckyd,
duckyd2 => \&duckyd2,
tanktalus => \&tanktalus,
},
);
print "duckyd answer: $duckyd_answer\n";
print "duckyd2 answer: $duckyd2_answer\n";
print "tankalus answer: $tanktalus_answer\n";
And the results on this machine:
Rate duckyd duckyd2 tanktalus
duckyd 47.3/s -- -1% -44%
duckyd2 47.7/s 1% -- -44%
tanktalus 84.6/s 79% 77% --
(I've removed the answers as they're all the same.) The 1% speed benefit of duckyd2 over duckyd is purely the removal of the map in the output string - mostly ignorable, I grant, as it's still O(n) vs the O(n^2) algorithm right before it. As you can see, arrays are significantly faster than hashes for this. Still O(n^2), but the constant is reduced ;-)