1

固定数の符号なし整数を含むstd::vectorsの非常に大きなstd::vectorがあります。

uintのすべてのベクトルは、昇順で並べ替えられます。

重複するベクトルを排除する私の現在の方法は

unsigned int i = 0;
while ( i < new_combs.size() )
{
  unsigned int j = i + 1;
  while ( j < new_combs.size() )
  {
     unsigned int k = 0;
     while ( k < new_combs.at(i).size() && new_combs.at(i).at(k) == new_combs.at(j).at(k) )
        ++k;
     if ( k == new_combs.at(j).size() )
        new_combs.erase(new_combs.begin() + j);
     else
        ++j;
  }
  ++i;
}

ここで、new_combsは、上記のベクトルを含むベクトルです。

ベクトルのベクトルがソートされていない場合、重複を排除するためのより効率的な方法はありますか？

4

6 に答える 6

9

より短い方法は次を使用すること<algorithm>です：

std::sort(new_combs.begin(), new_combs.end());
new_combs.erase(std::unique(new_combs.begin(), new_combs.end()), new_combs.end());

を特に必要としない限り、重複を避けるためにstd::vectorを使用できます。std::set

于 2012-04-10T12:16:42.807 に答える
3

std::set の使用を検討しましたか? 順序付けられており、重複を許可しません。

于 2012-04-10T12:17:35.350 に答える
2

ベクトルがソートされていない場合、できることはあまりありません。ただし、ソートされている場合は、アルゴリズムで定義された独自の方法を使用できます。

new_combs.erase(unique(new_combs.begin(), new_combs.end()), new_combs.end());
于 2012-04-10T12:17:51.647 に答える
0

コードには、パフォーマンスに関して警鐘を鳴らす要素がいくつかあります。

まず、ベクトルを使用しています。ベクトルからの要素の消去は常に低速です。別のコンテナー (std::list) の使用を検討するか、コードを調整して、特別な値 (0 または -1 など) を持たないようにすることができます。

次に、std::set または std::unordered_set を使用して、既に遭遇した値を保持できます。そうすれば、ベクトルを 1 回ループするだけで済みます。

編集：この答えは忘れてください。私は質問を読み違え、重複した値 (重複したベクトルではない) を削除する必要があると考えました。

それにもかかわらず、与えられたコメントに対するいくつかの反応：

  • @Jerry: ほとんどの場合、ベクトルはリストよりも高速ですが、ベクトルのサイズが制限されている場合に限ります。ベクトルに 100 万個の要素が含まれていて、3 番目、5 番目、10 番目を削除する必要がある場合、多くの要素を移動することになります。そのような場合、リストの方が高速になる可能性があります。
  • @ジェームズ：元の質問では、要素はベクトルの最後から削除されたのではなく、途中で削除されました。ベクトルが非常に大きい場合 (100 万要素としましょう)、要素の削除が依然としてボトルネックになる可能性があります。ただし、並べ替えを使用するよりも同意し、その後に一意を使用する方がおそらく高速です。
于 2012-04-10T12:19:15.920 に答える
0

漸近的に、アルゴリズムは通常の O(n) 実装のように見えるため、最適です。i( andを使用した対角化戦略を理解していませんでしjたが、要素を削除するだけで要素を移動しない理由。コードは非常に不明確です。) ただし、STL を複製しており、unique-ing ループの短いバージョンは次のとおりです。 :

struct unique {
    template <class C>
    void operator()( C& c ) {
         c.erase( std::unique( c.begin(), c.end() ), c.end() );
    }
};

std::for_each( new_combs.begin(), new_combs.end(), unique() );
于 2012-04-10T12:19:50.413 に答える
0

Luchian Grigore の答えに同意しますが、外側全体vectorを に変換することも検討してください。unordered_setソート用）。不必要なコピーを避けるために、内のサブベクトルへのポインターを使用することもできます。unordered_setこれは、大量のデータの場合に重要なパフォーマンスの違いになる可能性があります。

この例は、独自のハッシュ関数とポインターを使用する基本的な考え方を示しています (これはvectorof を扱い、 ではなくstringを使用しますが、必要に応じてかなり簡単に変更できるはずです)。unordered_mapunordered_set

于 2012-04-10T13:09:12.103 に答える