Re^2: 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?

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?	[reply]
Re^4: Iterating through Two Arrays. Is there a better use of memory? by AR (Friar) on Oct 13, 2011 at 17:17 UTC
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.	[reply]
Re^4: Iterating through Two Arrays. Is there a better use of memory? by DentArthurDent (Monk) on Oct 13, 2011 at 17:21 UTC
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!	[reply]
Re^5: Iterating through Two Arrays. Is there a better use of memory? by JavaFan (Canon) on Oct 13, 2011 at 20:34 UTC
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)`.	[reply] [d/l] [select]
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.	[reply]