Based on a comment I received to my first post, I have decided to radically change the topic. So today I am making a post on looping. It is a generally accepted fact that looping is one of the first concepts that a programmer is supposed to learn. However, it only occurred to me a few months ago that it might negatively affect both the efficency and the clarity of the code.
In industrial programming one barely uses for loops, which might be a consequence of both the OOP philosophy applied to larger projects and of the small number of objects handled at a time. During my 12-week intership at Microsoft I believe I wrote less than 10 for loops.
On the other hand, while I was learning problem-solving in highschool, around 99 out of a 100 problems required using at least one for loop. This happend for the following reasons:
- Solving in O(n) – the solution is hard to imagine, instead of O(n^2) – child’s play makes a big difference. In many cases it’s not a challenge to solve the problem itself, but to solve it with as small a number of operations as possible. And one can only validate this by running programs with large arrays as input.
- One of the highly-tested abilities in competitions is solving dynamic programming problems, which deal with recurring states. You can ideally implement this by using function calls. Memoization can help save time (memorizing results if they are computed several times), but for one who doesn’t know anything about recursion yet, it’s simpler to come up with a rule to compute the results in the order in which they are needed (from bottom to top), which implies iterations and for loops. Quora DP question
- Another competitive programming topic is data structures. Testing how innovative you are in this respect can only be done if the problem solution requires at least a slightly different data structure design from the well-known ones (variations of stacks, queues, dequeues, self-balancing binary trees, binary indexed trees, segment trees and k-d trees). Because of the fact that it’s hard and expensive to adapt these variations to the data structures from the standard libraries, the competitor has to explicitly write the methods for iterating and searching through the data structure.
So for me it has become a reflex to iterate explicitly. But after having gone through Andrew Ng’s Machine Learning course (the lecture on Vectorization), I found out about how numerical methods and parallelization can speed up operations that are abstracted in linear algebra (matrix multiplications, dot products, etc.). Numpy (Numerical Python) is one of the libraries for scientific computing and linear algebra in Python. OpenCV uses Numpy in order to abstract images into numbers, so using methods from Numpy instead of looping through rows and columns explicitly should be more efficient because these methods are written by experts in the field with optimization in mind.