3

我正在用 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;所有时间戳都必须被删除。这意味着清理后的向量应该等于。TIME4.95 and 5.459.05 and 9.55TIME_CLEANTIME_CLEAN=[1, 2.3, 5.5, 10];

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

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

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

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

PS下面的代码是完整的；它生成设置问题所需的所有数据并解决它（尽管非常缓慢！）。将变量更改为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
4

3 回答 3

4

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

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

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

这现在具有合并排序算法的相似部分。

于 2012-09-12T06:04:09.600 回答
3

在我的计算机上，这需要 0.025 秒来执行 1e6 个“时间步长”。该方法线性地通过 A，在通过 B_RANGE 时更​​新索引。需要特别注意“数组结束”的情况。

BR=B_RANGE';
C=logical(ones(size(A)));
j=1;
i=1;
tic;
while i<=A_ROWS && j<=B_ROWS

    if A(i)==99
        i=1;
    end
    % find start of bad signal
    while A(i)<BR(1,j) && i<A_ROWS
        i=i+1;
    end
    % finish at the end of A    
    if i==A_ROWS
        break;
    end
    ii=i;
    % find end of bad signal
    while A(ii)<=BR(2,j) && ii<A_ROWS
        ii=ii+1;
    end
    % special case for end of array
    if A(ii)==A(ii-1)
        ii=ii+1;
    end
    % mark bad signal entries
    C(i:ii-1)=false;
    i=ii;
    j=j+1;
end
AM=A(C);
toc
于 2012-09-12T08:38:13.863 回答
0

这需要 0.3 秒：

%% generate random measured and bad time samples
t       = sort(1e4 * rand(2e6, 1));
t_bad   = sort(1e4 * rand(3e5, 1));

%% find bad indexes
tolerance = 0.01;
idx_bad = ismember(round(t / tolerance), round(t_bad / tolerance));
于 2012-09-13T21:09:19.210 回答