配列内の結果を検索する最速の方法

Question

私は64バイトの値を含む配列を検索するアルゴリズムを持っており、4ビットの値を見つけて配列に何回出現するかを見たいと思います。たとえば、配列の最初の要素は10101010で、4ビットの値は1010で、これは1回だけカウントされます。次の要素が10000000の場合、これは0とカウントされます。配列内のすべての要素を調べ、4ビットの結果があれば各要素をチェックするのは簡単ですが、これを行う方法がより速いのですか？

Answer 1

precompute: 
- 4bit key offset by 0bit 
- 4bit key offset by 1bit 
- 4bit key offset by 2bit 
- 4bit key offset by 3bit 

- 4 bit mask offset by 0bit 
- 4 bit mask offset by 1bit 
- 4 bit mask offset by 2bit 
- 4 bit mask offset by 3bit 

for each byte in bytes: 
    for each offset: 
    mask out bytes we care about 
    check if it matches our precomputed key 

• 我々は見ていない任意の項目が一致またはない可能性がありますので、我々はすべての項目を見ているので、少なくともO(n)。
• すべての項目を一度見るだけで十分なので、非線形アルゴリズムを使用する理由はありません。
• 合計64個なので、高度に最適化されたSIMD命令は恐らく面倒ではありません。パフォーマンスを向上させる可能性は低いです。

---

キーとマスクの事前計算は、キーをシフトすることによって行われる時、及びマスクに1〜4つの関連ビットを設定することにより、1ビットを残しました。いくつかのkeyとオフセット0-3のそれぞれについて、

match = (bytes[i] & (0x0F << offset)) == (key << offset) 

。 (key << offset)と(0x0F << offset)は4つのループごとに再利用されるため、4つの値を事前に計算してループを展開する方が高速になります。あなたのコンパイラがこれを行うかもしれませんが、そうでない場合は手動で行う方法です：

matches = 0 
for (int i = 0; i < 64; i += 4) { 
    const mask0 = 0x0F << 0 
    const key0 = key << 0 
    match0 = (bytes[i+0] & mask0) == key0 

    const mask1 = 0x0F << 1 
    const key1 = key << 1 
    match1 = (bytes[i+1] & mask1) == key1 

    ... 

    matches += match0 + match1 + match2 + match3 
}