CODEWITHSUNDEEP
matlabfor-loopoptimization
BillyJean
BillyJean

Reputation: 1577

Optimize two nested for-loops and if-condition

I have the following piece of code, which runs through two nested for-loops and has an if condition in the middle:

N=1e4;

cond_array = [0:(N/2-1) -N/2+(0:(N/2-1))]/(N);
condition  = 0.1;

arr_one = zeros(N, 1);
arr_two = zeros(N, 1);

for m=1:N
    for k=1:N
        if(abs(cond_array(k)) <= condition)
            arr_one(m)  = arr_one(m)  + m*k;
        else
            arr_two(m)  = arr_two(m)  + m*k;
        end
    end
end

I'd like to optimize this code as I potentially need to use very large N (>1e4) and from my own experience, for-loops in MATLAB are often very CPU-consuming and not very efficient.

Is there a way to optimize this piece of code, maybe by using vectorized functions that work on entire arrays?

Upvotes: 1

Views: 132

Answers (2)

EBH
EBH

Reputation: 10440

Here is a much faster (and readable) way to get the same result:

N=1e4;
cond_array = [0:(N/2-1) -N/2+(0:(N/2-1))]/(N);
condition  = 0.1;
% this is so you don't check the same condition multiple times:
cond = abs(cond_array)<=condition;
% a vector of the positions in 'arr_one' and 'arr_two':
pos = (1:N).';
% instead of m*k(1)+m*k(2)... use: m*sum(k):
k1 = sum(pos(cond)); % for arr_one
k2 = sum(pos(~cond));% for arr_two
% the final result:
arr_one = pos.*k1;
arr_two = pos.*k2;

For the second case you mention in the comments, where m*k becomes exp((m-1)*(k-1)), we can again compute the sum of exp((m(1)-1)*(k(1)-1)) +...+ exp((m(1)-1)*(k(N)-1))... using vectorization, and then use some minimal loop to go over all ms:

% we define new vectors of constants:
k1 = pos(cond);
k2 = pos(~cond);
% define new functions for each of the arrays:
ek1 = @(m) sum(exp((m-1).*(k1-1)));
ek2 = @(m) sum(exp((m-1).*(k2-1)));
% and we use 'arrayfun' for the final result:
arr_one = arrayfun(ek1,1:N).';
arr_two = arrayfun(ek2,1:N).';

arrayfun is not faster than a for loop, just more compact. Using a for loop will be like this:

arr_one = zeros(N,1);
arr_two = zeros(N,1);
for k = 1:N
    arr_one(k) = ek1(k);
    arr_two(k) = ek2(k);
end

And here is another, more general, option using bsxfun:

ek = @(m,k) exp((m-1).*(k-1));
arr_one = sum(bsxfun(ek,1:N,k1)).';
arr_two = sum(bsxfun(ek,1:N,k2)).';

Upvotes: 4

zglin
zglin

Reputation: 2919

Look into the use of logical indexing. Without understanding your code too well, I'd imagine that you can remove the loops through array functions similar to the below.

arr_one(abs(cond_array)<condition)

This will remove the need for the comparison function, which will allow you to use an anonymous array function in order to create your computation.

However, if I understand your code correctly, you're just adding the product of the position of the condition index and the position of the array index to the array. If you do that, it will be much easier to just do something similar to the below. 

position=(1:N)'
arr_one(abs(cond_array)<condition)=arr_one(abs(cond_array)<condition)+position(abs(cond_array)<condition)

In this statement, you're looking for all the items where the cond_array is less than the condition, and adding the position (effectively a proxy for the m and k in your previous example).

In terms of runtime, I think you have to be 1 to 3 orders of magnitude larger than 1e4 for this code to make a significant difference in runtimes.

Upvotes: 0

Related Questions