Do you know where your variables are? 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??

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?

Replies are listed 'Best First'.
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.

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 studying the Monastery: (6)
As of 2020-10-20 15:46 GMT
Sections?
Information?
Find Nodes?
Leftovers?
Voting Booth?
My favourite web site is:

Results (210 votes). Check out past polls.

Notices?