CODEWITHSUNDEEP
matlaboptimizationvectorization
CodeFusionMobile
CodeFusionMobile

Reputation: 15110

Vectorize matlab code to map nearest values in two arrays

I have two lists of timestamps and I'm trying to create a map between them that uses the imu_ts as the true time and tries to find the nearest vicon_ts value to it. The output is a 3xd matrix where the first row is the imu_ts index, the third row is the unix time at that index, and the second row is the index of the closest vicon_ts value above the timestamp in the same column.

Here's my code so far and it works, but it's really slow. I'm not sure how to vectorize it.

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

The timestamps are already sorted in ascending order, so this is essentially an O(n) operation but because it's looped it runs slowly. Any vectorized ways to do the same thing?

Edit It appears to be running faster than I expected or first measured, so this is no longer a critical issue. But I would be interested to see if there are any good solutions to this problem.

Upvotes: 0

Views: 167

Answers (3)

Pursuit
Pursuit

Reputation: 12345

I believe that your current method is sound, and I would not try and vectorize any further. Vectorization can actually be harmful when you are trying to optimize some inner loops, especially when you know more about the context of your data (e.g. it is sorted) than the Mathworks engineers can know.

Things that I typically look for when I need to optimize some piece of code liek this are:

  1. All arrays are pre-allocated (this is the biggest driver of performance)
  2. Fast inner loops use simple code (Matlab does pretty effective JIT on basic commands, but must interpret others.)
  3. Take advantage of any special data features that you have, e.g. use sort appropriate algorithms and early exit conditions from some loops.

You're already doing all this. I recommend no change.

Upvotes: 1

Autonomous
Autonomous

Reputation: 9075

Have a look at knnsearch in MATLAB. Use cityblock distance and also put an additional constraint that the data point in vicon_ts should be less than its neighbour in imu_ts. If it is not then take the next index. This is required because cityblock takes absolute distance. Another option (and preferred) is to write your custom distance function.

Upvotes: 1

Smash
Smash

Reputation: 3802

A good start might be to get rid of the while, try something like:

for i = 1:size(tmap,2)
    C = max(0,tmap(3,:)-vicon_ts(i));
    tmap(2,i) = find(C==min(C));
end

Upvotes: 0

Related Questions