Beefy Boxes and Bandwidth Generously Provided by pair Networks
Perl Monk, Perl Meditation
 
PerlMonks  

Re: Array vs. Hash for sparsely integer-indexed data

by Anonymous Monk
on Jan 25, 2013 at 20:23 UTC ( #1015401=note: print w/ replies, xml ) Need Help??


in reply to Array vs. Hash for sparsely integer-indexed data

Also not to be excluded entirely is ... uhh ... an array of integers that is searched sequentially each time. Seriously. If you've got say 10,000 integers to look through, they're gonna take up 40K bytes. All sitting in memory all the time. You could loop through that. You could even loop through 10 times that and still be, well, okay. I'd suggest estimating how many unique values you're going to have, and set up a few short test-runs with randomly generated data to get a feel for how the various alternatives pan out. Then just pick one and go.


Comment on Re: Array vs. Hash for sparsely integer-indexed data
Re^2: Array vs. Hash for sparsely integer-indexed data
by BrowserUk (Pope) on Jan 25, 2013 at 21:48 UTC
    Also not to be excluded entirely is ... uhh ... an array of integers that is searched sequentially each time.

    That is a surprise winner for my 'Worst Advice of the Month (January, 2013)' prize.

    ... set up a few short test-runs ...

    I'd suggest you take your own advice before doling it out to others.

    NB: The following uses 1/10 the number of values and 1/10 the number of lookups than the tests above for arrays, hashes and bit vectors, because it takes so long to complete.:

    @a = map $_*20, 1 .. 1e4;; say total_size \@a;; 320176 $found=0; say time; for my $tgt ( 1 .. 20e4 ) { $tgt == $_ and ++$foun +d and last for @a; }; say time; say $found;; 1359149323.02034 1359149541.80419 10000

    Using that as the basis for estimation, the total size will be 3.2MB -- 12 times that required by the bitvector solution.

    And the lookups that took hashes 1 second; arrays 2/5ths of a second and bitvectors 1/3rd of a second; would take: 25 days!

    It is really hard to see any circumstance when this would be a viable solution.


    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.

Log In?
Username:
Password:

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

How do I use this? | Other CB clients
Other Users?
Others wandering the Monastery: (8)
As of 2014-12-26 19:35 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    Is guessing a good strategy for surviving in the IT business?





    Results (174 votes), past polls