3

n個の整数間隔（たとえば、{1-5}、{4-16}、{6434-114343}）を持つ巨大なデータベーステーブルがあり、どの間隔が互いに重複しているかを調べる必要があります。SOについても同様の質問がたくさんあります が、違いは、間隔ごとに、重複する間隔のセットを返す必要があることです。

      ------------------ A -------------------
    ------ B -------               ----- D -----
          --------- C ---------

この例では、出力は次のようになります。A:{B,C,D} B:{A,C} C:{A,B} D:{A}

最悪の場合、すべての間隔が互いに重なり合い、サイズO（n 2）の出力が生成される可能性があります。これは単純な解決策よりも優れています（間隔のすべてのペアを比較してください）。ただし、実際には、自分の間隔のいくつかが他の間隔と重なることはわかっていますが、重なる場合は、他の5つの間隔までしか重なりません。

この情報を前提として、どのように問題を解決する必要がありますか？（最適には、データがデータベースにあるため、SQLクエリソリューションが必要ですが、通常のアルゴリズムソリューションのみが可能だと思います。）

4

2 に答える 2

8

問題の一般的なプログラムによる解決策は、すべての範囲から区間ツリーを構築し、区間ごとに1つのルックアップを実行することです。これにより、時間内に交差するすべての区間のリストが得られますO(log n)。このような区間木がどのように見えるかのサンプルを次に示します。

区間木サンプル

ただし、この場合、主キーもツリーノードに格納するため、次の日付を指定します（重複する日付を見つけることは、区間木で解決できる一般的な問題です）。

サンプルの日付間隔

あなたの木はこのようになります

日付間隔のサンプルツリー

したがって、どの区間がCと重複しているかを知りたい場合は、1843年のCの開始点を検索すると、この値は、テストしている区間である区間C内にのみあることがツリーに示されます。それを無視することができます。次に、1907年のCの終わりを検索すると、ツリーは、それがA、B、およびCの間隔にあることを示します。ここでも、Cを無視できるため、結果セットはAおよびBになります。

確かに、そのようなツリーでのルックアップは、予想されるほど直感的ではありません。ここでは、できる限り詳しく説明します。最上位のルートノードから開始し、各ノードで、Leaveノード（子がもうないノード）に到達するまで、左に移動するか右に移動するかを決定します。ノードの値が検索している値よりも大きい場合は、左に移動します。ノード値が検索している値よりも小さい場合は、右に移動します。ノードの値が検索している値と正確に等しい場合はどうなりますか？場合によります！間隔の開始を検索する場合、等しい値は右に移動することを意味し、間隔の終了を検索する場合、等しい値は左に移動することを意味します。これは非常に重要です。脱退ノードに到達すると、完了し、任意のノードで見つかったすべての間隔が完了しますその脱退ノードに向かう途中で、脱退ノード自体に格納されている間隔（存在する場合）を含めて、脱退ノードに格納されている間隔だけでなく、結果セットを構成します。つまり、検索の実行中に遭遇した間隔を収集する必要があります。

最初の質問に戻りましょう。これはすべてSQLで実行できますか？はい、できます。でも、本当にやりたいのかわかりません。現在のSQLテーブルデータを間隔ツリーを表すSQLテーブルに変換してから、その間隔ツリーテーブルで直接ルックアップを実行できます。少なくとも私はまさにそれをした人を見つけました。彼は、データベース内の既存のすべての範囲と日付を比較することなく、特定の日付をカバーするすべての日付範囲を見つけようとします。

静的関係区間木

彼は巧妙なトリックを使用して、ルックアップの速度を最適化し、両方のCPU使用率を大幅に削減し、ルックアップテーブルを作成し、実際のルックアップを実行します（これにより全体が非常に複雑になります）。

于 2013-01-08T12:29:56.513 に答える
2

間隔の開始と終了のソートされたシーケンスを作成し、それをトラバースします。現在の間隔のリストを更新するたびに、新しく見つかった交差点を報告します。

このようなもの：

std::vector<TBorder> borders;
for(auto i=intervals.begin();i!=intervals.end();++i)
{
    borders.push_back(TBorder(i.Start(),Start));
    borders.push_back(TBorder(i.End(),End));
}
std::sort(borders.begin(),borders.end());
std::set<int> currentIntervals;
for(auto b=borders.begin();b!=borders.end();++b)
{
    if(b.IsEnd())
        currentIntervals.erase(b.IntervalIndex());
    else
    {
        currentIntervals.insert(b.IntervalIndex());
        if(currentIntervals.size()>1)
            ReportIntersection(currentIntervals);
    }
}

一般的にはO（n * log n）です（交差点の数がO（1）であると仮定します）。

ただし、たとえばstartでソートされた区間がすでにある場合は、O（n）でソートを実行できる可能性があります（ここでも、交差の数がO（1）であると想定しています）。

于 2013-01-08T12:49:05.917 に答える