6

小さな質問があります。LARGE unsigned char 配列内の特定の要素と、unsigned char 要素のみを含むベクトルをスキャンする最も速い方法は何ですか? 率直な答えは素晴らしいですが、詳細な詳細な答えは素晴らしいでしょう。高速とはどういう意味ですか? 基本的には、少なくとも 1 秒以内に特定の文字を検索します。私はそれがあまり教育を受けた定義ではないことを知っています...

注: 配列はソートされていません。

共通宣言:

unsigned char* Array = new unsigned char[ 50000 ];
std::vector< unsigned char > Vec( 50000 );
/*
 * Fill Array & Vec with random bytes
 */

たとえば、配列で文字「a」を検索したい場合、次のループを記述して検索します。

注: 検索プロセスでは、複数の要素が検索されます。主に 256 です。したがって、そのマジック ナンバーを利用できます。

ループ方式の場合:

unsigned int Count = 0;
for ( unsigned int Index = 0; Index != 50000; ++ Index )
   if( Array[ Index ] == 'a' ) Count ++;

std::count メソッド:

unsigned int Count = std::count ( Array, Array + 50000, 'a' );

配列内の特定の要素を検索するより高速な方法はありますか?

いくつかのアイデア - これについて私に親指を立てないでください! その唯一のアイデア。意見が欲しいです。

並べ替え

Array のコピーを作成して並べ替えると、速度が向上しますか? なぜコピーを作るのですか？元のコンテンツを保持する必要があるためです。目標は、基本的に文字の出現をスキャンしてカウントすることです。スピードが重要であることを忘れないでください。つまり、コピープロセスは高速でなければなりません。

Answer: No and its not worth it!

なんで？さて、これを読んでみましょう：

@キリルキーロフ：

依存します。単一の文字を検索する場合は、絶対にそうではありません。配列のコピーはコストのかかる操作です。それを並べ替える - さらに高価です。

配列が 1 つだけで、たとえば 100 個の異なる文字を検索する場合、この方法を使用するとパフォーマンスが向上する可能性があります。さて、これはあなたの使い方に大きく依存します。そして、この場合、誰もあなたに絶対に正しい答えを与えることはできません. それを実行してプロファイルする必要があります。

*詳細については、@Kiril Krov の有益な投稿までスクロールしてください。

回答: 特に SORTED でない場合に、この目標を達成するための本当に「速い」方法がないため、これまでのところ確実な答えはありません。ただし、スレッドは可能な解決策になる可能性があります。ただし、CPU には注意してください。これは@Andreaの提出された回答に基づいていました（詳細については、もう少し下にスクロールしてください）-正しく読んでほしいと思いました。

4

6 に答える 6

4

「速い」とはどういう意味ですか？

複雑さの点で高速ですか、それとも定数による改善ですか? ソートされていない配列では、複雑さを向上させることはできません。ただし、配列をめったに変更せず、頻繁に検索する場合は、変更のたびに並べ替えを検討するか、別のデータ構造 ( amultimapや a などset) を使用することをお勧めします。

より良い定数を使用する場合は、O(n)、CPUのキャッシュを使用/悪用する巧妙なトリックがいくつかあります。複数の要素を検索する場合は、一般に、検索用語ごとに配列全体をスキャンするよりも、文字ごとに最初の数百の配列要素を検索し、次に数百の配列要素を検索する方が高速です。改善は複雑ではないため、通常、効果はそれほど大きくありません。この検索が、他のアルゴリズムの奥深くで繰り返されるボトルネックで発生しない限り、お勧めしません。したがって、レンダリング アルゴリズム、デバイス ドライバー、または 1 つの特定のアーキテクチャなどの内部にない限り、おそらく価値はありません。ただし、まれに適切な場合もありますが、インライン アセンブリを使用して CPU キャッシュを悪用することで、3 倍から 4 倍以上の速度向上が見られました。

編集：

あなたのコメントは、データ構造についての簡単な紹介を含めることをお勧めします。

  • 配列、ベクトル: 最速のアクセス、低速の検索、低速の追加/削除 (最後に追加されていない場合)。
  • リスト: アクセスが遅い、検索が遅い、追加/削除が速い
  • ツリー、ハッシュ テーブルなど:最良の検索(検索を許可するものもありますO(0)!)、遅い変更 (タイプによって異なります)

C++ のさまざまなデータ構造 (ベクトル、リスト、マップ、マルチマップ、セット、マルチセットなど) について学習することをお勧めします。これにより、ニーズに最も適したものを使用できます。

CPU キャッシュについて: 適切なデータ構造とコード編成を選択することがより重要なようです。ただし、完全を期すためにこれを含めます。配列全体を一度に検索するのではなく、短いチャンクで配列を検索すると、配列のその部分が CPU のキャッシュに追加され、キャッシュへのアクセスは RAM へのアクセスよりもはるかに高速になります。そのため、データのその小さなチャンク (複数の要素を検索するなど) で作業してから、データの次のチャンクに切り替えることができます。これは、例えば、

