Beefy Boxes and Bandwidth Generously Provided by pair Networks
go ahead... be a heretic
 
PerlMonks  

Re^4: "Just use a hash": An overworked mantra?

by BrowserUk (Pope)
on Dec 23, 2011 at 21:34 UTC ( #944993=note: print w/ replies, xml ) Need Help??


in reply to Re^3: "Just use a hash": An overworked mantra?
in thread "Just use a hash": An overworked mantra?

real-life alhorithms are O(log N) in best case, but I afraid Perl's one is worse than that

I'd like to see you demonstrate that Perl's hashes are O(log N), let alone "worse than that"?


With the rise and rise of 'Social' network sites: 'Computers are making people easier to use everyday'
Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error.
"Science is about questioning the status quo. Questioning authority".
In the absence of evidence, opinion is indistinguishable from prejudice.

The start of some sanity?


Comment on Re^4: "Just use a hash": An overworked mantra?
Re^5: "Just use a hash": An overworked mantra?
by vkon (Deacon) on Dec 24, 2011 at 21:20 UTC
    yes, they are O(n x log n)

    how do the hashes work.

    ok, hash is computed (some say these are O(log n) i do not know but this time I trust the links provided to me by davido) and then - based on computed hash - it could be hash hit or miss: either "luck" - (this is what usually happens) - this was different on all previous values.
    or - otherwise - hash sum equality with earlier cases of that hash (rare in practice, but this is what is used on hash complexity attack)

    in that latter case - insertion/search happens (based on exact operation), which is O(n)

    otherwise this hunk of hv.c code is what for:

    * The "hash seed" feature was added in Perl 5.8.1 to perturb the resu +lts * to avoid "algorithmic complexity attacks". * * If USE_HASH_SEED is defined, hash randomisation is done by default * If USE_HASH_SEED_EXPLICIT is defined, hash randomisation is done * only if the environment variable PERL_HASH_SEED is set. * For maximal control, one can define PERL_HASH_SEED. * (see also perl.c:perl_parse()). */
      I'd like to see you demonstrate that Perl's hashes are O(log N), let alone "worse than that"

      That is not a demonstration.

      Just you expounding your own theory based upon your misunderstanding of a) what you've read; b) what O(N) & O(N log N) mean.

      Merry Xmas. :)


      With the rise and rise of 'Social' network sites: 'Computers are making people easier to use everyday'
      Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error.
      "Science is about questioning the status quo. Questioning authority".
      In the absence of evidence, opinion is indistinguishable from prejudice.

      The start of some sanity?

      Even if you manage to construct an insert sequence that, with a particular hash seed, results in Ω(N2) time to insert N keys, that still doesn't prove insertion isn't O(1) amortized time, with the amortization taken over all insert sequences, and/or all hash seeds.

Log In?
Username:
Password:

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

How do I use this? | Other CB clients
Other Users?
Others rifling through the Monastery: (11)
As of 2014-07-26 07:21 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    My favorite superfluous repetitious redundant duplicative phrase is:









    Results (175 votes), past polls