arrays - 优化 MATLAB 中的时间戳过滤器 - 使用非常大的数据集

Question

我正在用 MATLAB 编写程序(必须使用 MATLAB 而不能真正使用 MEX)来过滤大量数据。

我需要实现的过滤器之一要求我将时间戳向量与已知“坏”时间列表进行比较，其他时间戳不能在其周围出现。

一个典型的时间戳向量有大约 2,000,000 个条目，我有一个包含大约 300,000 个“坏时间”的列表。

这是一个工作示例，如果 TIME=[1, 2.3, 5.5, 9.1, 10]; 和 BAD_TIMES=[5.2, 9.3];，我们具有公差 tolerance=0.25;，则 TIME 中 4.95 和 5.45 以及 9.05 和 9.55 之间的所有时间戳必须被删除。这意味着清理后的向量 TIME_CLEAN 应该等于 TIME_CLEAN=[1, 2.3, 5.5, 10];。

这个问题很容易解决，我已经用大约 4 或 5 种不同的方法解决了。但是，对于 1,000,000 个时间戳作业，这个问题很容易需要一个小时来计算。

我希望在典型的 Core-i7 工作站上在 2 分钟内解决此类问题，以使此过滤器在这么多时间条目下可行。

我已经包含了这段代码的工作版本。我了解代码矢量化和 bsxfun() 等函数可以提供帮助，但相对于我对此过滤器所需的效率类型而言，改进微不足道。

有没有非常聪明的方法可以非常有效地解决这个问题？任何帮助将不胜感激。

附言下面的代码是完整的；它生成设置问题所需的所有数据并解决它(尽管非常慢!)。将 NO_OF_TIMESTAMPS 变量更改为更大的值(例如 1,000,000)以观察它的爬行!

clear all %% CLEAR WORKSPACE
close all %% CLOSE FIGURES
clc %% CLEAR COMMAND WINDOW

NO_OF_TIMESTAMPS=10000; %% NUMBER OF TIMESTAMPS IN ORIGINAL DATA

TOLERANCE=2; %% TOLERANCE AROUND TIMESTAMP

A=sort(randi(NO_OF_TIMESTAMPS/10,NO_OF_TIMESTAMPS,1)); %% GENERATE ARTIFICIAL TIMESTAMPS

B=unique(sort(round(randi([NO_OF_TIMESTAMPS/2,NO_OF_TIMESTAMPS*5],[NO_OF_TIMESTAMPS/10,1])/10))); %% GENERATE ARTIFICIAL LIST OF BAD TIMESTAMPS

B_LB=B-TOLERANCE; %% CREATE A LIST OF LOWERBOUND BAD TIMESTAMPS
B_UB=B+TOLERANCE; %% CREATE A LIST OF UPPERBPUND BAD TIMESTAMPS
B_RANGE=[B_LB B_UB]; %% AUGMENTED MATRIX COMPOSED OF VECTORS B_LB and B_UB

A_ROWS=size(A,1); %% SIZE OF A;

B_ROWS=size(B,1); %% SIZE OF B;

tic; %% START TIMER

A_TO_CLEAN=ones(A_ROWS,1); %% BOOLEAN VECTOR TO BE USED IN FILTERING
for ii=1:A_ROWS

    for jj=1:B_ROWS

        if A(ii)>=B_RANGE(jj,1) && A(ii)<=B_RANGE(jj,2) %% CHECK EACH MEMBER OF A VERSUS EACH MEMBER OF B_RANGE

           A_TO_CLEAN(ii)=0; %% SET INDEX VECTOR A_TO_CLEAN = 0 SO THAT WE CAN DELETE LATER

           break; %% A(ii) CAN ONLY BE ERASED ONCE, SO BREAK jj LOOP AND GO TO NEXT ii

        end

    end

end

CLEAN=A(~~A_TO_CLEAN); %% DELETE A VIA LOGICAL INDEXING

toc; %% END TIMER

clearvars -except A B_RANGE CLEAN %% ONLY SHOW RELEVANT VARIABLES

Answer 1

使这变得有效的技巧是首先对两个向量进行排序。然后通过其中一个向量创建一个简单循环，同时维护第二个向量的索引来描述最近的元素。也就是说，你会有类似的东西

for ix1 = 1:length(timestamps)
    while (badTimes(ix2) < timestamps(ix1)
        ix2 = ix2+1;
    end
    %check timestamp(ix1) against badTimes(ix2), and maybe badTimes(ix2 + 1) and  badTimes(ix2 - 1)
end

排序相对有效，尤其是使用内置函数。现在您只需要一个循环。

这现在与 a merge sort 的部分相似算法。