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

This is probably the least efficient, yet sane way to do this. I recommend using the elements of the shorter array as the keys of a hash. Then iterate over the longer array, checking whether that element has been seen.

Hash lookups are generally O(1) (if there are few to no collisions), so this reduces your complexity from O(m*n) to O(m+n).

  • Comment on Re: Iterating through Two Arrays. Is there a better use of memory?

Replies are listed 'Best First'.
Re^2: Iterating through Two Arrays. Is there a better use of memory?
by DentArthurDent (Monk) on Oct 13, 2011 at 17:09 UTC
    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!
[reply]

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

[reply]

        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]
        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]

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

[reply]
Re^2: Iterating through Two Arrays. Is there a better use of memory?
by Jeri (Scribe) on Oct 13, 2011 at 16:59 UTC
    Thanks, O(1) couldn't be more perfect.
[reply]
Re^2: Iterating through Two Arrays. Is there a better use of memory?
by Jeri (Scribe) on Oct 13, 2011 at 17:20 UTC

    I need some clarification. What does it mean exactly when "hash keys collide"?

[reply]
[reply]

In Section Seekers of Perl Wisdom