测试滑动区间内的中间点是否为最大值

Question

lengthData = 1500;
data = rand(lengthData,1);
result = zeros(floor(lengthData/2),lengthData);
for i = 1:floor(lengthData/2)-1
    for j = 1+i:length(data)-i
        if data(j) == max(data(j-i:j+i))
            result(i,j)=1;
        end
    end
end

我有一个指定 lengthData 的数据点存储在变量 data 中。现在我试图在指定区间内找到最大值，区间长度在增加。

一个快速的观察是，随着间隔大小的增加，result 中特定行中的条目数正在减少。以下是 sum(result,2) 的图表，用于验证代码是否按预期工作。

但是，这段代码的执行时间很长。对于较大的 lengthData 值（大约 6000），花费的时间几乎是 22 秒（从 lengthData 为 1500 时的 0.4 秒开始）。

有没有其他方法可以实现我的逻辑或对其进行矢量化，以某种方式加快速度？

Answer 1

我能够使用以下内容对内部循环进行矢量化...

lengthData=1500;
data=rand(lengthData,1);
result=zeros(floor(lengthData/2),lengthData);

for i=1:floor(lengthData/2)-1

    del = 2*i+1;
    ind_arr = [];
    ind_arr(:,1) = 1:lengthData+1-del;
    ind_arr(:,2:del) = 1;
    ind_arr = cumsum(ind_arr,2);

    data_arr = data(ind_arr);

    [~,max_ind] = max(data_arr,[],2);

    result(i,1+i:length(data)-i) = max_ind==(i+1);

end

可能有更简洁的构建方法 ind_arr 但这似乎会给出与您的原始代码匹配的结果。

运行它通过 R2014b 中的分析器显示

  time   calls  line
             1    1 lengthData=1500; 
             1    2 data=rand(lengthData,1); 
             1    3 result=zeros(floor(lengthData/2),lengthData); 
             1    4 result2 = result; 
                  5 
             1    6 t1ID = tic; 
                  7 
             1    8 for i=1:floor(lengthData/2)-1 
           749    9     for j=1+i:length(data)-i 
  3.66  561750   10         if(data(j)==max(data(j-i:j+i))) 
< 0.01    4276   11             result(i,j)=1; 
          4276   12         end 
  0.70  561750   13     end 
           749   14 end 
                 15 
             1   16 fprintf('Original Time: %g\n',toc(t1ID)); 
                 17 
             1   18 t2ID = tic; 
                 19 
             1   20 for i=1:floor(lengthData/2)-1 
                 21     
           749   22     del = 2*i+1; 
  0.02     749   23     ind_arr = []; 
< 0.01     749   24     ind_arr(:,1) = 1:lengthData+1-del; 
  0.45     749   25     ind_arr(:,2:del) = 1; 
  0.51     749   26     ind_arr = cumsum(ind_arr,2); 
                 27 
  1.42     749   28     data_arr = data(ind_arr); 
                 29 
  0.52     749   30     [~,max_ind] = max(data_arr,[],2); 
                 31 
  0.05     749   32     result2(i,1+i:length(data)-i) = max_ind==(i+1); 
                 33     
           749   34 end 
                 35 
             1   36 fprintf('Single Loop Time: %g\n',toc(t2ID));

Original Time: 4.53376
Single Loop Time: 2.81267

Answer 2

基于：

Maxima is occuring at the middle of window in my implementation of code. May be I was not clear in the problem description. I am looking for various maxima. There is only one global maxima but there are many local maxima. Now there local maximas can only exist when they are greater than numbers in their immediate vicinity. This vicinity I am considering as lenght of moving window. A particular value may be local maxima when sliding window is 5 but it may not be local maxima when sliding window is increased to 10.(...)

我建议看一下 findpeaks() 正是这样做的：找到局部最大值。然后，您的 "sliding window length" 将被合并到 'MinPeakDistance' name-value 对中，您在问题中提到的最小高度将由 'MinPeakHeight'.

给出

Answer 3

我有运行使用和 findpeaks() 的代码。此功能以更好的时间性能为我提供了所需的结果，请参阅以下基准：

tic;
lengthData=6000;
data=rand(lengthData,1);
result=zeros(floor(lengthData/2),lengthData);
for i=1:floor(lengthData/2)-1
    for j=1+i:length(data)-i
        if(data(j)==max(data(j-i:j+i)))
            result(i,j)=1;
        end
    end
end
toc;

tic;
result1=zeros(floor(lengthData/2),lengthData);
for i=1:floor(lengthData/2)-1
    del = 2*i+1;
    ind_arr = [];
    ind_arr(:,1) = 1:lengthData+1-del;
    ind_arr(:,2:del) = 1;
    ind_arr = cumsum(ind_arr,2);
    data_arr = data(ind_arr);
    [~,max_ind] = max(data_arr,[],2);
    result1(i,1+i:length(data)-i) = max_ind==(i+1);
end
toc;


tic;
result2=zeros(floor(lengthData/2),lengthData);

for i=1:floor(lengthData/2)-1

    [~,locs]=findpeaks(data,'MinPeakDistance',i);
    result2(i,1:length(locs))=locs;
end
toc;

结果：

Elapsed time is 23.317170 seconds.   % Original
Elapsed time is 312.340804 seconds.  % Vectorized
Elapsed time is 3.053548 seconds.    % findpeaks()

我在 Xeon 3.4 处理器和 32GB RAM 上使用 MATLAB R2018a。

测试滑动区间内的中间点是否为最大值

Test whether the middle point within a sliding interval is its maximum

performance

matlab

max

vectorization

windowing