3

考虑一个维度为 的矩阵Nx2，其中每一行包含统一 PDF 的下限和上限（即概率密度函数）。

我想计算重叠的数量，其中重叠定义为两个 PDF 重叠的情况，例如：

  • PDF1：[2,5]
  • PDF2：[3,6]
  • 两个 PDF 在区间内重叠[3,5]。

显然，如果三个 PDF和p1重叠，我计算三个重叠：vs. ，vs. ，vs. 。p2p3p1p2p1p3p2p3

我创建了以下计算重叠的 MATLAB 代码：

for m = 1:N-1
    for k = m+1:N
        l1 = dataService.getObjectCoordinate(m,1);
        l2 = dataService.getObjectCoordinate(k,1);
        u1 = dataService.getObjectCoordinate(m,2);
        u2 = dataService.getObjectCoordinate(k,2);
        if (l1 <= l2 && l2 <= u1) || (l2 <= l1 && l1 <= u2)
            numOverlaps = numOverlaps + 1;
        end
    end
end

但是，正如您可以想象的那样O(N^2)，它是 ，当它很大时，它是非常糟糕N的。我在三个小时前开始执行N=10000，它仍在运行。

您能否提出一种降低所提出算法复杂性的方法，也许排除一些先验比较？

提前致谢。

4

2 回答 2

3

我收回我之前留下的评论。你绝对可以在更短的时间内做到这一点。根据 Rody 和 Shoelzer 提供的链接，您可以使用以下代码在一秒钟内完成此操作

tic
numIntervals = 10000;
ranges = sort(randi(100,[numIntervals,2]),2);
[vals,idx] = sort(ranges(:,1));
ranges = ranges(idx,:);
overlaps = false(numIntervals);
for i = 1:numIntervals
    temp = [ranges(:,1) <= ranges(i,2),ranges(:,1) >= ranges(i,1)];
    overlaps(:,i) = logical(all(temp,2));
end
overlaps = tril(overlaps,-1);
toc

ranges将是您的间隔起点和终点的数组。

最后的下三角形部分的目的是删除任何重复的对。如果P1重叠P2那么显然P2会重叠P1。它还将P1通过删除对角线来消除重叠的事实

运行大量数据时要非常小心，因为它使用的存储量会很快填满您的 RAM，具体取决于您拥有的数量。我尝试将所有内容都保留为逻辑数组以帮助解决此问题，但它仍然会快速增加。

您绝对可以删除存储部分并为自己节省大量时间，但是您必须立即处理每个循环中的所有内容。

于 2013-09-04T13:29:15.867 回答
1

你分析过你的代码吗？问题的很大一部分可能是您dataService.getObjectCoordinate()每次迭代调用了四次。相反，尝试一次获取所有数据并将其存储在数组中，然后再进行任何比较。

之后，使用可能的面试问题的答案中描述的技术：如何找到所有重叠的时间间隔。

于 2013-09-04T13:11:53.977 回答