6

私はここでこの問題を解決するプログラムを作成しています：http：//opc.iarcs.org.in/index.php/problems/BOOKLIST

そして、私がベクトルを使用している唯一の場所は次のとおりです。

for(int i =0;i < total_books; i++){
    int temp;
    cin >> temp;
    books_order.push_back(temp);
}

と

for(int i = 0;i < total_entries; i++){
    int index;
    cin >> index;
    index--;
    cout << books_order[index] << endl;
    books_order.erase(books_order.begin()+index);
}

（これが私の完全なコードです：http：//cpaste.org/1377/）

ベクトルから使用している関数は、vector :: Erase、vector :: push_back、vector::beginのみです。大きな入力の場合、私のコードは3秒以上かかります（これはその問題の制限時間です）が、ベクトル関数を削除すると、はるかに高速に実行されます（もちろん間違った答えが得られます）

この問題でベクトルを使用するのは間違っていること、および私のアルゴリズムが非常に遅いことは理解しましたが、なぜ遅いのか理解できませんでした。

私が使用している機能が遅い理由を知っているなら、私にそれらを説明してください。ありがとうございました。

4

7 に答える 7

10

ベクトルから使用している関数は、vector :: Erase、vector :: push_back、vector::beginのみです。

これがあなたの問題だと思います。vector::eraseはO(n)、他は一定の時間であり、オンラインジャッジの問題で効率の問題を引き起こしてはなりません。消去方法は避けてください。

ただし、一般的に、配列のサイズを事前に知っている場合は、単純な配列を使用します。あなたがそれを助けることができるならば、不必要なオーバーヘッドを加えないでください。

ただし、リンクした問題を解決するには、セットの使用を検討してください。その消去方法はO(log n)、挿入方法と同様です。これは、ランダムな削除が必要な場合に一般的に使用する必要があるものです。

編集： C ++にも優先キューがあることを忘れたので、それらも調べてください。ここでは最大値のみを気にするため、どちらも理論上の複雑さは同じですが、セットよりも高速である可能性があります（ヒープは最小値/最大値を取得O(1)できますが、この問題に対して実行する必要があるのは、それを削除することですO(log n)） 。この場合、どちらも問題なく動作するはずです。

于 2012-10-19T12:36:46.563 に答える
7

IMOが原因はvector::erase、要素を削除した後にすべての要素をシフトするためです。したがって、常に最後の要素を削除しない限り、非常に遅くなる可能性があります。

于 2012-10-19T12:36:32.867 に答える
3

reserveベクトルのサイズを既存の要素の数に合わせて呼び出す必要がない限り、を呼び出すとpush_back、新しいサイズがベクトルの容量を超えるたびにメモリが再割り当てされます。要素に十分なメモリを割り当てるためにを使用することを検討しreserveてください。特にベクトルが大きい場合は、パフォーマンスが向上するはずです。の使用に関する他の回答にも注意してeraseください。

于 2012-10-19T12:35:37.747 に答える
2

ベクトルの中央から（を使用して）要素を削除するのvector::eraseは時間がかかります。これは、削除した要素によって残されたギャップを埋めるために、ベクトルの上位要素をすべて下に移動する必要があるためです。

したがって、これはベクトルが遅い場合ではありませんが、不適切なデータ構造を選択したためにアルゴリズムが遅くなります。

于 2012-10-19T12:36:13.550 に答える
2

あなたの問題は「消去」の呼びかけです。ここでドキュメントを確認すると、次のことに注意してください。

ベクトルは配列形式を保持するため、ベクトルの終わり以外の位置で消去すると、セグメントが消去された後のすべての要素も新しい位置に移動します。これは、他の種類のシーケンスコンテナ（deque、list）での消去ほど効率的な方法ではない場合があります。 。

ループを最後から実行するか、ループの後で消去します。

于 2012-10-19T12:38:48.077 に答える
1

ベクトルに特定の数の要素が事前に含まれていることがわかっている場合は、ベクトル内のスペースの再割り当てを節約するために、すべてを含めるのに十分なスペースを予約できます。

books_order.reserve(total_books)
for(int i=0 ;i < total_books; ++i){
    int temp;
    cin >> temp;
    books_order.push_back(temp);
}

ただし、ここではそれは問題ではありません。コードをプロファイリングした場合、.erase()使用量から大きなオーバーヘッドが発生することは間違いありません。ベクトルの途中から要素を削除するのは遅いです。これは、ベクトルがどのように実装されているかによって、削除された要素の一部であるすべての要素を移動する必要があるためです。代わりに、などの代わりに別のデータ構造を使用することを検討してくださいstd::array。

于 2012-10-19T12:36:14.033 に答える
0

あなたは本当にあなたがしていることを達成するためにベクトルが必要ですか？

ベクトルがどのように機能するかを覚えておく必要があります。ベクトルは基本的に動的配列であり、アイテムを追加するとサイズが変更されます。ベクトルのサイズ変更は、O（n）操作（nはベクトル内のアイテムの数）であり、新しいメモリを割り当て、アイテムを新しいベクトルにコピーします。

ここで、どのベクトルが優れているかについて読むことができます。

代わりに標準の配列を使用することをお勧めします-これは、要素の総数がすでにわかっているので、完全にもっともらしいようです（これはtotal_books）

于 2012-10-19T12:38:08.733 に答える