3

配列のすべてのメンバーが同じ値に設定されているかどうかをテストするための STL アルゴリズムまたは高速な手法はありますか?

たとえば、デフォルト値を持つ配列があります。

bool *finishFlags  =new (std::nothrow) bool[numOfBools];

    //Init all to false:

for(int i = 0 ; i < numOfBools; ++i){
   *finishFlags++ = false;
}

現在、実行時に一部の配列メンバーが true に設定されており、それらすべてが同じ値 (この場合は true) に設定されているかどうかをテストしたいと考えています。典型的な配列反復なしでそれを行う高速な方法はありますか?

4

6 に答える 6

7

カウンターを保持し、フラグが true または false に切り替わるように加算/減算します。それからif ctr == numOfBools、またはctr == 0それらはすべて同じです。

編集：チェックが必要であることを追加する必要があるため、ブール値がすでにオフになっている場合は減算したり、既にオンになっている場合は追加したりしません。

于 2013-08-25T14:15:32.173 に答える
3

コレクションの構築中にメタデータを保存および更新していない限り、これには配列の反復が必要になるため、すべてのソリューションは O(N) になります。

ただし、単一命令の複数データ アーキテクチャ (Intel の SSE、ARM の Neon など) を使用してベクトル化することで、ループの反復回数を大幅に削減できる可能性があります。これは、データがアライメントされていて、SIMD ストライドの倍数である場合に最適に機能します。それ以外の場合は、エンド エフェクトを処理する必要があります。また、これを自動的に行うコンパイラもあります。

考慮すべきもう1つのことは、早期終了です。たとえば、count_of別の回答で言及されている関数は、最初の 2 つの要素が異なっていても、常に配列全体を反復処理します。つまり、明示的な反復を使用した単純なアプローチと比較すると、最適化が解除されています。

于 2013-08-25T14:14:58.343 に答える
2

all_of適切な条件でご使用いただけます。

または、count、count_if、find_if、any_ofをnone_ofこの目的に使用することもできます。countバリエーションは早期に終了しないため、常に配列全体を反復処理します。

反復ベースの方法が必要ない場合は、2 つのかなりハックな方法を考えることができます。

  1. 挿入の追跡 -num_true挿入またはセットを作成するたびに変更されるカウント。後でこれを使用して、状態を確認できます。
  2. それが純粋な配列である場合memcmp、すべて真の配列と比較して同一であるかどうかを確認するためにいくつかのことを行うことができます。これはわずかに速いかもしれません。
于 2013-08-25T14:09:52.507 に答える
1

それを自動的に行う機能があるのか​​もしれません。

ただし、とにかく配列の各メンバーをテストする必要があるため、反復ソリューションよりも高速になることはありません

于 2013-08-25T14:09:35.333 に答える
1

ループを使用してすべてのオブジェクトを反復処理し、それらをチェックする必要があります。

ループの最適化でパフォーマンスを改善できる場合があります。

それに加えて、データがコンテナー内に存在し (ポインターなし)、アーキテクチャーがそれを許可する場合、SSEベクトル化を使用して全体的なパフォーマンスを向上させることができます。

于 2013-08-25T14:14:38.187 に答える
0

アレイへのアクセスをカプセル化することでアレイのステータスをキャッシュし、true に設定されているエントリの数を記録できます。

配列を false に初期化するときは、カウンタを 0 に設定します。エントリが false から true に変わるたびにカウンタをインクリメントし、エントリが true から false になるとカウンタをデクリメントします。

これで、配列がすべて true、すべて false、または混合であるかどうかを 1 回のテストで確認できます。

于 2013-08-25T14:18:38.477 に答える