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 n². 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.