6

私がやりたいのは、インターバルを効率的に処理することです。たとえば、私の例では、間隔は次のようになります。

[10, 20], [15, 25], [40, 100], [5, 14]

間隔は閉じて整数であり、一部の間隔は省略されている場合があります。特定のクエリの重複する間隔を効率的に見つけたい。たとえば、[16, 22]が与えられた場合：

[10, 20], [15, 25]

上記の間隔は、過大な間隔として計算する必要があります。

私は現在、赤黒木に基づいた区間木を書いています（参照：CLRS、アルゴリズムの概要）。重複するすべての間隔を見つけることはO（n）ですが、実行時間はより速くなるはずです。間隔は削除および挿入できることに注意してください。

interval_mapただし、Boostには次のものがあることがわかりましたinterval_set： http ：//www.boost.org/doc/libs/1_46_1/libs/icl/doc/html/index.html

試してみましたが、動作がおかしいです。たとえば、[2, 7]が最初に[3, 8]挿入されてから挿入された場合、結果のマップには、、、[2, 3)および[3, 7]が含まれ(7, 8]ます。つまり、新しい間隔が挿入されると、分割が自動的に行われます。

この機能をオフにできますか？または、Boostinterval_mapは私の目的に適していますか？

4

3 に答える 3

5

重複を効率的に見つけることができるデータ構造を求めました。これは、データ構造にオーバーラップを格納することによって行われます。今、あなたはそれがそうしていると不平を言っているようです。

この例では、ロジックについて説明します。

typedef std::set<string> guests;
interval_map<time, guests> party;
party += make_pair(interval<time>::right_open(time("20:00"), time("22:00")),
guests("Mary"));
party += make_pair(interval<time>::right_open(time("21:00"), time("23:00")),
guests("Harry")); 
// party now contains
[20:00, 21:00)->{"Mary"} 
[21:00, 22:00)->{"Harry","Mary"} //guest sets aggregated on overlap
[22:00, 23:00)->{"Harry"}

2つの重複する間隔を追加すると、実際には、異なるプロパティを持つ3つの間隔が作成されます。オーバーラップは両方の元の間隔にあり、元の間隔のいずれかと論理的に異なる間隔にします。そして、2つの元の間隔は、異なるプロパティ（元の間隔と重なるものと重ならないもの）を持つ時間にまたがるようになりました。この分割により、オーバーラップはマップ内の独自の間隔であるため、オーバーラップを効率的に見つけることができます。

いずれにせよ、Boostでは間隔の組み合わせスタイルを選択できます。したがって、オーバーラップを見つけにくくする構造を強制したい場合は、そうすることができます。

于 2011-11-02T02:32:30.960 に答える
2

ブーストinterval_mapとinterval_setを試してみました。それらは非常に非効率的です。実装は基本的に各サブインターバル（交差）をそれを含むすべてのインターバルにマッピングするため、セットアップコストは非常に高くなります。

赤黒木に基づくCLRS「アルゴリズム入門」での実装ははるかに優れていると思います。std::setとstd::mapがRBツリーに基づいているにもかかわらず、拡張を可能にする赤黒木実装がそこにないのは奇妙です。

于 2012-07-12T17:55:10.597 に答える
1

を使用できると思いますinterval_map<int, set<discrete_interval<int> > >。間隔を追加するときはいつでも、マップにI追加するだけです。ここで、は。のみを含みます。したがって、上記の例では、次のようにします。make_pair(I, II)IIsetI

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

using namespace boost::icl;

typedef std::set<discrete_interval<int> > intervals;

intervals singleton(const discrete_interval<int> &value) {
    intervals result = { value };
    return result;
}

int main() {
    interval_map<int, intervals> mymap;
    discrete_interval<int> i1 = discrete_interval<int>(2, 7);
    discrete_interval<int> i2 = discrete_interval<int>(3, 8);
    mymap.add(make_pair(i1, singleton(i1)));
    mymap.add(make_pair(i2, singleton(i2)));

    for (int i = 0; i < 10; ++i) {
        std::cout << "i: " << i << ", intervals: " << mymap(i) << std::endl;
    }
}

ブーストのドキュメントは、このページの下部にあるsのaninterval_mapは特に効率的ではないことを示唆していることに注意してください。したがって、これは、セットコンセプトの独自の実装を作成するか、とは異なる実装を使用することをお勧めします。std::setstd::set

于 2011-11-02T14:56:50.477 に答える