これは私がずっと前に遭遇した問題です。私はあなたのアイデアを聞いてもいいと思いました。高速に並べ替える必要がある、4 つまたは 8 つの要素の非常に小さな数 (整数) のリストがあるとします。最良のアプローチ/アルゴリズムは何ですか?
私のアプローチは、最大/最小関数を使用することでした（4つの数字をソートする10個の関数、分岐なし、iirc）。
// s(i,j) == max(i,j), min(i,j)
i,j = s(i,j)
k,l = s(k,l)
i,k = s(i,k) // i on top
j,l = s(j,l) // l on bottom
j,k = s(j,k)
私の質問は、アルゴリズムの種類ではなく、実装に関係していると思います。
この時点でハードウェア依存になるので、SSE3 を搭載した Intel 64 ビット プロセッサを想定します。
ありがとう
このような小さな配列の場合は、おそらくネットワークの並べ替えを検討する必要があります。そのページでわかるように、挿入ソートはソートネットワークとして表現できます。ただし、アレイのサイズが事前にわかっている場合は、最適なネットワークを考案できます。このサイトを見て、特定のサイズの配列に最適な並べ替えネットワークを見つけることができます (ただし、最適なサイズは 16 までしか保証されていないと思います)。コンパレータは、並行して実行できる操作にグループ化されています。コンパレータは基本的に s(x,y) 関数と同じですが、これを本当に高速にしたい場合は、必要な比較回数の 2 倍を行うため、min と max を使用しないでください。
この並べ替えアルゴリズムが幅広いサイズで機能する必要がある場合は、他の人が示唆しているように、おそらく挿入並べ替えを使用する必要があります。
少量の数値を並べ替えるには、単純なアルゴリズムが必要です。複雑になるとオーバーヘッドが増えるからです。
たとえば 4 つのアイテムを並べ替える最も効率的な方法は、並べ替えアルゴリズムを線形比較に分解して、すべてのオーバーヘッドを排除することです。
function sort(i,j,k,l) {
if (i < j) {
if (j < k) {
if (k < l) return [i,j,k,l];
if (j < l) return [i,j,l,k];
if (i < l) return [i,l,j,k];
return [l,i,j,k];
} else if (i < k) {
if (j < l) return [i,k,j,l];
if (k < l) return [i,k,l,j];
if (i < l) return [i,l,k,j];
return [l,i,k,j];
} else {
if (j < l) return [k,i,j,l];
if (i < l) return [k,i,l,j];
if (k < l) return [k,l,i,j];
return [l,k,i,j];
}
} else {
if (i < k) {
if (k < l) return [j,i,k,l];
if (i < l) return [j,i,l,k];
if (j < l) return [j,l,i,k];
return [l,j,i,k];
} else if (j < k) {
if (i < l) return [j,k,i,l];
if (k < l) return [j,k,l,i];
if (j < l) return [j,l,k,i];
return [l,j,k,i];
} else {
if (i < l) return [k,j,i,l];
if (j < l) return [k,j,l,i];
if (k < l) return [k,l,j,i];
return [l,k,j,i];
}
}
}
ただし、アイテムを追加するたびにコードが大きくなります。5 番目の項目を追加すると、コードは約 4 倍大きくなります。項目が 8 つあると、およそ 30000 行になるため、最も効率的ではありますが、コードが多くなり、正しいコードを作成するプログラムを作成する必要があります。
5 つの比較を使用するソリューションが既にあるようです (s(i,j) が 2 つの数値を 1 回比較し、それらを交換するかどうかのいずれかであると仮定します)。比較ベースの並べ替えに固執する場合、5 回未満の比較では実行できません。
4つあるから証明できる！= 4 つの数字を注文する 24 通りの方法。それぞれの比較は可能性を半分にすることしかできないため、4 つの比較では 2^4 = 16 の可能な順序しか区別できません。
挿入ソートは、小さな配列に最適であると考えられています。小さな配列の高速安定ソート (32 または 64 要素未満) を参照してください。
このような小さなデータ セットの場合は、できるだけ単純なアルゴリズムが必要です。ほとんどの場合、基本的なInsertion Sortで十分に機能します。
これが実行されているシステム、1秒間にこのソートを何回行う必要があるかなどについてもっと知る必要があります...しかし、小さなソートの一般的なルールは、単純に保つことです。クイックソートなどは役に立ちません。
ソート ネットワークは SIMD で簡単に実装できますが、N = 16 あたりから見苦しくなり始めます。N = 4 または N = 8 の場合、これは良い選択ですが。理想的には、同時に並べ替えるには多数の小さなデータ セットが必要です。つまり、8 ビット値を並べ替える場合、少なくとも 16 個のデータ セットを並べ替える必要があります。SIMD ベクトル全体でこの種のことを行うのははるかに困難です。