Оптимизация фильтра меток времени в MATLAB - Работа с очень большими наборами данных

Я пишу программу на 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 and 5.45 а также9.05 and 9.55 должны быть стерты. Это означает, что очищенный векторTIME_CLEAN должно быть равноTIME_CLEAN=[1, 2.3, 5.5, 10];.

Эту проблему легко решить, и я решил ее примерно 4 или 5 различными способами. Однако для задания с отметкой в 1 000 000 единиц времени эта проблема может легко занять один час.

Я собираюсь решить эту проблему менее чем за 2 минуты на типичной рабочей станции Core-i7, чтобы этот фильтр был жизнеспособным с таким количеством записей времени.

Я включил рабочую версию этого кода. Я понимаю векторизацию кода и такие функции, как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

Ответы на вопрос(3)

Решение Вопроса

чтобы сделать это эффективным, чтобы сначала отсортировать оба вектора. Затем создайте простой цикл через один из векторов, сохраняя при этом индекс во втором векторе, описывающем ближайший элемент. То есть у вас будет что-то вроде

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

Сортировка относительно эффективна, особенно с использованием встроенных модулей. И теперь вам нужен только один цикл.

Это теперь имеет сходство частей аСортировка слиянием алгоритм.

 13 сент. 2012 г., 20:52
Из любопытства, какова ваша продолжительность до / после обработки?
 felimz13 сент. 2012 г., 18:19
Это сработало очень хорошо. Большое спасибо.
 felimz19 сент. 2012 г., 08:59
Алгоритм в OP занял около 3 часов 30 минут, а ваш метод занял около 2,3 секунд. Весьма замечательно.

Это занимает 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));
 31 янв. 2013 г., 16:48
Обратите внимание, что это точно не отбрасывает значения, которые находятся дальше, чем допустимое отклонение от неправильного значения.Example: Bad value is 0.4 and tolerance is 1, Когда вы не заботитесь о точном размере допуска, все должно быть хорошо.

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
 felimz13 сент. 2012 г., 18:19
Этот ответ сработал, но объяснение Преследования было более скупым. Я хотел бы принять несколько ответов.
 13 сент. 2012 г., 18:50
@ user1090581 Хех. По сути, они одинаковы. Вы не должны принимать все ответы. Это нормально с 1, даже если это не мое :) Некоторые люди не удосужились сделать даже это ..

Ваш ответ на вопрос