Beefy Boxes and Bandwidth Generously Provided by pair Networks
Problems? Is your data what you think it is?
 
PerlMonks  

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

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


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

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!


Comment on Re^4: Iterating through Two Arrays. Is there a better use of memory?
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).

Log In?
Username:
Password:

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

How do I use this? | Other CB clients
Other Users?
Others exploiting the Monastery: (9)
As of 2015-07-07 02:14 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    The top three priorities of my open tasks are (in descending order of likelihood to be worked on) ...









    Results (86 votes), past polls