Beefy Boxes and Bandwidth Generously Provided by pair Networks
Pathologically Eclectic Rubbish Lister
 
PerlMonks  

What is the best way to find the key is exists or not in a hash ?

by swaroop (Beadle)
on May 10, 2005 at 10:23 UTC ( #455500=perlquestion: print w/replies, xml ) Need Help??

swaroop has asked for the wisdom of the Perl Monks concerning the following question:

Hi All,

I need to find the key already exists or not. We can use exists $data{keyvalue}. How how efficient it is ? Is there any other method to do this ?

thanks,
Swaroop
  • Comment on What is the best way to find the key is exists or not in a hash ?

Replies are listed 'Best First'.
Re: What is the best way to find the key is exists or not in a hash ?
by Corion (Patriarch) on May 10, 2005 at 10:38 UTC

    You did not state in what circumstances exists is not good enough for you, so in the spirit of TIMTOWTDI I present a reimplementation that might be faster. You might want to use Benchmark to find out the relative performance gain. The function implements the sort reverse keys mechanism, which is why I call it exists_srk.

    %x = (foo=>1,bar=>2,baz=>3); sub exists_srk(\%$){my($h,$k)=@_; map{$_ eq $k?$_:()}(sort reverse key +s %$h)}; print exists_srk(%x,$_) for qw(foo bar baz bat)

    Of course, since you don't tell us anything, it's hard to come up with an optimization for your special case. But if you don't know anything about how exists works, it's hard to tell you anything other than to learn how exists works before looking for a replacement.

    Update: After some discussion in the CB, there came up another method which you should benchmark as well. I call it exists_ggg because it uses grep three times. It relies on the fact that grep steps through the list in order though, so it might not work on a platform where the sequence of items visited by grep is different from the current Perl implementation.

    sub exists_ggg (\%$) { my($h,$k) = @_; my $c; grep { len == len $k } grep /^\Q$k\E/ grep { $c++ == 0 } %$h };

    Update2: If the documentation and the code differ, at least one of them is wrong. In this case, the last map should have been a grep as well. Thanks blazar.

      Out of curiosity: I may be missing something obvious, but why sort reverse? Why map where a grep would be most suited? (Or better, a for loop with an immediate return on a match?

      This was intended to be a joke to the OP, wasn't it?

      If I really were to reimplement exists (along the lines of the proposed sub), I'd probably do something like this:

      sub my_exists (\%$) { my($h,$k)=@_; $_ eq $k and return $_ for keys %$h; undef; }

      Update: I saw your update, and yes, it was a joke... how stupid of me to have even the slightest doubt about it!! But your second proposal should be called "exists_ggm" instead... ;-)

      Given the necessary modification to exists_ggg:

      sub exists_ggg (\%;$) { my($h,$k) = @_; my $c; grep { length == length $k } grep { /\Q$k\E/ } grep { ++$c % 2 } % +$h; }

      Just in case anyone had any doubts regarding the efficency of exists alternatives:

      Rate exists_ggg exists_srk exists exists_ggg 5394/s -- -68% -98% exists_srk 16784/s 211% -- -92% exists 219707/s 3973% 1209% --

      If you're really worried about that 219707-th of a second, you've got bigger problems...

Re: What is the best way to find the key is exists or not in a hash ?
by blazar (Canon) on May 10, 2005 at 10:28 UTC
    It seems to me that you do know the answer to your question. It may be that defined is fine for you. I'd say that exists is the way to go though. I wouldn't be concerned about efficiency for such an atomic statement. Do you have any particular situation in which this may matter?!?
Re: What is the best way to find the key is exists or not in a hash ?
by demerphq (Chancellor) on May 10, 2005 at 11:09 UTC

    It would be really nice if you could tell us what your background is that you come to ask this. Im guessing that your experience is with VB and VBscript where collections are more or less crippled, would that be correct?

    Anyway, to add some detail to the fully warranted sarcasm in this thread ill point out that an existance check on an associative array in perl performs in exactly the same time (possibly faster) as a fetch, and associative array fetches in perl are O(1). This is because the underlying algorithm, Hashing, has amortized O(1) properties in general which basically means its damn fast, in fact because of this and because the word is shorter in perl we call associative arrays "hashes". :-)

    Unless the hash you are doing this check against is actually a tie into some kind of complex data structure that isnt using hashing you arent going to get any faster than the hash lookup that perl does. Oh, well maybe making your keys short will shave a nanosecond or two off the run time but i doubt it would be worth the loss of readability.

    Reword your question with above knowledge integrated and you get the fairly easy to answer question

    is there any mechanism faster than O(1) to do a lookup on a hashed data structure.

    And the answer is NO.

    ---
    $world=~s/war/peace/g

Re: What is the best way to find the key is exists or not in a hash ?
by gellyfish (Monsignor) on May 10, 2005 at 10:30 UTC

    Er, exists is the way to find whether a particular key is in a hash. Please explain why you want to try to do this some other way.

    /J\

Re: What is the best way to find the key is exists or not in a hash ?
by rupesh (Hermit) on May 10, 2005 at 11:07 UTC
Re: What is the best way to find the key is exists or not in a hash ?
by vladdrak (Monk) on May 11, 2005 at 06:10 UTC
    if (grep/^keyvalue$/, keys %data) { print "yes"; } # and if (defined $data{keyvalue}) { print "yes"; } # and if you also are sure there is value data in your hash if ($data{keyvalue}) { print "yes"; }


    -Vlad
      Sorry guys, I just want to know the methods to findout the key is exists or not. I need to process more then 500000 values.

      Thanks for the replys.

      - Swaroop

Log In?
Username:
Password:

What's my password?
Create A New User
Domain Nodelet?
Node Status?
node history
Node Type: perlquestion [id://455500]
Approved by Corion
help
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others imbibing at the Monastery: (3)
As of 2023-03-21 11:20 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?
    Which type of climate do you prefer to live in?






    Results (60 votes). Check out past polls.

    Notices?