Vectorization of nested for loops

Hi everyone,

I'm doing some practice to vectorize nested for loops.

For example, I have the following code:

a = linspace(40,45,5);

b = linspace(90,95,5);

idx = 1;

for ii = 1:4

for jj = 1:4

c(idx,:) = [a(ii),a(ii + 1),b(jj),b(jj + 1)];

idx = idx + 1;

end

end

Is there an efficient way to vectorize and run it in a much more efficiently way?

[Dyuman Joshi]

What you are trying is not allowed, you are storing 4 elements in one-place holder. If you try to run your code, you will get an error.

Do you want to horizantally/vertically concetanate the elements? or do you store the each output seperately?

[Angelo]

I'm sorry, I just corrected the code.

Answer 1

[Jan]

Your fixed code:

a = linspace(40,45,5);
b = linspace(90,95,5);
idx = 1;
for ii = 1:4
    for jj = 1:4
        c(idx, :) = [a(ii),a(ii + 1),b(jj),b(jj + 1)];
        %    ^^^  c(idx) is a scalar, but the right side is a vector
        idx = idx + 1;
    end
end

The first and important improvement is a pre-allocation, because the iterative growing of arrays is extremely expensive:

idx = 1;
c = zeros(16, 4);  % Pre-allocate !!!
for ii = 1:4
    for jj = 1:4
        c(idx, :) = [a(ii),a(ii + 1),b(jj),b(jj + 1)];
        idx = idx + 1;
    end
end

Without a pre-allocation the runtime grows exponentially, and this the programmers hell.

Vectorizing the inner loop:

idx = 1;
c = zeros(16, 4);  % Pre-allocate !!!
for ii = 1:4
    % for jj = 1:4
        c(idx:idx+3, :) = [repelem(a(ii), 4, 1), repelem(a(ii + 1), 4, 1), ...
                           b(1:4).', b(2:5).'];
        idx = idx + 4;
    % end
end

I do not assume, that this is faster. Most of all the code has a hight complexity and is harder to debug and maintain. But the strategy is easy: Move the index from the for loop inside the code.

A full vectorizing:

c = [repelem(a(1:4).', 4, 1), repelem(a(2:5).', 4, 1), ...
     repmat(b(1:4).', 4, 1),  repmat(b(2:5).', 4, 1)];

Because c is not filled iteratively, a pre-allocation would waste time only.

I guess, that a fully de-vectorized code is faster:

c   = zeros(16, 4);  % Pre-allocate !!!
idx = 0;
for ii = 1:4
    a1 = a(ii);
    a2 = a(ii + 1);
    for jj = 1:4
        idx       = idx + 1;
        c(idx, 1) = a1;
        c(idx, 2) = a2;
        c(idx, 3) = b(jj);
        c(idx, 4) = b(jj + 1);
    end
end

If I expand the data size to n=1e4, I get these runtimes under R2018b:

% Original without pre-allocation: Stopped after 5 Minutes...
Elapsed time is 15.586963 seconds.  % Pre-allocation
Elapsed time is 4.184093 seconds.   % Vectorized inner loop
Elapsed time is 26.814111 seconds.  % Fully vectorized :-(
Elapsed time is 1.668518 seconds.   % Only scalars and loops !!!

You see, that vectorizing is not necessarily the fastes way. The old rumor, that Matlab is slow for processing loops is outdated since Matlab 6.5 (2002 - 20 years ago).

[Angelo]

Great! Thank you for your precious help!