Vectorize for-loop that changes overlapping parts of an array

Question

Maximilian Rüppell 2016-4-20

0
链接

此问题的直接链接

https://ww2.mathworks.cn/matlabcentral/answers/280009-vectorize-for-loop-that-changes-overlapping-parts-of-an-array

评论： Roger Stafford 2016-4-20

Hi everyone,

I have problem speeding up my code. I have a very large (20-40m datapoints) logical array and at every position where it reads "1", the next N datapoints should be set to "1" a well.

I have the following code that is quite slow since it has a for loop:

N=5000-1;
logarray; %logical array of size 40000000x1 
inx=find(logarray);  %inx can be quite large as well, 1-5m points
for ii=1:length(inx)  
    logarray(inx(ii):(inx(ii)+N))=1;
end

This code works, but is very slow (more than 10 secs). I tried something like

logarray(find(inx):(find(inx)+100))=1;

but this did not work. I was wondering whether vectorisation would be a solution here? Mind that overlapping parts of the logical array are changed by the loop.

Does anyone have a good suggestion?

Thanks, Maximilian

0 个评论
显示 -2更早的评论隐藏 -2更早的评论

请先登录，再进行评论。

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

Answer 1

Jos (10584) 2016-4-20

0
链接

此回答的直接链接

https://ww2.mathworks.cn/matlabcentral/answers/280009-vectorize-for-loop-that-changes-overlapping-parts-of-an-array#answer_218696

编辑：Jos (10584) 2016-4-20

在 MATLAB Online 中打开

Easy when using convolution:

logarray = logical([0 1 1 0 0 0 1 0 0 0 1 0 0 0 0 1 0 1 0 0 0 0 1])
N = 2 ;
out = conv2(double(logarray(:)), ones(N+1,1)) ;
out = out(1:numel(logarray))>0 ;
out = reshape(out,size(logarray)) ; 
disp([logarray(:) ; out(:)]) ;

2 个评论
显示无隐藏无

Jos (10584) 2016-4-20

taking about 2 seconds on my old mac for a 3e7 elements and N = 5000

Maximilian Rüppell 2016-4-20

Works like a charm - thanks!

请先登录，再进行评论。

Answer 2

Roger Stafford 2016-4-20

0
链接

此回答的直接链接

https://ww2.mathworks.cn/matlabcentral/answers/280009-vectorize-for-loop-that-changes-overlapping-parts-of-an-array#answer_218703

编辑：Roger Stafford 2016-4-20

在 MATLAB Online 中打开

It isn't perhaps that you have a for-loop that is slowing you down so much as that your loop is repeating the writing of ones so much in overlapping intervals. You might try the following which first combines overlapping intervals before doing the writing of ones.

   N=5000-1;
   f1 = find(logarray);
   f2 = min(f1+N,length(logarray));
   f3 = zeros(size(f1));
   f4 = zeros(size(f2));
   ie = 1;
   f3(ie) = f1(ie);
   f4(ie) = f2(ie);
   for ib = 1:size(f1,1)-1
     if f1(ib+1) > f4(ie)+1
       ie = ie+1;
       f3(ie) = f1(ib+1); 
     end
     f4(ie) = f2(ib+1);
   end
   f3 = f3(1:ie); % The intervals defined by f3 and f4 don't overlap
   f4 = f4(1:ie);
   for ib = 1:ie
     logarray(f3(ib):f4(ib)) = 1;
   end

1 个评论
显示 -1更早的评论隐藏 -1更早的评论

Roger Stafford 2016-4-20

在 MATLAB Online 中打开

I thought of another way you could try which uses 'accumarray'. Assume 'logarray' is a column vector.

   N = 1000;
   f = find(logarray);
   t = ones(size(f));
   logarray = min(cumsum(accumarray([f;f+N+1],[t;-t],...
              [length(logarray)+N+1,1])),1);
   logarray(end) = [];

请先登录，再进行评论。