search "a" in elements 1..100
search "b" in elements 1..100
search "c" in elements 1..100
search "a" in elements 101..200
search "b" in elements 101..200
search "c" in elements 101..200
...
search "c" in elements 999901 .. 1000000

よりも速くすることができます

search "a" in elements 1..1000000
search "b" in elements 1..1000000
search "c" in elements 1..1000000

検索された要素 (a、b、c、..) の数が十分に多い場合。なんで？キャッシュサイズが100の場合、最初の例では10000回、2番目の例では30000回RAMからデータが読み込まれるためです。

ただし、これの効率 (およびデータ チャンク サイズの選択) はアーキテクチャに大きく依存するため、これが実際のボトルネックであることが確実な場合にのみ推奨されます。通常はそうではありません。

于 2013-03-21T08:32:25.713 に答える
4

最適なアルゴリズムは です。O(n)ここnで、 は要素の数です。

各要素をチェックする必要があるため、配列全体を調べる必要があります。

私が考えることができる簡単な方法は、すでにあなた自身の答えに書かれています。

そして、これを行うためのより速い方法はありません-メモリは連続しており、配列はソートされておらず、各要素に「触れる」必要があります。それが最速の解決策です。

あなたの編集に関して：std::count配列を使用して「手動で」ループすると、同じパフォーマンスが得られます。

配列内の特定の要素を検索するより高速な方法はありますか

はい、配列がソートされている場合。まで達成できますO( log(n) )。次に、バイナリ検索などの既存の検索アルゴリズムが必要になります。

Array のコピーを作成して並べ替えると、速度が向上しますか?

依存します。単一の文字を検索する場合は、絶対にそうではありません。配列のコピーはコストのかかる操作です。それを並べ替える - さらに高価です。

配列が 1 つだけで、たとえば 100 個の異なる文字を検索する場合、この方法を使用するとパフォーマンスが向上する可能性があります。さて、これはあなたの使い方に大きく依存します。そして、この場合、誰もあなたに絶対に正しい答えを与えることはできません. それを実行してプロファイルする必要があります。

于 2013-03-21T08:05:41.383 に答える
3

それに応じて、1回のスキャンまたは複数回のスキャンです。並べ替えはスキャン速度を大幅に向上させます。bisearch でいつでもスキャンを絞り込むことができます。複雑さは O(log(n)) になる可能性があります。

または、挿入から始めてスキャンする配列を構築できる場合は、挿入が遅いが常にソートされる赤黒ツリーを使用できます。

最後になりましたが、要素の数が制限されている「unsigned char array」をスキャンしているまさにその質問についてです。1 回のスキャンを実行できますが、より多くのメモリが必要です。 unsigned char 配列内の各要素の値を、スキャン結果を格納するために使用される別の配列のインデックスとして使用します。

すべての要素の位置が必要な場合、他の配列は次のようになります: int scanresult[256][n]、n は特定の char の数の最大数です。

配列内の 'a' の数だけをカウントする必要がある場合、他の配列は次のようになります: int scanresult[256]、これを例に取ります。複雑さは O(n) ですが、実行する必要があるのは 1 回だけです:

unsigned char* Array = new unsigned char[ 50000 ];
/* Fill Array */
int scanresult[256];
for ( int i=0;i<256;++i) { scanresult[i]=0; }
for ( unsigned int Index = 0; Index != 50000; ++ Index )
   scanresult[Array[Index]]++;
于 2013-03-21T08:40:31.970 に答える
2

1文字の検索の場合、std::countおそらく最速です。また、データのセットが小さい場合 (および 50000 個) は小さいため、とにかく時間に気付くことはほとんどありません。もちろん、単一の文字の場合、ほとんどの合理的なアルゴリズムは、データの読み取りにかかる時間よりも短い時間で済みます。（std::countベクトルまたはCスタイルの配列の50000要素では、最新のマシンでは瞬時に近くなります。とにかく、「少なくとも1秒」よりも桁違いです。）

より高速に処理したい場合の解決策は、最初から配列を作成するのではなく、データの読み取り中にオンザフライで処理を行うことです (または、 を介して配列をすぐに取得します mmap)。複数の文字のデータが必要な場合は、データを読みながら文字頻度表を作成してください。そして、データを読み取る最速の方法を見つけます (mmap少なくとも最近行ったいくつかの対策によれば、Linux ではほぼ確実です)。その後、カウントが必要なときにこのテーブルにインデックスを付けるだけです。データの読み取りは O(n) になります (それを回避する方法はありません)。しかし、その後、カウントを取得するのは O(1) であり、定数係数も非常に非常に小さくなります (多くのマシンでは 1 ナノ秒未満)。 ）。

于 2013-03-21T09:05:17.600 に答える
0

忘れないでください、unsigned char > 0 && unsigned char <= 256...

#define MAX 50000 

unsigned char* Array = new unsigned char[ MAX ];
unsigned int Logs[ 256 ];

// Fill Array

::memset( &Logs, 0, sizeof( Logs ) * 256 );
for( unsigned int Index = 0; Index != MAX; ++ Index )
   Logs[ Array[ Index ] ] ++;

delete [] Logs;
于 2013-03-21T08:51:52.540 に答える