In my previous post, The Comfort Zone Loop, I discuss my motivation for exploring code vectorization and the advantages it brings along with it. While this might seem like a one-size-fits-all solution to write efficient code, I'm sorry to say that it is not that simple. Granted, in many cases, code vectorization leads to significantly more efficient code. And while there certainly is a template that can be followed, not every kind of loop follows the same path to vectorization and not every kind of loop should be vectorized. However, based on my experience with converting algorithms and code segments into a vectorized solution, I have put together a list of 4 kinds of loops (there certainly are more, but let's start with these) you should definitely consider vectorizing for a more efficient solution.
Manipulating specific elements of a matrix
Applying a function along each column or row of a matrix
Applying an operation on a matrix based on a conditional statement
Applying a function to different subsets of a matrix
Before we dig in, I do want to point out that the vectorized implementations for the relatively simple examples in this post may not necessarily be more efficient that their loop counterparts. However, the purpose of this post is to expose you to the various different ways in which loops can be converted to vectorized solutions, without emphasizing the change in efficiency of the code. Rather, we will explore the trade-offs between the two solutions in future blog posts.
1. Manipulating specific elements of a matrix
Imagine a scenario in which you have created a matrix of values and want to manipulate the elements at certain indices in some way. For instance, you might want to remove entire rows from a matrix, or replace them with another value. You might, instead, want to replace elements at particular (row,column) locations with another value or extract their values for use elsewhere. Instead of creating a loop or nested loop to iterate over each such index, these tasks can be easily achieved through vectorization.
Let's create an example 5x4 matrix, M, from which we would like to extract the values at indices (1,2), (2,3), (3,1), (4,4), and (5,2).
M = [1 2 3 4;...
5 6 7 8;...
9 10 11 12;...
13 14 15 16;...
17 18 19 20];
r = [1 2 3 4 5];
c = [2 3 1 4 2];It may seem intuitive to simply call the corresponding elements of the matrix, M, and store them in a new matrix, S, as follows:
S = M(r,c);However, Matlab will interpret this as you wishing to extract the elements at all column indices in the column array, c, for each of the row indices in row array, r. This would return the following, and is not the intention.
M = [1 2 3 4;...
5 6 7 8;...
9 10 11 12;...
13 14 15 16;...
17 18 19 20];
r = [1 2 3 4 5];
c = [2 3 1 4 2];
M(r,c)ans =
2 3 1 4 2
6 7 5 8 6
10 11 9 12 10
14 15 13 16 14
18 19 17 20 18Rather, you could, of course, use a for-loop to extract the desired elements as follows:
M = [1 2 3 4;...
5 6 7 8;...
9 10 11 12;...
13 14 15 16;...
17 18 19 20];
r = [1 2 3 4 5];
c = [2 3 1 4 2];
for iter = 1:length(r)
S(1,iter) = M(r(iter),c(iter));
end
S
S =
2 7 9 16 18
Instead, you should consider using the built-in functionality to convert the (row, column) pairs to linear indices. Recall that Matlab defines the linear indices of a matrix along each of its columns consecutively as shown below.
From this, we can see that the linear indices of the 5 elements we wish to extract from the matrix, M, are 6, 12, 3, 19, and 10. Matlab can compute these indices for you through the function sub2ind, by passing the size of the matrix, the row indices and the column indices, as follows:
inds = sub2ind(size(M),r,c)inds =
6 12 3 19 10From here, we can extract the desired elements.
M = [1 2 3 4;...
5 6 7 8;...
9 10 11 12;...
13 14 15 16;...
17 18 19 20];
r = [1 2 3 4 5];
c = [2 3 1 4 2];
inds = sub2ind(size(M),r,c);
S = M(inds)
S =
2 7 9 16 182. Applying a function along each column or row of a matrix
One of the most common actions I often find myself needing to perform is to apply a particular function along a certain dimension of a matrix, such as the rows or columns. Luckily, many built-in Matlab functions allow the user to specify the dimension along which to apply the function. For instance, in order to find the minimum value corresponding to each row of a matrix, one could create a for-loop to iterate over each row of the matrix and store the minimum value in an output matrix, S, at each iteration.
M = [1 2 3 4;...
5 6 7 8;...
9 10 11 12;...
13 14 15 16;...
17 18 19 20];
for r = 1:size(M,1)
S(r,1) = min(M(r,:));
end
S
S =
1
5
9
13
17However, rather than creating a loop to compute the minimum value of each row, one can specify a dimension of 2 in Matlab's min function. This will result in the same output matrix, S, as was computed by the for-loop above, but in a more efficient, one-line statement.
M = [1 2 3 4;...
5 6 7 8;...
9 10 11 12;...
13 14 15 16;...
17 18 19 20];
S = min(M,[],2)
S =
1
5
9
13
17Similarly, the following built-in Matlab functions are among the many that allow the user to specify a desired dimension along which to apply said function: min, max, mean, diff, sum, prod, vecnorm, dot, cross, etc.
Of course, you might come across various different scenarios where those built-in functions just don't cut it. You might want to apply a function which does not have built-in dimension functionality, or even apply a custom function, to each row of the matrix instead. In this case, you will need to get a bit more creative and use matrix operations or other built-in Matlab functions such as accumarray, arrayfun, and bsxfun. More on those later!
3. Applying an operation on a matrix based on a conditional statement
Many times, you might find yourself needing to perform operations on those elements of a matrix which satisfy certain conditions. For instance, you might want to replace all elements less than zero with zero, or to extract all elements from a matrix which are between two values. Rather than using a loop or nested loops to iterate over all elements and perform the comparison using an if-statement, Matlab allows the user to apply a conditional statement to a matrix as a whole.
For example, using nested loops, one could implement the following to extract all elements in a matrix, M, which are between 5 and 15, not inclusive:
M = [1 2 3 4;...
5 6 7 8;...
9 10 11 12;...
13 14 15 16;...
17 18 19 20];
S = [];
for c = 1:size(M,2)
for r = 1:size(M,1)
if M(r,c) > 5 && M(r,c) < 15
S(end+1,1) = M(r,c);
end
end
end
S
S =
9
13
6
10
14
7
11
8
12The same functionality can be implemented using the logical output of a conditional statement as follows:
M = [1 2 3 4;...
5 6 7 8;...
9 10 11 12;...
13 14 15 16;...
17 18 19 20];
S = M(M>5 & M<15)
S =
9
13
6
10
14
7
11
8
12In the background, Matlab will generate a logical matrix, L, corresponding to the indices of the input matrix, M, which match the conditional statement "M>5 & M<15", and then return the values of the input matrix, M, for which the value in the logical matrix, L, is true.
4. Applying a function to different subsets of a matrix
Finally, you might come across a situation where you would like to apply a function to certain subsets of a matrix. Out of the 4 scenarios discussed here, this one is often the most difficult to imagine without a for-loop.
Let's consider an example where we start with a 1x100 input matrix, M, and would like to find the sum of the following elements: 1-10, 11-30, 31-60, and 61-100. First, we could write this by evaluating the minimum of the matrix, M, at each of the intervals by brute force.
M = 1:100;
S(1) = min(M(1:10));
S(2) = min(M(11:30));
S(3) = min(M(31:60));
S(4) = min(M(61:100));
S
S =
1 11 31 61
However, as you can imagine, when there are many intervals to evaluate, this will quickly become a tiresome and inefficient process. Instead, we could write this as a for-loop to automate this process.
M = 1:100;
I = [0,10,30,60,100];
S = zeros(1,4);
min_val = Inf;
min_ind = 2;
for iter = 1:length(M)
if iter == I(min_ind)
S(min_ind-1) = min_val;
min_ind = min_ind+1;
min_val = Inf;
elseif iter>I(min_ind-1) && iter<I(min_ind) && M(iter)<min_val
min_val = M(iter);
end
end
S
S =
1 11 31 61
Though, once again, as the length of M increases, the execution time of such an algorithm will become increasingly slow and inefficient. Rather, we can use a few built-in functions to achieve the same result. For instance, we can use accumarray to apply the function min to all elements of the matrix, M, which correspond to the same group indicated by a variable called "sub". In order to use this functionality, though, we need to first create the "sub" array by using Matlab's repelem to repeat the numbers 1 through 4 by the corresponding amount of times for each of the 4 groups of numbers for which we wish to find the minimum value. Hence, we would repeat the number "1" 10 times, the number "2" 20 times, the number "3" 30 times, and the number "4" 40 times. Once we have indicated the group to which each element in the matrix, M, belongs, we can use accumarray to find the minimum value of each group and store it in the output matrix, S.
M = (1:100)';
I = [10,30,60,100]';
I_all = repelem((1:length(I))',[I(1);diff(I)],1);
S = accumarray(I_all,M,[],@min)'
S =
1 11 31 61While the 4 scenarios covered in this post are certainly not an all-encompassing list, they should give you a good idea on the kinds of loops that can be replaced by their vectorized counterparts. Each vectorized solution can likely be achieved in a number of ways, and you'll see those explored further in other blog posts.
Comments