Векторизуйте код Matlab для сопоставления ближайших значений в двух массивах

У меня есть два списка временных меток, и я пытаюсь создать карту между ними, которая использует imu_ts как истинное время и пытается найти ближайшее к нему значение vicon_ts. Результатом является матрица 3xd, где первая строка — это индекс imu_ts, третья строка — это время unix для этого индекса, а вторая строка — это индекс ближайшего значения vicon_ts над отметкой времени в том же столбце.

Вот мой код, и он работает, но очень медленно. Я не уверен, как его векторизовать.

function tmap = sync_times(imu_ts, vicon_ts)

tstart = max(vicon_ts(1), imu_ts(1));
tstop = min(vicon_ts(end), imu_ts(end));

%trim imu data to 
tmap(1,:) = find(imu_ts >= tstart & imu_ts <= tstop);
tmap(3,:) = imu_ts(tmap(1,:));%Use imu_ts as ground truth

%Find nearest indecies in vicon data and map
vic_t = 1;
for i = 1:size(tmap,2)
    %
    while(vicon_ts(vic_t) < tmap(3,i))
        vic_t = vic_t + 1;
    end
    tmap(2,i) = vic_t;
end

Временные метки уже отсортированы в порядке возрастания, так что это, по сути, операция O(n), но из-за того, что она зациклена, она выполняется медленно. Любые векторизованные способы сделать то же самое?

Изменить Похоже, что он работает быстрее, чем я ожидал или измерял сначала, так что это больше не критическая проблема. Но мне было бы интересно посмотреть, есть ли хорошие решения этой проблемы.


matlab optimization vectorization
person CodeFusionMobile    schedule 05.02.2013    source источник
comment
Вчера я ответил на аналогичный вопрос, не видя этого, вероятно, связанного . Я считаю, что это решение применимо и здесь, хотя обрезка и создание матрицы 3xd все равно должны быть выполнены позже.   -  person arne.b    schedule 19.02.2013

Ответы (3)


arrow_upward
1
arrow_downward

Взгляните на knnsearch в MATLAB. Используйте расстояние городского квартала, а также установите дополнительное ограничение, согласно которому точка данных в vicon_ts должна быть меньше, чем ее сосед в imu_ts. Если это не так, возьмите следующий индекс. Это необходимо, потому что городской квартал принимает абсолютное расстояние. Другой вариант (и предпочтительный) — написать собственную функцию расстояния.

person Autonomous    schedule 05.02.2013

arrow_upward
1
arrow_downward

Я считаю, что ваш текущий метод является правильным, и я бы не стал пытаться векторизовать дальше. Векторизация на самом деле может быть вредной, когда вы пытаетесь оптимизировать некоторые внутренние циклы, особенно когда вы знаете больше о контексте ваших данных (например, они отсортированы), чем могут знать инженеры Mathworks.

Вещи, которые я обычно ищу, когда мне нужно оптимизировать какой-то фрагмент кода, например, это:

  1. Все массивы предварительно распределены (это самый большой фактор производительности)
  2. Быстрые внутренние циклы используют простой код (Matlab довольно эффективно выполняет JIT для основных команд, но должен интерпретировать другие).
  3. Воспользуйтесь любыми специальными функциями данных, которые у вас есть, например. использовать соответствующие алгоритмы сортировки и условия раннего выхода из некоторых циклов.

Вы уже делаете все это. Я рекомендую без изменений.

person Pursuit    schedule 05.02.2013

arrow_upward
0
arrow_downward

Хорошим началом может быть избавление от while, попробуйте что-то вроде:

for i = 1:size(tmap,2)
    C = max(0,tmap(3,:)-vicon_ts(i));
    tmap(2,i) = find(C==min(C));
end
person Smash    schedule 05.02.2013
comment
Find на самом деле был бы более неэффективным, потому что он не предполагает отсортированные данные. Поскольку данные vic_t отсортированы, общая сложность уже равна O(n), поэтому добавление find и max делает ее O(n^2) - person CodeFusionMobile; 07.02.2013