What Type of Loop Should I Use?
In a blog post I wrote in January, Why are for loops in IDL so slow?, I discussed ways to make a loop more efficient in IDL and other programming languages. The article referred specifically to For loops, but its principles could be applied to any type of loop in IDL. This leads to the question: Are some loops better than others for certain situations, and if so, what is the best loop to use?
The truth is that there is usually more than one way to solve a problem, and almost every programming problem that needs to make use of a loop could be solved with more than one type of loop. Given the concern of efficiency, there are pros and cons to each type.
Here is a description of each type of loop, along with some pros, cons, and comparisons:
For
The for loop is probably the most common and well known type of loop in any programming language.
For can be used to iterate through the elements of an array:
For can also be used to perform a fixed number of iterations:
By default the increment is one. You can also iterate by a given increment, which is specified as the third argument. The increment can even be negative.
Pros:
- In a for loop, the index of iteration is always a clearly defined variable. By common practice, the variable is usually the letter i. This makes it easy to index one or more arrays by the index.
- For loops can easily be used to iterate through elements of multidimensional arrays using nested for loops. By common practice, the next loop would use the variable j, then k, etc.
Cons:
- To use a for loop, it is necessary to know the length of the array through which the for loop is iterating, or alternatively, the total number of iterations must be known. There are cases where neither of these definite values is known.
- To break out of the loop after a specific condition, you will need to explicitly write a conditional statement with a BREAK statement.
Efficiency:
Given that you are iterating over an array with known length or are known number of iterations, it is very easy to vectorize as well as move as many operations and array-based conditionals as possible outside of the loop.
Foreach
Similar to a for loop, Foreach is used to iterate though a given number of items in the input.
Foreach has the optional argument of the index, in case it is needed.
Pros:
- The foreach loop is particularly convenient to a programmer because you don't need to think about the index in times where you don't care about it.
- Foreach has specifically been designed as an operator on IDL's LIST. It works very similarly to using foreach to iterate through an array.
- Even more conveniently, foreach has also been specifically designed as an operator on IDL's HASH. The element in each iteration is the value of the given element. The optional third argument gives you the key for that element.
If you really want, you can iterate through an ordered hash and even define your own index.
Cons:
- Unlike a for loop, a foreach loop cannot be used to perform a fixed number of iterations.
- You can lose efficiency with a foreach loop compared to a plain for loop.
Efficiency, and Foreach vs. For
- A very simple for loop where the array isn't indexed, or where the loop makes a fixed number of iterations, is comparatively quite fast.
% Time elapsed: 0.00099992752 seconds.
- If a variable containing the element at the given index is defined during every iteration of the for loop, then it turns out that using a simple foreach loop takes the exact same amount of time. This is because IDL internally does the exact same thing in a foreach loop.
% Time elapsed: 0.0019998550 seconds.
% Time elapsed: 0.0019998550 seconds.
- However, be warned that if you are going to use the third argument in the foreach statement, you are going to be sacrificing efficiency, and unless you really benefit from its convenience, you should just use a plain for loop instead.
% Time elapsed: 0.0030000210 seconds.
- On the other hand, because foreach has been specifically implemented by the IDL developers as a tool for lists and hashes, foreach is much more efficient for these two objects than a plain for loop.
While
The while loop is used to perform an indefinite number of iterations, as long as a certain condition remains true.
Pros:
- If the number of iterations is not known up front, then this is a case where a for loop can't be used.
- The while loop is quite simple. It contains no indices or defined variables, so it is convenient when a loop is simply needed to keep performing an action until a desired condition is (or isn't) met.
Cons:
- Here is a big warning: When using a while loop, you need to make sure that the condition is actually going to turn false at some point in time. If the condition is always true, then you will end up in an infinite loop.
- A while loop is quite inefficient in IDL (see example below).
Efficiency, and While vs For
When iterating through an array, here is a comparison of For vs. While:
Using for: % Time elapsed: 0.0010001659 seconds.
Using while: % Time elapsed: 0.026000023 seconds.
The main reason that While is much slower is because the while loop checks the condition after each iteration, so if you are going to write this code, just use a for loop instead.
If you perform one or more conditional checks in a For loop, however, and these checks would not be needed if you used a While loop, then you may consider the While option with an index that is manually incremented with the ++ operator.
Repeat
The repeat loop is very similar to the while loop in that it performs an indefinite number of iterations. The differences between while and repeat are 1.) Repeat does not need a condition at the start, 2.) Repeat keeps iterating until a condition is false, whereas a while loop is the opposite.
Pros:
- It turns out that Repeat is actually quite a bit more efficient than While, demonstrated below.
- Repeat may have the convenience that in many situations, the condition is not known or even defined until inside the loop. For this reason, while loops often need the condition set to a dummy state, which must evaluate to true.
Cons:
- Just like with a while loop, it is possible to end up in an infinite loop, so it is very important to make sure the end condition will always be met eventually.
- If the condition prior to the loop actually does matter (i.e. if you want to skip the loop entirely given a certain condition), then a while loop might be more convenient. However, the easy way around this is to simply put the entire loop inside a conditional statement.
Efficiency, and Repeat vs. While
Using while: % Time elapsed: 0.026000023 seconds.
Using repeat: % Time elapsed: 0.016000032 seconds.
Therefore, in this basic example, a Repeat loop is the better choice. However, if you find yourself needing to place conditional checks somewhere within the loop, which could be avoided by using the other type of conditional loop, then you might end up with better performance if you use the one with fewer total conditional checks.
Important note
IDL is an interpreted language, which means that IDL's interpreter compiles the user-written code into machine-language. Therefore, many of the performance differences described here are based on how IDL interprets each line of code. Other languages might have completely different behavior, and consequently, the best choice for the type of loop in IDL might not be the best choice in another language.
In Conclusion
Every scenario is different, so every time you start writing a loop, it's important to consider what type of loop is best. Maybe in one situation, you just want to use what is most convenient, but if you are processing large amounts of data, then performance might be critical.
Which loop you choose is ultimately up to you. Just remember that because every scenario is different, what works in one situation may not always work best in others. In other words, these ideas are only rules-of-thumb, but hopefully they can help you get started on the decision.
If you're unsure of what might be faster in a given situation, remember that you can always create a sample dataset and use IDL's tic and toc routines to measure the time it takes for code to run.