algorithm - 查找与某个时间点重叠的一组目标

Question

在某个时间点，我需要找到所有早于和晚于该时间点的Target。

目前我正在做以下事情:

for current_time = sorted_set_of_times;
    target_set = find([Targets.First_Time] <= current_time ... 
        & [Targets.Last_Time] >= current_time);
    % Using target_set here. Targets are not modified within this loop
end

MATLAB 探查器告诉我这条线大约需要 40 分钟，调用 40,000 次。

有什么方法可以更有效地做到这一点？

current_time按顺序在 for_loop 中递增。我在想，这个总是在增加的事实可以用来简化一些测试。例如Targets.First_Time <= current_time将是 Targets.First_Time <= current_time+n 的子集.

numel(sorted_set_of_times)大约是 40,000

numel(Targets)超过1000万

Answer 1

方法 #1

使用 bsxfun 的矢量化解决方案 -

eqcond = bsxfun(@le,Targets.First_Time,sorted_set_of_times) & bsxfun(@ge,Targets.Last_Time,sorted_set_of_times);
[r,c] = find(eqcond);
for k =1:numel(sorted_set_of_times)
    target_set = r(c==k);
end

使用逻辑索引的建议(如果适用):如果您使用 target_set 索引到某个名为 target 的变量的维度之一>，其长度与该维度的 Targets.First_Time 相同，那么您可以直接索引到 target 的该维度，而不是计算 target_set使用 eqcond(:,ind)，其中 ind 将是该循环中 sorted_set_of_times 的索引。因此，例如，如果您在原始代码中使用 target_set 对 target 的行进行索引，例如 target(target_set,..) , 然后你可以做 target(eqcond(:,ind),..) 代替。

方法 #2

减少数据的方法-

vind = find(Targets.First_Time <= Targets.Last_Time); %//Indices to reduce Targets datasize
Targets.First_Time = Targets.First_Time(vind);
Targets.Last_Time = Targets.Last_Time(vind);
for current_time = sorted_set_of_times;
    target_set = vind([Targets.First_Time] <= current_time & [Targets.Last_Time] >= current_time);
end

方法 #3(方法 #1,2 的混合)

vind = find(Targets.First_Time <= Targets.Last_Time);
Targets.First_Time = Targets.First_Time(vind);
Targets.Last_Time = Targets.Last_Time(vind);
eqcond = bsxfun(@le,Targets.First_Time,sorted_set_of_times) & bsxfun(@ge,Targets.Last_Time,sorted_set_of_times);
[r,c] = find(eqcond);
for k =1:numel(sorted_set_of_times)
    target_set = vind(r(c==k));
end

使用逻辑索引的建议(如果适用):在针对方法 #1 所述的类似讨论中，您也可以为此方法执行逻辑索引。因此，使用与该讨论相同的符号，而不是执行 target(target_set,..)，您可以执行 target(vind(eqcond(:,ind)),..) 。