私はこの線形検索を最適化しようとしています:
static int
linear (const int *arr, int n, int key)
{
int i = 0;
while (i < n) {
if (arr [i] >= key)
break;
++i;
}
return i;
}
配列はソートされ、関数はキー以上の最初の要素のインデックスを返すことになっています。They 配列は大きくなく (200 要素未満)、多数の検索に対して一度だけ準備されます。n 番目以降の配列要素は、必要に応じて適切なものに初期化できます。これにより、検索が高速化されます。
いいえ、バイナリ検索は許可されていません。線形検索のみが許可されています。
編集: このトピックに関する私の知識はすべて、このブログ投稿にまとめられています。
これまでに複数のアドバイスを受け取りましたが、そのほとんどは、並べ替えられたデータに対して線形検索は意味がなく、代わりにバイナリ検索がはるかに効率的に機能するというものでした。これはしばしば、問題をあまり考えたくない人々によってなされる、人気のある「その通りだ」という主張の 1 つです。実際には、全体像を考えると、適切な状況が与えられた場合、線形検索は二分検索よりもはるかに効率的です。
ソートされた配列に対する単一の検索クエリを考えると、バイナリ検索は線形検索よりもはるかに効率的な方法であることに注意してください。それについての議論はありません。また、同じデータに対して複数の完全にランダムなクエリを実行すると、バイナリ検索が線形検索よりも優先されます。
ただし、シーケンシャルな検索クエリを考慮すると、状況は変わり始めます。これらのクエリは完全にランダムではありません。クエリがソートされた順序で到着すると想像してください。つまり、次の各クエリは前のクエリよりも高い値を求めています。つまり、クエリもソートされます。ところで、それらはグローバルかつ厳密にソートされる必要はありません。時々、クエリ シーケンスが「リセット」される可能性があります。つまり、クエリはseriesで到着し、各シリーズは昇順でソートされます。この場合、シリーズの平均の長さが配列の長さに匹敵する場合、線形検索のパフォーマンスが向上します。大差で二分探索。ただし、この状況を利用するには、検索を段階的に実装する必要があります。簡単です。次のクエリが前のクエリよりも大きい場合、配列の先頭から検索を開始する必要はありません。代わりに、前回の検索が停止したポイントから検索できます。最も単純な実装 (アイデアを説明するため) は次のようになります。
static int linear(const int *arr, int n, int key)
{
static int previous_key = INT_MIN;
static int previous_i = 0;
i = key >= previous_key ? previous_i : 0;
while (i < n) {
if (arr[i] >= key)
break;
++i;
}
previous_key = key;
previous_i = i;
return i;
}
(免責事項: 上記の実装は、以前の検索状態が内部に格納されている一方で、配列がパラメーターとして外部から到着するという明らかな理由から、ひどく醜いです。もちろん、これは実際には間違った方法です。しかし、繰り返しますが、上記はアイデアを説明するためのものであり、それ以上のものではありません)。
上記のアプローチを使用して順序付けられたクエリの各シリーズを処理する複雑O(N)さは、シリーズの長さに関係なく常に であることに注意してください。二分探索を使用すると、複雑さは になりますO(M * log N)。Mしたがって、が に近い場合N、つまり、クエリが十分に長く順序付けられた一連の列で到着する場合の明らかな理由により、上記の線形検索は二分検索よりも大幅に優れたパフォーマンスを発揮しますが、小さいM場合は二分検索が優先されます。
また、順序付けされた一連のクエリがそれほど長くない場合でも、線形検索を使用する必要があることを考えると、上記の変更によって検索パフォーマンスが大幅に向上する可能性があります。
PS問題の構造に関する追加情報として：
長さの順序付けられた配列で検索を実行する必要がありN、クエリが [approximate, average] length の順序付けられた一連の順序で到着することが事前にわかっている場合M、最適なアルゴリズムは次のようになります。
S = [N/M]。の値を 2 の [最も近い] 累乗に "スナップ" することも理にかなっていSます。ソートされた配列を、長さのブロックのシーケンス、SいわゆるSブロックと考えてください。Sです (もちろん、前の検索が中断したブロックから開始することを忘れないでください)。上記は、繰り返し検索の漸近効率の理論的限界を達成するという意味で、可能な限り最適なインクリメンタル検索アルゴリズムです。の値がMよりもはるかに小さい場合、アルゴリズムは「自動的に」二分探索にN移行しますが、アルゴリズムに「自動的に」近づくと、線形探索が優先されることに注意してください。このような環境では、線形検索は二分検索よりもはるかに効率的であるため、後者は理にかなっています。MN
これはすべて、「ソートされた配列の線形検索は常に役に立たない」などの包括的なステートメントは、そのようなステートメントを作成する側の知識の欠如を示しているに過ぎないという事実を説明するためのものです。
まず第一に、高速なソリューションでは、ベクトル化を使用して一度に多くの要素を比較する必要があります。
ただし、これまでに投稿されたすべてのベクトル化された実装には、共通の問題があります。それらには分岐があります。その結果、配列のブロック単位の処理を導入する必要があり (分岐のオーバーヘッドを削減するため)、小さな配列のパフォーマンスが低下します。大規模な配列の場合、線形検索は十分に最適化された二分検索よりも悪いため、最適化しても意味がありません。
ただし、線形検索は分岐なしで実装できます。アイデアは非常に単純です。必要なインデックスは、検索するキーよりも少ない配列内の要素の数です。したがって、配列の各要素をキー値と比較し、すべてのフラグを合計できます。
static int linear_stgatilov_scalar (const int *arr, int n, int key) {
int cnt = 0;
for (int i = 0; i < n; i++)
cnt += (arr[i] < key);
return cnt;
}
このソリューションの面白い点は、配列をシャッフルしても同じ答えが返されることです =) このソリューションはかなり遅いように見えますが、エレガントにベクトル化できます。以下に示す実装では、配列を 16 バイトでアラインする必要があります。また、配列は一度に 16 個の要素を消費するため、INT_MAX 要素でパディングする必要があります。
static int linear_stgatilov_vec (const int *arr, int n, int key) {
assert(size_t(arr) % 16 == 0);
__m128i vkey = _mm_set1_epi32(key);
__m128i cnt = _mm_setzero_si128();
for (int i = 0; i < n; i += 16) {
__m128i mask0 = _mm_cmplt_epi32(_mm_load_si128((__m128i *)&arr[i+0]), vkey);
__m128i mask1 = _mm_cmplt_epi32(_mm_load_si128((__m128i *)&arr[i+4]), vkey);
__m128i mask2 = _mm_cmplt_epi32(_mm_load_si128((__m128i *)&arr[i+8]), vkey);
__m128i mask3 = _mm_cmplt_epi32(_mm_load_si128((__m128i *)&arr[i+12]), vkey);
__m128i sum = _mm_add_epi32(_mm_add_epi32(mask0, mask1), _mm_add_epi32(mask2, mask3));
cnt = _mm_sub_epi32(cnt, sum);
}
cnt = _mm_hadd_epi32(cnt, cnt);
cnt = _mm_hadd_epi32(cnt, cnt);
// int ans = _mm_extract_epi32(cnt, 0); //SSE4.1
int ans = _mm_extract_epi16(cnt, 0); //correct only for n < 32K
return ans;
}
単一の SSE2 レジスタの最終的な削減は、必要な場合にのみ SSE2 で実装できます。全体的なパフォーマンスに実際に影響することはありません。
Intel Core2 Duo E4700 (かなり古いです) 上の Visual C++ 2013 x64 コンパイラでテストしました。サイズ 197 の配列は、rand() によって提供される要素で生成されます。すべてのテストを含む完全なコードはこちらです。32M 検索を実行する時間は次のとおりです。
[OP]
Time = 3.155 (-896368640) //the original OP's code
[Paul R]
Time = 2.933 (-896368640)
[stgatilov]
Time = 1.139 (-896368640) //the code suggested
OP の元のコードは、1 秒あたり 1060 万の配列 (1 秒あたり 21 億要素) を処理します。提案されたコードは、1 秒あたり 2950 万の配列 (1 秒あたり 58 億要素) を処理します。また、提案されたコードは小さな配列でもうまく機能します。15 要素の配列であっても、OP の元のコードよりもほぼ 3 倍高速です。
生成されたアセンブリは次のとおりです。
$LL56@main:
movdqa xmm2, xmm4
movdqa xmm0, xmm4
movdqa xmm1, xmm4
lea rcx, QWORD PTR [rcx+64]
pcmpgtd xmm0, XMMWORD PTR [rcx-80]
pcmpgtd xmm2, XMMWORD PTR [rcx-96]
pcmpgtd xmm1, XMMWORD PTR [rcx-48]
paddd xmm2, xmm0
movdqa xmm0, xmm4
pcmpgtd xmm0, XMMWORD PTR [rcx-64]
paddd xmm1, xmm0
paddd xmm2, xmm1
psubd xmm3, xmm2
dec r8
jne SHORT $LL56@main
$LN54@main:
phaddd xmm3, xmm3
inc rdx
phaddd xmm3, xmm3
pextrw eax, xmm3, 0
最後に、十分に最適化された二分探索は、間隔が短くなるとすぐに説明したベクトル化された線形探索に切り替えることで高速化できることに注意してください。
更新:詳細については、この件に関する私のブログ投稿を参照してください。
最後の有効なエントリの後に既知の値を配置できるため、要素 n+1 = max を追加して、i < n をテストすることなくループが配列の末尾を超えないようにします。
static int
linear (const int *arr, int n, int key)
{
assert(arr[n] >= key);
int i = 0;
while (arr[i] < key) {
++i;
}
return i;
}
同じセンチネル値を使用して、ループを展開することもできます。
static int
linear (const int *arr, int n, int key)
{
assert(arr[n] >= key);
int i = 0;
while (true) {
if (arr [i++] >= key)
break;
if (arr [i++] >= key)
break;
if (arr [i++] >= key)
break;
if (arr [i++] >= key)
break;
}
return --i;
}
ターゲット固有のソリューションが受け入れられる場合は、SIMD（SSE、AltiVec、または利用可能なもの）を非常に簡単に使用して、一度に1つではなく4つの要素をテストすることで、最大4倍の速度向上を実現できます。
興味深いことに、私は次のように簡単なSIMD実装をまとめました。
int linear_search_ref(const int32_t *A, int32_t key, int n)
{
int result = -1;
int i;
for (i = 0; i < n; ++i)
{
if (A[i] >= key)
{
result = i;
break;
}
}
return result;
}
int linear_search(const int32_t *A, int32_t key, int n)
{
#define VEC_INT_ELEMS 4
#define BLOCK_SIZE (VEC_INT_ELEMS * 32)
const __m128i vkey = _mm_set1_epi32(key);
int vresult = -1;
int result = -1;
int i, j;
for (i = 0; i <= n - BLOCK_SIZE; i += BLOCK_SIZE)
{
__m128i vmask0 = _mm_set1_epi32(-1);
__m128i vmask1 = _mm_set1_epi32(-1);
int mask0, mask1;
for (j = 0; j < BLOCK_SIZE; j += VEC_INT_ELEMS * 2)
{
__m128i vA0 = _mm_load_si128(&A[i + j]);
__m128i vA1 = _mm_load_si128(&A[i + j + VEC_INT_ELEMS]);
__m128i vcmp0 = _mm_cmpgt_epi32(vkey, vA0);
__m128i vcmp1 = _mm_cmpgt_epi32(vkey, vA1);
vmask0 = _mm_and_si128(vmask0, vcmp0);
vmask1 = _mm_and_si128(vmask1, vcmp1);
}
mask0 = _mm_movemask_epi8(vmask0);
mask1 = _mm_movemask_epi8(vmask1);
if ((mask0 & mask1) != 0xffff)
{
vresult = i;
break;
}
}
if (vresult > -1)
{
result = vresult + linear_search_ref(&A[vresult], key, BLOCK_SIZE);
}
else if (i < n)
{
result = i + linear_search_ref(&A[i], key, n - i);
}
return result;
#undef BLOCK_SIZE
#undef VEC_INT_ELEMS
}
2.67 GHz Core i7では、OpenSUSEx86-64とgcc4.3.2を使用し7x - 8xて、かなり広い「スイートスポット」（n = 100000）の周りで改善が見られ、キーはアレイの中間点にあります（つまり、結果= n / 2）。3.5xnが大きくなると、パフォーマンスが低下し、アレイがキャッシュサイズを超えます（この場合、おそらくメモリ帯域幅が制限されます）。SIMD実装の非効率性のために、nが小さい場合にもパフォーマンスが低下します（もちろん、nが大きい場合に最適化されています）。
改善のための多くの提案を受け取りましたが、各最適化を測定して、ハードウェアとコンパイラーに最適なものを確認する必要があります。
この例として、この応答の最初のバージョンでは、100〜200の配列要素によって、配列へのプローブをはるかに少なくすることで、バイナリ検索のわずかに高いオーバーヘッドを簡単に支払うことができると推測しました。ただし、以下のコメントで、Mark Probstは、ハードウェア上で最大約500エントリの線形検索が先にあると報告しています。これにより、最高のパフォーマンスを探すときに測定する必要性が高まります。
注：適度に小さいNの線形対二分探索の測定に関する以下のMarkのコメントに従って編集されました。
あなたはそれを並行して行うことができます。
リストが小さい場合は、検索を分割する価値がないかもしれませんが、多数の検索を処理する必要がある場合は、それらを確実に並行して実行できます。これにより、操作の待ち時間は短縮されませんが、スループットは向上します。
このトピックが古いことは承知していますが、投稿せずにはいられませんでした。センチネル線形検索の最適化は次のとおりです。
int sentinel_linear_search(int key, int *arr, int n)
{
int last_value, i;
/* considering that n is the real size of the array */
if (--n < 1)
return -1;
last_value = arr[n];
/* set array last member as the key */
arr[n] = key;
i = 0;
while (arr[i] != key)
++i;
/* recover the real array last member */
arr[n] = last_value;
return (arr[i] == key) ? i : -1;
}
センチネル検索の大きな改善点は、その反復で 2 つ (インデックスとキー) ではなく 1 つの条件分岐 (キー) のみが使用されることです。
while (arr[i] != key)
++i;
Intel プラットフォームを使用している場合:
int linear (const int *array, int n, int key)
{
__asm
{
mov edi,array
mov ecx,n
mov eax,key
repne scasd
mov eax,-1
jne end
mov eax,n
sub eax,ecx
dec eax
end:
}
}
ただし、それは完全一致のみを検索し、以上の一致は検索しません。
C では、 Duff の Deviceも使用できます。
int linear (const int *array, int n, int key)
{
const int
*end = &array [n];
int
result = 0;
switch (n % 8)
{
do {
case 0:
if (*(array++) >= key) break;
++result;
case 7:
if (*(array++) >= key) break;
++result;
case 6:
if (*(array++) >= key) break;
++result;
case 5:
if (*(array++) >= key) break;
++result;
case 4:
if (*(array++) >= key) break;
++result;
case 3:
if (*(array++) >= key) break;
++result;
case 2:
if (*(array++) >= key) break;
++result;
case 1:
if (*(array++) >= key) break;
++result;
} while(array < end);
}
return result;
}
量子コンピューターがあれば、グローバーのアルゴリズムを使用して、O(N 1/2 ) 時間で O(log N) のストレージ スペースを使用してデータを検索できます。そうでなければ、あなたの質問はかなりばかげています。二分探索またはその変形の 1 つ (三分探索など) は、実際には最良の選択です。優れたアルゴリズムを選択できる場合、線形検索でマイクロ最適化を行うのはばかげています。
この回答は他の回答よりも少しわかりにくいので、別に投稿します。これは、C がブール値の結果 false=0 および true=1 を保証するという事実に依存しています。X86 は分岐せずにブール値を生成できるため、高速になる可能性がありますが、テストしていません。このようなマイクロ最適化は、常にプロセッサとコンパイラに大きく依存します。
以前と同様に、呼び出し元は、ループが確実に終了するように、配列の末尾にセンチネル値を配置する必要があります。
ループ展開の最適な量を決定するには、いくつかの実験が必要です。リターンが減少する (または負の) ポイントを見つけたいと考えています。SWAGを取って、今度は8にしてみます。
static int
linear (const int *arr, int n, int key)
{
assert(arr[n] >= key);
int i = 0;
while (arr[i] < key) {
i += (arr[i] < key);
i += (arr[i] < key);
i += (arr[i] < key);
i += (arr[i] < key);
i += (arr[i] < key);
i += (arr[i] < key);
i += (arr[i] < key);
i += (arr[i] < key);
}
return i;
}
編集:マークが指摘するように、この関数は、前の行の各行に依存関係を導入します。これにより、プロセッサ パイプラインが操作を並行して実行する機能が制限されます。そこで、関数を少し変更して依存関係を削除してみましょう。これで、関数は実際に最後に 8 つのセンチネル要素を必要とします。
static int
linear (const int *arr, int n, int key)
{
assert(arr[n] >= key);
assert(arr[n+7] >= key);
int i = 0;
while (arr[i] < key) {
int j = i;
i += (arr[j] < key);
i += (arr[j+1] < key);
i += (arr[j+2] < key);
i += (arr[j+3] < key);
i += (arr[j+4] < key);
i += (arr[j+5] < key);
i += (arr[j+6] < key);
i += (arr[j+7] < key);
}
return i;
}
ループのアンローリングと同様の n チェックを回避できます
static int linear(const int *array, int arraySize, int key)
{
//assuming the actual size of the array is always 1 less than arraySize
array[arraySize] = key;
int i = 0;
for (; ; ++i)
{
if (array[i] == key) return i;
}
}
固定配列インデックスで展開します。
int linear( const int *array, int n, int key ) {
int i = 0;
if ( array[n-1] >= key ) {
do {
if ( array[0] >= key ) return i+0;
if ( array[1] >= key ) return i+1;
if ( array[2] >= key ) return i+2;
if ( array[3] >= key ) return i+3;
array += 4;
i += 4;
} while ( true );
}
return -1;
}
uint32 LinearFindSse4( uint8* data, size_t data_len, uint8* finddata, size_t finddatalen )
{
/**
* the following is based on...
* #define haszero(v) (((v) - 0x01010101UL) & ~(v) & 0x80808080UL)
* we split it into 2 sections
* first section is:
* (v) - 0x01010101UL)
*
* second section is:
* ~(v) & 0x80808080UL)
*/
__m128i ones = _mm_set1_epi8( 0x01 );
__m128i eights = _mm_set1_epi8( 0x80 );
__m128i find_field = _mm_set1_epi8( finddata[0] );
uint32 found_at = 0;
for (int i = 0; i < data_len; i+=16)
{
#define CHECKTHIS( n ) if (!memcmp(&data[i+n], &finddata[0], sizeof(finddata))) { found_at = i + n; break; }
__m128i chunk = _mm_stream_load_si128( (__m128i *)&data[i] );
__m128i xor_result = _mm_xor_si128( chunk, find_field );
__m128i first_sec = _mm_sub_epi64( xor_result, ones );
__m128i second_sec = _mm_andnot_si128( xor_result, eights );
if(!_mm_testz_si128(first_sec, second_sec))
{
CHECKTHIS(0);
CHECKTHIS(1);
CHECKTHIS(2);
CHECKTHIS(3);
CHECKTHIS(4);
CHECKTHIS(5);
CHECKTHIS(6);
CHECKTHIS(7);
CHECKTHIS(8);
CHECKTHIS(9);
CHECKTHIS(10);
CHECKTHIS(11);
CHECKTHIS(12);
CHECKTHIS(13);
CHECKTHIS(14);
CHECKTHIS(15);
}
}
return found_at;
}
一度に int よりも大きな要素を検索できます。具体的には、プラットフォームでは、読み取られたより大きなデータの処理方法に応じて、これははるかに高速または低速になる可能性があります。たとえば、64 ビット システムでは、一度に 2 つの要素を配列に読み込み、hi/low 要素を個別にチェックすると、I/O が少なくなるため、実行速度が向上する可能性があります。それでも、これは何があっても O(n) 種類の並べ替えです。
逆方向にループ、これは翻訳されるかもしれません...
// loop backward
for (int i = arraySize - 1; i >=0; --i)
...これに（「もっと」速くなる可能性があります）：
mov cx, arraySize - 1
detectionHere:
...
loop detectionHere
それ以外は、バイナリ検索のみが検索を高速化できます
これにより、ベクトル命令が強制される可能性があります (Gman が推奨):
for (int i = 0; i < N; i += 4) {
bool found = false;
found |= (array[i+0] >= key);
...
found |= ( array[i+3] >= key);
// slight variation would be to use max intrinsic
if (found) return i;
}
...
// quick search among four elements
これにより、分岐命令も少なくなります。入力配列が 16 バイト境界に揃えられていることを確認することで助けになります
ベクトル化に役立つ可能性のある別のこと (垂直方向の最大比較を行う):
for (int i = 0; i < N; i += 8) {
bool found = false;
found |= max(array[i+0], array[i+4]) >= key;
...
found |= max(array[i+3], array[i+7] >= key;
if (found) return i;
}
// have to search eight elements
コメントの 1 つで、配列の長さは 64 であると述べました。
直線的に行う必要がある場合は、次のことができます。
int i = -1;
do {
if (arr[0] >= key){i = 0; break;}
if (arr[1] >= key){i = 1; break;}
...
if (arr[62] >= key){i = 62; break;}
if (arr[63] >= key){i = 63; break;}
} while(0);
しかし、それがこの二分探索よりも速いかどうかは真剣に疑問です: *
int i = 0;
if (key >= arr[i+32]) i += 32;
if (key >= arr[i+16]) i += 16;
if (key >= arr[i+ 8]) i += 8;
if (key >= arr[i+ 4]) i += 4;
if (key >= arr[i+ 2]) i += 2;
if (key >= arr[i+ 1]) i += 1;
*Jon Bentley に感謝します。
追加：このテーブルは多数の検索に対して一度準備され、高速が必要だと言ったので、どこかにスペースを割り当てて、値が組み込まれたマシンコードを生成できます。線形検索または二分検索のいずれかです。バイナリの場合、マシン コードは、コンパイラがこれから生成するもののようになります。
if (key < value32){
if (key < value16){
...
}
else {
...
}
}
else {
if (key < value48){
...
}
else {
...
}
}
次に、それを呼び出すことができる場所にコピーするだけです。
または、上記のコードを印刷し、オンザフライでコンパイルして dll にリンクし、dll をロードすることもできます。
実際には、この質問に対する答えは、コードを書いているプラットフォームに 100% 依存しています。例えば：
CPU : Memory speed | Example CPU | Type of optimisation
========================================================================
Equal | 8086 | (1) Loop unrolling
------------------------------------------------------------------------
CPU > RAM | Pentium | (2) None
さて、あなたはポインタを使うことができます...
static int linear(const int *array, int arraySize, int key) {
int i;
for(i = 0; i < arraySize; ++i) {
if(*array >= key) {
return i;
}
++array;
}
return arraySize;
}