Efficiency considerations in loops

it is rare these days to think about efficiency considerations in loops, I mean if an algorithm runs in 0 milliseconds it couldn’t get better could it? Likely not… on a fast machine. Consider however that you write a similar loop structure for a process that is much more computationally intensive. Getting into the habit of ignoring efficiency will have repercussions for instance when you port your algorithm to a mobile device. In for loops this is especially true of the inner portion of nested loops. Therefore an effort should be made to keep computationally intensive operations out of inner loops. Consider the following piece of code:

sum = 0
for i = 1:n
    for j = 1:i
        for k = j:i
            sum = sum + f(i,j) * g(j,k)
        end
    end
end

The problem with this piece of code is that the function f(i,j) is calculated every time the innermost loop is run, yet it has no dependencies with this loop. For instance if the value of n is 100, the innermost loop will execute 171,700 times. The efficiency of this loop will improve if the function f(i,j) is removed from the innermost loop.

sum = 0
for i = 1:n
    for j = 1:i
        fij = f(i,j)
        for k = j:i
            sum = sum + fij * g(j,k)
        end
    end
end

Now for n=100, f(i,j) is only calculated 5050 times. Now this only works if the computation time of f(i,j) is greater than that of g(i,j). If g(j,k) is heavily computationally intensive, then it might be better to rearrange the nested loop hierarchy. For instance in the following re-configuration:

sum = 0
for j = 1:n
    for k = j:n
        Gjk = g(j,k)
        for i = k:n
            sum = sum + f(i,j) * Gjk
        end
    end
end

Now g(j,k) is only calculated 5050 times. This makes sense if the order of f(i,j) is only n versus g(j,k) at . Such small changes may seem trivial on a system with plenty of resources, but on resource constrained devices such as mobile device it may make the difference between an app being successful or not.

 

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s