For loop vectorisation having structure arrays

Question

Melanie VT 2023-3-11

0
链接

此问题的直接链接

https://ww2.mathworks.cn/matlabcentral/answers/1927055-for-loop-vectorisation-having-structure-arrays

评论： Melanie VT 2023-3-13

采纳的回答： Jan

data.mat

在 MATLAB Online 中打开

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

2 个评论
显示无隐藏无

Walter Roberson 2023-3-11

在 MATLAB Online 中打开

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 2023-3-12

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

请先登录，再进行评论。

请先登录，再回答此问题。

Answer 1

Jan 2023-3-12

1
链接

此回答的直接链接

https://ww2.mathworks.cn/matlabcentral/answers/1927055-for-loop-vectorisation-having-structure-arrays#answer_1191155

编辑：Jan 2023-3-12

在 MATLAB Online 中打开

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

4 个评论
显示 2更早的评论隐藏 2更早的评论

Jan 2023-3-13

在 MATLAB Online 中打开

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 2023-3-13

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 2023-3-13

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🙏🏻

请先登录，再进行评论。