これは非常に素朴な方法です。(午前 4 時のせん妄に起因する疑似コードのバグはご容赦ください ;)
//4x sorted subsets
data[4][4] = {
{3, 4, 5, INF},
{2, 7, 8, INF},
{1, 4, 4, INF},
{5, 8, 9, INF}
}
data_offset[4] = {0, 0, 0, 0}
n = 4*3
for(i=0, i<n, i++):
sub = 0
sub = 1 * (data[sub][data_offset[sub]] > data[1][data_offset[1]])
sub = 2 * (data[sub][data_offset[sub]] > data[2][data_offset[2]])
sub = 3 * (data[sub][data_offset[sub]] > data[3][data_offset[3]])
out[i] = data[sub][data_offset[sub]]
data_offset[sub]++
編集:
AVX2 とその収集サポートにより、一度に最大 8 つのサブセットを比較できました。
編集 2:
タイプ キャストによっては、Nehalem での反復ごとに 3 余分なクロック サイクルを削減できる可能性があります (mul: 5、shift+sub: 4)
//Assuming 'sub' is uint32_t
sub = ... << ((data[sub][data_offset[sub]] > data[...][data_offset[...]]) - 1)
編集 3: 2 つ以上の値
を使用することで、特に K が大きくなるにつれて、順不同の実行をある程度悪用できる可能性があります。max
max1 = 0
max2 = 1
max1 = 2 * (data[max1][data_offset[max1]] > data[2][data_offset[2]])
max2 = 3 * (data[max2][data_offset[max2]] > data[3][data_offset[3]])
...
max1 = 6 * (data[max1][data_offset[max1]] > data[6][data_offset[6]])
max2 = 7 * (data[max2][data_offset[max2]] > data[7][data_offset[7]])
q = data[max1][data_offset[max1]] < data[max2][data_offset[max2]]
sub = max1*q + ((~max2)&1)*q
編集4:
コンパイラのインテリジェンスに応じて、三項演算子を使用して乗算を完全に削除できます。
sub = (data[sub][data_offset[sub]] > data[x][data_offset[x]]) ? x : sub
編集5:
コストのかかる浮動小数点比較を避けるためreinterpret_cast<uint32_t*>()
に、整数比較になるため、データを単純化することができます。
もう 1 つの可能性は、型付けされていない SSE レジスタを利用し、整数比較命令を明示的に使用することです。
これ< > ==
は、バイナリ レベルで float を解釈するときに演算子が同じ結果を生成するために機能します。
編集6:
値の数を SSE レジスタの数に一致させるためにループを十分に展開すると、比較対象のデータをステージングできます。
反復の最後に、選択した最大値/最小値を含むレジスタを再転送し、それをシフトします。
これには索引付けを少しやり直す必要がありますが、ループに を散らかすよりも効率的であることが証明される場合がありますLEA
。