The following is a slight modification of your program.
It (ab)uses the fact that Perl only checks whether to split
buckets when you use a new bucket. It does not make any
assumptions about Perl's hashing algorithm. It is
therefore able to generate the special keys much more
quickly than yours does.
my $HOW_MANY = shift || 100_000;
my ($s, $e1, $e2);
$s = time;
for ($i=0; $i<$HOW_MANY; $i++) {
$q{$i}=1;
}
$e1 = time - $s;
print qq{
Normally, it takes me about $e1 second(s) to put $HOW_MANY items into
+a
hash. Now I'm going to construct $HOW_MANY special keys and see
how long it takes to put those into a hash instead.
};
undef %q;
print "Generating $HOW_MANY keys\n";
my @keys;
my $i = 0;
while (@keys < $HOW_MANY) {
$i++;
my %hash = (0 => 0, $i => 0);
if (%hash =~ /1/) {
# Goes in the same bucket as 0
push @keys, $i;
}
}
print "Putting the $HOW_MANY special keys into the hash.\n";
$i = 0;
$lasttime = $s = time;
foreach $key (@keys) {
$h{$key} = 1;
$i++;
if (time() - $lasttime > 5) {
my $h = %h + 0;
print "I have put $i keys into the hash, using $h bucket(s)\n" ;
$lasttime = time;
}
}
$e2 = time - $s;
print qq{
The $HOW_MANY special keys took $e2 seconds to put into the hash,
instead of $e1 seconds.
};
Update: (Much later.) Perl changed when it splits buckets so this program no longer runs slowly. Furthermore Perl's hashing algorithm is now random, so Dominus' program no longer runs slowly. Shucks. |