Вопрос по filtering, optimization, performance, arrays, matlab – Оптимизация фильтра меток времени в MATLAB - Работа с очень большими наборами данных

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;тогда все отметки времени в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   ответа
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

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

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

Это сработало очень хорошо. Большое спасибо. felimz
Алгоритм в OP занял около 3 часов 30 минут, а ваш метод занял около 2,3 секунд. Весьма замечательно. felimz
Из любопытства, какова ваша продолжительность до / после обработки?
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));
Обратите внимание, что это точно не отбрасывает значения, которые находятся дальше, чем допустимое отклонение от неправильного значения.Example: Bad value is 0.4 and tolerance is 1, Когда вы не заботитесь о точном размере допуска, все должно быть хорошо.
3

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

Похожие вопросы