Re: 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

Replies are listed 'Best First'.
Re^2: Array vs. Hash for sparsely integer-indexed data by BrowserUk (Patriarch) 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` [download] 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.	[reply] [d/l]

Replies are listed 'Best First'.

Re^2: Array vs. Hash for sparsely integer-indexed data
by BrowserUk (Patriarch) 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
[download]

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.

[reply]
[d/l]