3

非常に大量のデータをフィルター処理するプログラムをMATLABで作成しています（MATLABを使用する必要があり、実際にはMEXを使用できません）。

実装する必要のあるフィルターの1つでは、タイムスタンプベクトルと、他のタイムスタンプが発生しない既知の「不良」時間のリストを比較する必要があります。

典型的なタイムスタンプベクトルには約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のタイムスタンプジョブの場合、この問題の計算には1時間かかることがあります。

私は、このタイプの問題を典型的なCore-i7ワークステーションで2分以内に解決し、このフィルターがこの多くの時間のエントリで実行可能になるようにしたいと考えています。

このコードの動作バージョンを含めました。bsxfun()コードのベクトル化や役立つ関数などは理解していますが、このフィルターに必要な効率のタイプに比べると、改善はわずかです。

この問題を非常に効率的に解決するための非常に賢い方法はありますか？どんな助けでも大歓迎です。

PS以下のコードは完全です。問題の設定に必要なすべてのデータを生成し、それを解決します（非常にゆっくりですが！）。変数をより大きなもの（1,000,000など）に変更してNO_OF_TIMESTAMPS、クロールを監視します。

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

これを効率的にして両方のベクトルを最初にソートするための秘訣。次に、最も近い要素を表す2番目のベクトルへのインデックスを維持しながら、ベクトルの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

特に組み込みを使用すると、並べ替えは比較的効率的です。そして今、あなたはただ一つのループを必要とします。

これは現在、マージソートアルゴリズムの類似部分を持っています。

于 2012-09-12T06:04:09.600 に答える
3

私のコンピューターでは、1e6 の「タイムステップ」に対して 0.025 秒かかります。このメソッドは 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 に答える