3

次元 の行列を考えてみましょうNx2。各行には一様 PDF (つまり、確率密度関数) の下限と上限が含まれます。

オーバーラップの数をカウントしたいのですが、オーバーラップは 2 つの PDF がオーバーラップしている状態として定義されます。

  • PDF1:[2,5]
  • PDF2:[3,6]
  • 2 つの PDF は間隔で重なり合っています[3,5]。

明らかに、3 つの PDFp1とが重複p2している場合、 vs. 、vs. 、vs . の3つのp3重複をカウントします。p1p2p1p3p2p3

オーバーラップをカウントする次の 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ます。で 3 時間前に実行を開始しましたN=10000が、まだ実行中です。

アプリオリにいくつかの比較を除外して、提案されたアルゴリズムの複雑さを軽減する方法を提案できますか?

前もって感謝します。

4

2 に答える 2

3

先に残したコメントを取り消します。間違いなく短時間でできます。Rody と Shoelzer が提供するリンクに基づいて、次のコードを使用してこの操作を 1 秒以内に実行できます。

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()反復ごとに 4 回呼び出していることにある可能性があります。代わりに、すべてのデータを一度に取得して、比較を行う前に配列に格納してみてください。

その後、Possible Interview Question: How to Find All Overlapping Intervals への回答で説明されている手法を使用します。

于 2013-09-04T13:11:53.977 に答える