0

そのため、さまざまなグラフで多くの DFS を実行するというプログラミング コンテストの問題がありました。

最初に、グラフ (隣接リスト表現) をセットのベクトルとして表現しました。

vector< set<int> > graph;

また、空のセットを使用するたびに、指定されたノード数に従ってグラフを初期化するには:

set<int> tmpSet;

そして、私はそれを次のように初期化しました:

for(int j=0;j<N;j++)//N was the number of nodes needed for the graph
   graph.push_back(tmpSet);

そして私は使った

graph.clear();

毎回グラフを空にします。

後でエッジを挿入するには、std::set の挿入機能を使用しました。

//Insert directed edge from u to v
graph[u].insert(v);
graph[v].insert(u);

その結果、プログラムは大量のメモリを消費し、遅すぎてテストに合格できませんでした。一定時間の操作である push_back 関数を使用して std::list でも同じことが起こりました。次に、std::vector に変更すると、メモリ消費量が最小限になり、3 秒でテストに合格しましたが、std::set と std::list は 20 秒でもテストに合格できませんでした。

私の疑問は、それが内部セットとリストのスペースを解放することと関係があるということですが、なぜベクトルの動作が異なるのでしょうか?

だから私の質問は、なぜこれが起こったのかを誰かが説明できるかどうかです。そうすれば、別のコンテナ内にコンテナがあるような状況で stl コンテナがどのように動作するかをよりよく理解できます。

編集: いくつかの追加情報: ノードの数は約 N=3000 で、テストの数は 1000 を超えていました。つまり、1000 を超えるグラフをすべて変数「グラフ」に保持する必要がありました。また、set は O(lgn) 時間で挿入され、ベクトルとリストは O(1) にあることを認識しているため、set がvector よりも少しだけ長くかかる理由を理解しています。しかし、なぜ std::list も失敗したのでしょうか? また、set と list は 100Mb のメモリ使用量で終了し、vector は 3Mb で終了したことにも触れておきます。

最後の編集では、グラフ (リスト バージョン) をどのように使用しているかを正確に示すコードを次に示します。プログラムの他の場所では、メモリの解放やグラフ データの変更は行われません。

vector< list<int> > graph;
list<int> tmpList;
int T; //num of test cases
int N; //num of nodes
int M; //num of edges
int main ()
{
    int u,v;
    scanf("%d",&T);//Read test cases
    for(int i=0;i<T;i++){

        scanf("%d %d",&N,&M);//Read number of nodes and number of edges
        for(int j=0;j<N;j++)
            graph.push_back(tmpList);

        for(int j=0;j<M;j++){
            scanf("%d %d",&u,&v);//Read edge from u to v
            graph[u].push_back(v);
            graph[v].push_back(u);
        }
        dfs();
        graph.clear();
    }
}
4

3 に答える 3

2

std::set隣接するノード番号を保持するために使用すると、遅い対数時間で要素を挿入して取得します。しかし、std::vector insert(push_back) を使用して要素を取得すると、一定の時間で行われるため、時間の差が生じます。したがってstd::vector、セット内の要素を見つける必要がない場合に使用し、それ以外の場合に使用する必要がありstd::setます。

std::list との違いstd::vectorは機能によるものかもしれませんclear。それlistは線形ですが、vector原子化された定数です。

于 2013-04-10T12:03:56.283 に答える
1

セットで注文。指定したファンクターに従って、特定の順序にとどまることが保証されます。どの要素を追加または削除しても (セットで許可されていない重複を追加しない限り)、常に順序付けられます。

ベクトルには、明示的に指定した順序のみがあります。ベクトル内のアイテムは、それらを置く場所です。それらを順不同にすると、順不同になります。コンテナを並べ替えて、順番に戻す必要があります。

確かに、セットの用途は比較的限られています。適切な規律があれば、アイテムをベクトルに挿入して順序を保つことができます。ただし、コンテナーにアイテムを頻繁に挿入したり削除したりしている場合、ベクターは多くの問題に遭遇します。事実上単なる配列であるため、要素のコピー/移動などを多数実行します。

ベクトルに項目を挿入するのにかかる時間は、ベクトルに既にある項目の数に比例します。アイテムをセットに挿入するのにかかる時間は、アイテム数の対数に比例します。アイテムの数が多い場合、それは大きな違いです。Log(100,000) は 5 です。これは大幅な速度の向上です。取り外しも同様です。

ただし、初期化時に一度にすべての挿入を行う場合、問題はありません。ベクトルにすべてを挿入し、並べ替え (その代価を 1 回支払う) し、並べ替えられたベクトルの標準アルゴリズムを使用して要素を検索し、並べ替えられたリストを反復処理することができます。また、セットの要素に対する反復処理は必ずしも遅くはありませんが、ベクトルに対する反復処理は高速です。

そのため、ソートされたベクトルがセットよりも優れている場合があります。そうは言っても、必要であることがわかっていない限り、この種の最適化の費用を気にするべきではありません。したがって、作成している種類のシステムの経験がない (したがって、そのパフォーマンスが必要であることを知っている) か、セットではなくベクトルが必要であることを示すプロファイリング データを手元に持っていない限り、セットを使用してください。

于 2013-04-10T12:09:46.627 に答える