4

4 つの異なる場所で停止しているサービスがあります。各ロケーションの停止を Boost ICL interval_set にモデル化しています。少なくとも N か所でアクティブな停止がいつ発生するかを知りたいです。

したがって、この回答に従って、組み合わせアルゴリズムを実装したので、 interval_set 交差点を介して要素間の組み合わせを作成できます。

このプロセスが終了したら、特定の数の interval_set が必要で、それぞれが同時に N か所の停止を定義します。最終ステップは、それらを結合して目的の全体像を取得することです。

問題は、現在コードをデバッグしていて、各交差点を印刷する時間になると、出力テキストがおかしくなり (gdb を使用して段階的にデバッグしている場合でも)、それらが表示されないことです。その結果、多くの CPU 使用率が発生します。

どういうわけか、必要以上に多くのメモリを出力するために送信していると思いますが、どこに問題があるのか​​ わかりません。

これは SSCCE です。

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


int main() {
    // Initializing data for test
    std::vector<boost::icl::interval_set<unsigned int> > outagesPerLocation;
    for(unsigned int j=0; j<4; j++){
        boost::icl::interval_set<unsigned int> outages;
        for(unsigned int i=0; i<5; i++){
            outages += boost::icl::discrete_interval<unsigned int>::closed(
                (i*10), ((i*10) + 5 - j));
        }
        std::cout << "[Location " << (j+1) << "] " << outages << std::endl;
        outagesPerLocation.push_back(outages);
    }

    // So now we have a vector of interval_sets, one per location. We will combine
    // them so we get an interval_set defined for those periods where at least
    // 2 locations have an outage (N)
    unsigned int simultaneusOutagesRequired = 2;  // (N)

    // Create a bool vector in order to filter permutations, and only get
    // the sorted permutations (which equals the combinations)
    std::vector<bool> auxVector(outagesPerLocation.size());
    std::fill(auxVector.begin() + simultaneusOutagesRequired, auxVector.end(), true);

    // Create a vector where combinations will be stored
    std::vector<boost::icl::interval_set<unsigned int> > combinations;

    // Get all the combinations of N elements
    unsigned int numCombinations = 0;
    do{
        bool firstElementSet = false;
        for(unsigned int i=0; i<auxVector.size(); i++){
            if(!auxVector[i]){
                if(!firstElementSet){
                    // First location, insert to combinations vector
                    combinations.push_back(outagesPerLocation[i]);
                    firstElementSet = true;
                }
                else{
                    // Intersect with the other locations
                    combinations[numCombinations] -= outagesPerLocation[i];
                }
            }
        }
        numCombinations++;
        std::cout << "[-INTERSEC-] " << combinations[numCombinations] << std::endl;  // The problem appears here
    }
    while(std::next_permutation(auxVector.begin(), auxVector.end()));

    // Get the union of the intersections and see the results
    boost::icl::interval_set<unsigned int> finalOutages;
    for(std::vector<boost::icl::interval_set<unsigned int> >::iterator
        it = combinations.begin(); it != combinations.end(); it++){
        finalOutages += *it;
    }

    std::cout << finalOutages << std::endl;
    return 0;
}

何か助けはありますか？

4

2 に答える 2

3

置換ループの最後に、次のように記述します。

numCombinations++;
std::cout << "[-INTERSEC-] " << combinations[numCombinations] << std::endl;  // The problem appears here

私のデバッガーは、インクリメント前の最初の反復numCombinations では0 だったと教えてくれます。しかし、それをインクリメントすると、combinationsコンテナの範囲外になりました（これは単一の要素にすぎないため、インデックスが0であるため）。

使用後にインクリメントするつもりでしたか？使用しない特別な理由はありましたか

std::cout << "[-INTERSEC-] " << combinations.back() << "\n";

または、c++03 の場合

std::cout << "[-INTERSEC-] " << combinations[combinations.size()-1] << "\n";

または単に：

std::cout << "[-INTERSEC-] " << combinations.at(numCombinations) << "\n";

どちらが投げたstd::out_of_rangeでしょうか？

余談ですが、 Boost ICL には、求めている答えを得る非常に効率的な方法があると思います。ちょっと考えさせてください。私がそれを見たら、別の答えを投稿します。

更新： Boost ICLを使用した高レベルコーディングのケースを示す他の回答を投稿しました

于 2015-02-04T19:57:25.407 に答える