25

問題

A と B という名前の間隔の 2 つのコレクションがあるとします。どのようにすれば、最も時間効率とメモリ効率の高い方法で差 (相対的補数) を見つけることができるでしょうか?

説明用の画像: ここに画像の説明を入力

区間終点は整数( ≤ 2 128 -1 ) であり、常に 2 nの長さで、m×2 n格子上に配置されます (したがって、それらから二分木を作成できます)。

間隔は入力でオーバーラップできますが、これは出力には影響しません (平坦化された場合の結果は同じになります)。

問題は、両方のコレクションに多くの間隔 (最大 100,000,000) があるため、単純な実装はおそらく遅くなるということです。

入力は 2 つのファイルから読み取られ、小さなサブ間隔 (重複している場合) がサイズ順に親の直後になるように並べ替えられます。例えば：

[0,7]
[0,3]
[4,7]
[4,5]
[8,15]
...

私は何を試しましたか？

これまでのところ、私は二分探索木を生成する実装に取り​​組んできました。その際[0,3],[4,7] => [0,7]、両方のコレクションから隣接する間隔 (必要に応じて最初のツリーの間隔)。

これは小さなコレクションでは機能しているように見えますが、ツリーへの挿入とツリーからの削除を完了するのに必要な時間は言うまでもなく、ツリー自体を保持するためにより多くの RAM が必要になります。

間隔は事前にソートされているため、動的アルゴリズムを使用して 1 回のパスで終了できると考えました。ただし、これが可能かどうかはわかりません。

では、この問題を効率的に解決するにはどうすればよいでしょうか。

免責事項：これは宿題ではなく、私が直面している実際の現実の問題の修正/一般化です. 私は C++ でプログラミングしていますが、任意の [命令型] 言語のアルゴリズムを受け入れることができます。

4

4 に答える 4

9

私たちが学校で最初に行ったプログラミング演習の 1 つ、電卓プログラムの作成を思い出してください。入力行から算術式を取得し、解析して評価します。括弧の深さを追跡したことを覚えていますか? それでは、行きましょう。

類推: 区間の始点は開き括弧、終点は閉じ括弧です。括弧の深さ (ネスト) を追跡します。二の深さ - 間隔の交点、一の深さ - 間隔の差

アルゴリズム：

  • A と B を区別する必要はありません。すべての始点と終点を昇順に並べ替えるだけです。
  • 括弧の深さカウンターをゼロに設定します
  • 最小のものから始めて、エンドポイントを反復します。開始点の場合は深度カウンターをインクリメントし、終了点の場合はカウンターを減算します
  • 深さが 1 の間隔を追跡します。これらは A と B の差の間隔です。深さ2の区間はAB交点
于 2012-08-09T22:14:52.327 に答える
7

あなたの間隔は素晴らしいですソートされています。これは、メモリをほとんど使用せずに線形時間で実行できます。

2 つのセットを「平らにする」ことから始めます。これはセット A の場合で、最小の間隔から開始し、重なりのない間隔セットになるまで、重なり合う間隔を組み合わせます。次に、B に対してそれを行います。

今あなたの 2 つのセットを取り、最初の 2 つの間隔から始めます。これらを A と B、Ai と Bi の区間インデックスと呼びます。

Ai は A の最初の間隔、Bi は B の最初の間隔にインデックスを付けます。

処理する間隔がありますが、次のことを行います。

両方の間隔の開始点を検討してください。開始点は同じですか? 両方の間隔の開始点を小さい方の間隔の終了点に進める場合、出力には何も出力しません。小さい間隔のインデックスを次の間隔に進めます。(つまり、Ai が Bi の前に終了した場合、Ai は次のインターバルに進みます。) 両方のインターバルが同じ場所で終了した場合、Ai と Bi の両方を進め、何も出力しません。

一方の開始点は他方の開始点よりも早いですか? その場合、前の開始点から a) 後のエンドポイントの開始点、または b) 前のエンドポイントの終わりまでの間隔を発行します。オプション b を選択した場合は、前の間隔のインデックスを進めます。

たとえば、Ai の間隔が最初に開始する場合、Ai の開始から Bi の開始まで、または Ai の終了のいずれか小さい方までの間隔を発行します。Ai が Bi の開始前に終了した場合、Ai を進めます。

すべての間隔が消費されるまで繰り返します。

Ps。2 つの間隔セットを別々のバッファーにフラット化するための予備のメモリがないことを前提としています。これを 2 つの関数で実行します。必要に応じて平坦化を行い、平坦化されたデータを差分関数に供給する間隔インデックスを進める「次の間隔を取得」関数。

于 2012-08-09T20:25:57.440 に答える
5

あなたが探しているのはSweep line algorithmです。単純なロジックで、スイープ ラインが A と B の両方の間隔と交差するとき、および 1 つのセットのみと交差する場所がわかります。

これは、この問題とよく似ています。B のセグメントの終点を通る一連の垂直線があると考えてください。

このアルゴリズムの複雑さは、初期ソートのコストである O((m+n) log (m+n)) です。ソート済みセットのスイープ ライン アルゴリズムは O(m+n) かかります

于 2012-08-09T20:26:49.067 に答える
2

boost.icl (Interval Container Library) http://www.boost.org/doc/libs/1_50_0/libs/icl/doc/html/index.htmlを使用する必要があると思います 

#include <iostream>
#include <boost/icl/interval_set.hpp>

using namespace boost::icl;

int main()
{
  typedef interval_set<int> TIntervalSet;
  TIntervalSet intSetA;
  TIntervalSet intSetB;

  intSetA += discrete_interval<int>::closed( 0, 2);
  intSetA += discrete_interval<int>::closed( 9,15);
  intSetA += discrete_interval<int>::closed(12,15);

  intSetB += discrete_interval<int>::closed( 1, 2);
  intSetB += discrete_interval<int>::closed( 4, 7);
  intSetB += discrete_interval<int>::closed( 9,10);
  intSetB += discrete_interval<int>::closed(12,13);

  std::cout << intSetA << std::endl;
  std::cout << intSetB << std::endl;

  std::cout << intSetA - intSetB << std::endl;

  return 0;
}

これは印刷します

{[0,2][9,15]}
{[1,2][4,7][9,10][12,13]}
{[0,1)(10,12)(13,15]}
于 2012-08-12T12:34:32.383 に答える