Beefy Boxes and Bandwidth Generously Provided by pair Networks
Perl: the Markov chain saw
 
PerlMonks  

Re^2: Iterating through Two Arrays. Is there a better use of memory?

by DentArthurDent (Monk)
on Oct 13, 2011 at 17:09 UTC ( #931327=note: print w/ replies, xml ) Need Help??


in reply to Re: Iterating through Two Arrays. Is there a better use of memory?
in thread Iterating through Two Arrays. Is there a better use of memory?

Nitpick: O(m+n) where m>n is just O(m). The point is, the operation is of linear order in the larger number of items.
Also, this is computationally O(1), but the original post asks for memory usage, not computation. I'm not a high enough level monk to know what the memory usage of arrays vs. hashes is, but I would hazard a guess that unless you're using an embedded environment or something else with very little available memory, that at 10k items you don't need to care too much about that.

Ben

My mission: To boldy split infinitives that have never been split before!


Comment on Re^2: Iterating through Two Arrays. Is there a better use of memory?
Re^3: Iterating through Two Arrays. Is there a better use of memory?
by Jeri (Scribe) on Oct 13, 2011 at 17:13 UTC

    So, you're saying. If I do just at AR suggested, I will have a linear growth rate instead of an exponential?

      Almost definitely. The worst case scenario with hashes is if every hashed key collides. In that case, you may as well be using an array.

      That's exactly what I'm saying. Your first algorithm has quadratic growth (not exponential). The second algorithm has linear growth. It's a linear cost in the smaller array to load up the hash and then a linear cost in the larger array to do all the look-ups.

      By the way: exponential growth would be O(n^m). Your original algorithm is polynomial, or quadratic to be precise O(n^2).

      Ben
      ----
      My mission: To boldy split infinitives that have never been split before!
        Note that it's only the runtime that's quadratic (or, to be precise, O(n*m)). The memory usage of the algorithm is bounded by O(n+m).
Re^3: Iterating through Two Arrays. Is there a better use of memory?
by Jeri (Scribe) on Oct 13, 2011 at 17:26 UTC

    Thank you. Hopefully, this spring I will take some more comp. math so I can become a somewhat better at growth estimates.

Log In?
Username:
Password:

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

How do I use this? | Other CB clients
Other Users?
Others lurking in the Monastery: (2)
As of 2014-09-22 04:37 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    How do you remember the number of days in each month?











    Results (178 votes), past polls