Beefy Boxes and Bandwidth Generously Provided by pair Networks
good chemistry is complicated,
and a little bit messy -LW
 
PerlMonks  

Re: Hash reference searching

by kyle (Abbot)
on Dec 07, 2009 at 17:18 UTC ( #811563=note: print w/ replies, xml ) Need Help??


in reply to Hash reference searching

This is a lot worse than it could be: exists {%{$HASH_REF}}->{$random_number}.

What that does is dereference the hash %{$HASH_REF} in the context of creating another hash reference { ... }, which is then checked. On every iteration, you copy the whole referenced hash into a new hash reference and then destroy it.

Write it this way instead: exists $HASH_REF->{$random_number}

Update: If I were testing this, I'd probably use Benchmark like so:

use Benchmark qw( cmpthese ); use List::Util qw( shuffle ); my $range = 100000; my $ITERS = 30000; my (%HASH, $HASH_REF); for(my $iter = 1; $iter <= $ITERS; $iter++){ my $random_number = int(rand($range)); $HASH{$random_number} = 1; $HASH_REF->{$random_number} = 1; } my @rand = map { int rand $range } 1 .. $ITERS; my @hits = shuffle keys %HASH; my @miss = grep { ! exists $HASH{$_} } 0 .. $range; cmpthese( -2, { hash_r => sub { map { exists $HASH{$_} } @rand }, ref_r => sub { map { exists $HASH_REF->{$_} } @rand }, hash_h => sub { map { exists $HASH{$_} } @hits }, ref_h => sub { map { exists $HASH_REF->{$_} } @hits }, hash_m => sub { map { exists $HASH{$_} } @miss }, ref_m => sub { map { exists $HASH_REF->{$_} } @miss }, } ); __END__ Rate ref_m hash_m ref_r ref_h hash_r hash_h ref_m 57.8/s -- -10% -56% -58% -59% -61% hash_m 64.2/s 11% -- -51% -54% -54% -56% ref_r 131/s 127% 105% -- -5% -6% -11% ref_h 139/s 140% 117% 6% -- -0% -6% hash_r 140/s 141% 117% 6% 0% -- -5% hash_h 147/s 155% 130% 12% 6% 6% --

This way I test the difference between hits and misses as well as the random chance test you have. From this, it appears that the difference between exists finding or not finding something is a lot bigger than the difference between operating on a hash or a reference to a hash. In fact, I'd say the differences between hashes and references is so small as to be within the margin of error (which I usually think of as 5–10% with Benchmark).

Update 2: Oops! Bad test. I was feeding in far more misses than hits. I should have said:

my @rand = ( map { int rand $range } 1 .. $ITERS )[0 .. $ITERS/2]; my @hits = ( shuffle keys %HASH )[0 .. $ITERS/2]; my @miss = ( grep { ! exists $HASH{$_} } 0 .. $range )[0 .. $ITERS/2];

Then the results are:

Rate ref_h hash_h ref_r ref_m hash_r hash_m ref_h 229/s -- -10% -13% -18% -22% -30% hash_h 254/s 11% -- -3% -9% -14% -22% ref_r 263/s 15% 3% -- -6% -11% -19% ref_m 279/s 22% 10% 6% -- -5% -14% hash_r 295/s 29% 16% 12% 6% -- -10% hash_m 326/s 42% 28% 24% 17% 11% --

Just the opposite of before. Misses are faster than hits. Hashes are faster than references, but not by much.

I might also note: performance testing is hard.


Comment on Re: Hash reference searching
Select or Download Code
Re^2: Hash reference searching
by AnomalousMonk (Monsignor) on Dec 07, 2009 at 20:58 UTC

    A test expression like
        map { exists $HASH{$_} } @rand
    seems to include a lot of superfluous temporary list construction and destruction redundant overhead extraneous activity.

    My approach would be simpler (please forgive a bit of slapdashery):

    >perl -wMstrict -le "use Benchmark qw(cmpthese); my %HASH; my $not_key = 'not_key'; $HASH{ rand() } = 1; compare(); $HASH{ rand() } = 1 for 0 .. 30_000; compare(); sub compare { print '------------------'; print 'hash keys/buckets: ' . %HASH; my ($is_key) = each %HASH; ! exists $HASH{$not_key} or die qq{$not_key should not exist}; exists $HASH{$is_key} or die qq{$is_key should exist}; print qq{test keys '$is_key' and '$not_key' seem ok}; my $HR = \%HASH; cmpthese(-2, { hash_hit => sub { exists $HASH{$is_key} }, hash_miss => sub { exists $HASH{$not_key} }, href_hit => sub { exists $HR->{$is_key} }, href_miss => sub { exists $HR->{$not_key} }, }); } " ------------------ hash keys/buckets: 1/8 test keys '0.408477783203125' and 'not_key' seem ok Rate hash_miss href_miss href_hit hash_hit hash_miss 3305141/s -- -6% -22% -42% href_miss 3520236/s 7% -- -16% -39% href_hit 4215045/s 28% 20% -- -27% hash_hit 5746274/s 74% 63% 36% -- ------------------ hash keys/buckets: 14778/32768 test keys '0.091217041015625' and 'not_key' seem ok Rate href_miss href_hit hash_miss hash_hit href_miss 3392515/s -- -18% -21% -36% href_hit 4126900/s 22% -- -3% -23% hash_miss 4272362/s 26% 4% -- -20% hash_hit 5329295/s 57% 29% 25% --

    Hashes still seem faster than references, but hits seem faster than misses. Overall differences are still not compelling.

    Update: The results above support the notion that hash key lookup (e.g., with exists) is O(1), so the idea of direct or indirect hash lookup being 'faster' might not have much meaning even if the timing differences were more significant.

Log In?
Username:
Password:

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

How do I use this? | Other CB clients
Other Users?
Others musing on the Monastery: (15)
As of 2014-08-28 15:56 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    The best computer themed movie is:











    Results (263 votes), past polls