For loop vectorisation having structure arrays

Hi,

I'm still having trouble converting for loops into vectorised form. This time, I have a code snippet which generates two arrays (array2 & array3) using a for loop. Unfortunately, I couldn't manage to get a vectorised solution. I'd be more than happy to get your help.

Thanks in advance,

Mel

array2 = zeros(height(array1),1);
array3 = zeros(height(array1),1);
for i = 1:length(array1)    
    temp_s1 = array1(i); 
    idx = [struct_data1(:).cid].' == temp_s1;
    temp_s2 = struct_data1(idx);
    array2(i) = temp_s2([struct_data1(idx).group2].'== 1).group1;
    array3(i) = struct_data2([struct_data2(:).cid].' == temp_s1).gid;
end

[Walter Roberson]

array2(i) = temp_s2([struct_data1(idx).group2].'== 1).group1;

That assumes that you will get exactly one match from the == 1 in that line, and that the group1 returned is a scalar.

As outside observers, we have no particular reason to expect that you will ever sometimes get 0 matches or sometimes get more than one match.

We can guess that idx might have more than one true entry since you [struct_data1(idx).group2] which is code that is compatible with the possibility that more than one entry in struct_data1 is being referred to.

[Melanie VT]

I get what you mean @Walter Roberson! Thank you for drawing my attention to this matter🙏🏼

Answer 1

[Jan]

What is the prupose of a vectorization here? Remember that vectorized code creates temporary arrays usually and this is expensive. Therefore loops are faster in many cases.

Avoid repeated work instead:

c1 = [struct_data1(:).cid].';  % Do this once only
c2 = [struct_data1(:).group2].';
c3 = [struct_data2(:).cid].';
for i = 1:length(array1) 
    temp_s1   = array1(i); 
    idx       = (c1 == temp_s1);
    temp_s2   = struct_data1(idx);
    array2(i) = temp_s2(c2(idx) == 1).group1;
    array3(i) = struct_data2(c3 == temp_s1).gid;
end

In my local Matlabr R2018b this reduces the runtime from 38 sec of the original to 0.4 sec.

Further 10% faster:

[~, index] = ismember(array1, c3);

array2 = zeros(size(array1, 1),1);
array3 = zeros(size(array1, 1),1);
for i = 1:length(array1) 
    temp_s1   = array1(i); 
    idx       = (c1 == temp_s1);
    temp_s2   = struct_data1(idx);
    array2(i) = temp_s2(c2(idx) == 1).group1;
    array3(i) = struct_data2(index(i)).gid;
end

[Melanie VT]

Thank you very much for sharing your solutions @Jan. They are definitely much smarter and more effective. However, this approach doesn’t completely solve my problem. My purpose is to shorten the duration of completion, as you guessed. Although your solution is a great alternative, completion time doesn’t increase linearly with the increase of inputs. When I increase the size of the inputs by 100 times (which is very probable in my case, considering the data I usually work with), the duration increases by 6000 times (0.36 sec becomes 36 min. It can be tested using the bigger data here, ~24 MB). Therefore, I keep searching for finding a faster solution. Still very grateful for your sharing🙏🏼

[Jan]

I've simplified the code again. For large arrays the logical indexing for idx is less efficient than find(). A parfor() instead of the for loop accelerates the code by 10% on my old 2 core i5, but you need the parallel processing toolbox. Run gcp before comparing the timings to ignore the overhead for the parallel pool.

% Version 3:
c1 = [struct_data1.cid].';
c2 = [struct_data1.group2].' == 1;
c4 = [struct_data1.group1];

array2 = zeros(size(array1, 1),1);

[~, index] = ismember(array1, [struct_data2.cid].');
parfor i = 1:nLoop
    idx       = find(c1 == array1(i));
    array2(i) = c4(idx(c2(idx)));
end

c5     = [struct_data2.gid];
array3 = c5(index);

This takes 20 minutes for the complete set.

The next speedup comes from replacing the linear search in find(c1 == array1(i)) by a binary search using ismember with a corted c1. This finds the first occurence of array1(i) only and a loop is used to find the matching set of values. Then c2(idx(k)) can be used to stop the loop. c2 and c4 must be sorted also:

% Version 4:
c2 = [struct_data1.group2].' == 1;
c4 = [struct_data1.group1];

[~, index] = ismember(array1, [struct_data2.cid].');

[c1s, c1s_idx] = sort([struct_data1.cid].');
c2s = c2(c1s_idx);
c4s = c4(c1s_idx);

array2 = zeros(size(array1, 1),1);
parfor i = 1:nLoop
    % A lot of overhead: still 20 min   
    %   [~, b] = ismember(array1(i), c1s);
    % Avoid the overhead and call the core directly: 6.4 seconds !!!
    [~, b] = builtin('_ismemberhelper', array1(i), c1s);
    while ~c2s(b)
       b = b + 1;
    end
    array2(i) = c4s(b);
end

c5     = [struct_data2.gid];
array3 = c5(index);

This takes 6.4 seconds only! The older core function is even faster:

    b = ismembc2(array1(i), c1s);
    while ~c2s(b)
       b = b - 1;   % - instead of +
    end

4.4 seconds.

For the binary search see: https://www.mathworks.com/matlabcentral/answers/92533-how-do-i-perform-a-binary-search-of-a-presorted-array .

[Jan]

My first suggestion offered a speedup of a factor 100. The version 4 with ismembc2 is again 260 times faster. 26'000 is a satisfying acceleration and it is based on simplifications of the code, not a vectorization.

Most of the time in the fastest version is spent for combining the scalar fields of the struct to vectors. This shows, that the chosen representation of the data as structs might by clear and clean, but a bunch of vectors will be more efficient.

[Melanie VT]

That's a splendid job @Jan! My hat's off to you👒 I can't literally thank you enough. You're providing not only solutions but also capacity strengthening! This is why you're an L10-MVP, I guess. From now on, I will build my codes with this logic. Thanks a million; it's really exceptional🙏🏻