2

2d ベクトルvector < vector <int> > Nを考えてみましょう。その内容は次のとおりです。

1 1 1 1
2 2 2 2
3 3 3 3
4 4 4 4

したがって、ここでの N のサイズは 4 です。N.size() = 4

ここで、次のコードを検討してください。

int i = 0;
while(N != empty()){
N.erase(i);
++i;
}

N のさまざまなサイズを使用して、このコードだけの時間を計算した結果は次のとおりです。

N のサイズは 1000 実行時間: 0.230000 秒

N のサイズは 10000 実行時間: 22.900000 秒

N のサイズは 20000 実行時間: 91.760000 秒

N のサイズは 30000 実行時間: 206.620000 秒

N のサイズは 47895 実行時間: 526.540000 秒

私の質問は、なぜこの機能がそれほど高価なのですか? そうである場合、多くのプログラムの条件付き消去ステートメントは、この機能のために永遠にかかる可能性があります。で消去機能を使う場合も同様std::mapです。この機能に代わるものはありますか。Boost のような他のライブラリは提供していますか?

N.erase()この機能を分析しようとしているだけなので、全体としてできるとは言わないでください。

4

6 に答える 6

16

ベクトルの最初の要素を削除するとどうなるか考えてみてください。ベクトルの残りの部分は、インデックスを 1 つ下に "移動" する必要があります。これには、コピーが含まれます。反対側から消去してみて、それが違いを生むかどうかを確認してください（私はそうなると思います...）

于 2011-01-11T22:36:22.813 に答える
6

あなたのアルゴリズムはO(n^2)だからです。を呼び出すたびに、消去された要素の後のすべての要素がerase強制的に戻されます。vectorしたがって、4 要素ベクトルを使用したループでは、最初のループで 3 つの要素がシフトされ、2 番目の反復で 1 つの要素がシフトされ、その後は未定義の動作が発生します。

8 つの要素がある場合、最初の反復では 7 つの要素が移動し、次の反復では 5 つの要素が移動し、次の反復では 3 つの要素が移動され、最後の列挙では 1 つの要素が移動されます。（また、未定義の動作があります）

このような状況に遭遇した場合、通常は代わりに標準アルゴリズム (つまりstd::remove, std::remove_if) を使用する必要があります。これは、コンテナーを 1 回実行し、典型的な O(n^2) アルゴリズムを O(n) アルゴリズムに変換するためです。詳細については、Scott Meyers の「有効な STL」項目 43: 明示的なループよりもアルゴリズム呼び出しを優先するを参照してください。

于 2011-01-11T22:38:58.650 に答える
2

std::vector は、内部的には単なる要素の配列です。途中の要素を削除すると、それ以降のすべての要素を下に移動する必要があります。operator=これは非常にコストがかかる可能性があります - 要素に多くの作業を行うカスタムがある場合はなおさらです!

erase()高速である必要がある場合は、 a を使用する必要がありますstd::list- これは、途中から高速に消去できる二重リンク リスト構造を使用します (ただし、他の操作は多少遅くなります)。リストの先頭からすばやく削除する必要がある場合は、 std::deque- を使用すると、配列のリンクされたリストが作成され、 の速度の利点のほとんどが提供されますがstd::vector、最初または最後からのみ高速消去が可能です。

さらに、ループが問題を悪化させることに注意してください。最初に、ゼロに等しいすべての要素をスキャンして消去します。スキャンには O(n) 時間、消去にも O(n) 時間かかります。次に、1 を繰り返します。全体として、O(n^2) 回です。複数の値を消去する必要がある場合は、イテレータstd::listを使用して、 のイテレータ バリアントを使用して自分自身を処理する必要がありますerase()。または、 を使用する場合vectorは、新しいベクターにコピーする方が高速であることがわかります。

std::map(および)に関してstd::setは、これはまったく問題ではありません。std::map要素をランダムに削除することも、時間とともに要素をランダムに検索O(lg n)することもできます。これは、ほとんどの用途にとって非常に合理的です。あなたの単純なループでさえ、それほど悪くはないはずです。std::list削除したいものすべてを 1 回のパスで手動で反復して削除する方がいくらか効率的ですが、友人との場合ほどではありません。

于 2011-01-11T22:39:12.523 に答える
1

vector.erase は、i の後にすべての要素を 1 つ進めます。これは O(n) 操作です。

さらに、ベクトルを参照ではなく値で渡しています。

また、コードはベクトル全体を消去しません。

例: i = 0 消去 N[0] N = {{2, 2, 2, 2}, {3, 3, 3, 3}, {4, 4, 4, 4}}

i = 1 消去 N[1] N = {{2, 2, 2, 2}, {4, 4, 4, 4}}

i = 2 erase N[2] 最大インデックスが N[1] であるため、何も起こりません。

最後に、これは vector.erase() の正しい構文ではないと思います。必要な要素を消去するには、イテレータを開始位置に渡す必要があります。これを試して：

vector<vector<int>> vectors; // still passing by value so it'll be slow, but at least erases everything
for(int i = 0; i < 1000; ++i)
{
    vector<int> temp;
    for(int j = 0; j < 1000; ++j)
    {
        temp.push_back(i);
    }
    vectors.push_back(temp);
}

// erase starting from the beginning
while(!vectors.empty())
{
    vectors.erase(vectors.begin());
}

これを最後からの消去と比較することもできます (特に参照ではなく値を使用する場合は、大幅に高速になるはずです)。

// just replace the while-loop at the end
while(!vectors.empty())
{
    vectors.erase(vectors.end()-1);
}
于 2011-01-11T22:56:08.013 に答える
0

ベクターは、要素を追加すると自動的に大きくなる配列です。そのため、ベクトル内の要素はメモリ内で連続しています。これにより、要素への一定時間のアクセスが可能になります。それらは最後から成長するため、最後に/から追加または削除するには、償却された一定の時間もかかります。

では、途中で外すとどうなるでしょうか？つまり、消去された要素の後に存在するものはすべて、1 つ後ろにシフトする必要があります。これは非常に高価です。

途中で多くの挿入/削除を行いたい場合は、std::deque の std::list などのリンクされたリストを使用します。

于 2011-01-11T22:37:55.320 に答える
0

Oli が言ったように、ベクトルの最初の要素からの消去は、配列が目的どおりに動作するために、それに続く要素をコピーする必要があることを意味します。

これが、要素がリスト内のランダムな場所から削除される状況でリンクされたリストが使用される理由です。コピーがなく、一部のノード ポインターのみがリセットされるため、(より大きなリストでは) 高速です。

于 2011-01-11T22:40:07.883 に答える