Beefy Boxes and Bandwidth Generously Provided by pair Networks
Don't ask to ask, just ask

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

by vkon (Curate)
on Dec 24, 2011 at 21:20 UTC ( #945040=note: print w/replies, xml ) Need Help??

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

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()). */

Replies are listed 'Best First'.
Re^6: "Just use a hash": An overworked mantra?
by JavaFan (Canon) on Dec 25, 2011 at 09:58 UTC
    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.
Re^6: "Just use a hash": An overworked mantra?
by BrowserUk (Pope) on Dec 24, 2011 at 22:08 UTC
    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?

Log In?

What's my password?
Create A New User
Node Status?
node history
Node Type: note [id://945040]
[Discipulus]: ah! thanks shmem it works in strawberry 5.24
[shmem]: ah. Introduced in 5.22.0, see perl5220delta
[Discipulus]: if so the previous error is a bit misleading, anyway
[shmem]: well, previous to that << was always treated as the left-shift operator
[Eily]: or the here-doc operator
[Eily]: which is actually how it is parsed in this case
[shmem]: older versions of perl can't guess that "use of <<>> may be implemented someday" :D
Discipulus how much wise my brothers are? ;=)
[karlgoethebier]: thanks ;-

How do I use this? | Other CB clients
Other Users?
Others examining the Monastery: (9)
As of 2017-07-21 09:07 GMT
Find Nodes?
    Voting Booth?
    I came, I saw, I ...

    Results (320 votes). Check out past polls.