Beefy Boxes and Bandwidth Generously Provided by pair Networks
Keep It Simple, Stupid
 
PerlMonks  

Re: A short meditation about hash search performance

by Courage (Parson)
on Nov 16, 2003 at 13:27 UTC ( #307461=note: print w/ replies, xml ) Need Help??


in reply to A short meditation about hash search performance

Best search performance could be reached as O(log(N)) by using balanced tree.
You could implement this as a perl module, although this will be much slower than internal implementation O(N).
Also do not forget that adding into search list also counts, and I think adding into a hash would cost O(1)

It is know that commonly used in C library qsort is also O(N*N) in worst case and something like O(N*LOG(N)) in real life.
Also sorting method changed to mergesort in perl-5.8.0 and it was qsort for earlier perls.

Best regards,
Courage, the Cowardly Dog


Comment on Re: A short meditation about hash search performance

Log In?
Username:
Password:

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

How do I use this? | Other CB clients
Other Users?
Others meditating upon the Monastery: (10)
As of 2015-07-06 09:38 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 (71 votes), past polls