私はバイト配列を持っていて、特定のバイトの最初の出現（もしあれば）を見つけたいと思っています。
皆さんはそれを行うための素晴らしい、エレガントで効率的な方法で私を助けてくれますか？
/// Summary
/// Finds the first occurance of a specific byte in a byte array.
/// If not found, returns -1.
public int GetFirstOccurance(byte byteToFind, byte[] byteArray)
{
}
public static int GetFirstOccurance(byte byteToFind, byte[] byteArray)
{
return Array.IndexOf(byteArray,byteToFind);
}
見つからない場合は-1を返します
または、Samが指摘したように、拡張メソッドは次のとおりです。
public static int GetFirstOccurance(this byte[] byteArray, byte byteToFind)
{
return Array.IndexOf(byteArray,byteToFind);
}
またはそれを一般的にするために：
public static int GetFirstOccurance<T>(this T[] array, T element)
{
return Array.IndexOf(array,element);
}
次に、あなたはただ言うことができます：
int firstIndex = byteArray.GetFirstOccurance(byteValue);
効率についておっしゃっていたので、ネイティブアドレス指定と最大のqwordに合わせた読み取りを使用して、メモリアクセスの数を8分の1に削減する、高度に最適化されたC＃コードをいくつか示します。 .NETのメモリ内のバイトをスキャンします。
これは、オフセット（アドレスに対して）で始まり、長さ.まで続く、メモリの範囲内で最初に出現するバイト'v'のインデックスを返します。バイトが見つからない場合は-1を返します。isrccv
// fast IndexOf byte in memory. (To use this with managed byte[] array, see below)
public unsafe static int IndexOfByte(byte* src, byte v, int i, int c)
{
ulong t;
byte* p, pEnd;
for (p = src + i; ((long)p & 7) != 0; c--, p++)
if (c == 0)
return -1;
else if (*p == v)
return (int)(p - src);
ulong r = v; r |= r << 8; r |= r << 16; r |= r << 32;
for (pEnd = p + (c & ~7); p < pEnd; p += 8)
{
t = *(ulong*)p ^ r;
t = (t - 0x0101010101010101) & ~t & 0x8080808080808080;
if (t != 0)
{
t &= (ulong)-(long)t;
return (int)(p - src) + dbj8[t * 0x07EDD5E59A4E28C2 >> 58];
}
}
for (pEnd += c & 7; p < pEnd; p++)
if (*p == v)
return (int)(p - src);
return -1;
}
あなたが見る1つの掛け算に驚かないでください。最終的なdeBruijnルックアップを実行するために、この関数の呼び出しごとに最大1回だけ実行されます。そのために使用される読み取り専用ルックアップテーブルは、64バイト値の単純な共有リストであり、1回限りの初期化が必要です。
// elsewhere in the static class...
readonly static sbyte[] dbj8 =
{
7, -1, -1, -1, -1, 5, -1, -1, -1, 4, -1, -1, -1, -1, -1, -1,
-1, -1, -1, -1, -1, -1, -1, -1, 6, -1, -1, -1, -1, -1, -1, -1,
-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
-1, -1, -1, 3, -1, -1, -1, -1, -1, -1, 1, -1, 2, 0, -1, -1,
};
必要に応じて、前の-1テーブル初期化コードの次の代替案に示すように、値にアクセスすることはなく、必要に応じてゼロのままにすることができます。
static MyStaticClass()
{
dbj8 = new sbyte[64]; // initialize the lookup table (alternative to the above)
dbj8[0x00] = 7;
dbj8[0x18] = 6;
dbj8[0x05] = 5;
dbj8[0x09] = 4;
dbj8[0x33] = 3;
dbj8[0x3C] = 2;
dbj8[0x3A] = 1;
/* dbj8[0x3D] = 0; */
}
readonly static sbyte[] dbj8, dbj16;
完全を期すために、元の質問でOPによって提供されたメソッドプロトタイプで関数を使用する方法を次に示します。
/// Finds the first occurrence of a specific byte in a byte array.
/// If not found, returns -1.
public static unsafe int GetFirstOccurance(byte byteToFind, byte[] byteArray)
{
fixed (byte* p = byteArray)
return IndexOfByte(p, byteToFind, 0, byteArray.Length);
}
ディスカッション
私のコードは少し複雑なので、興味のある読者のための演習として詳細な調査が残されています。.NET内部メソッドBuffer.IndexOfByteでギャングワイズメモリ検索の一般的なアプローチに関する別の見方を研究できますが、そのコードには私のものと比較して重大な欠点があります。
t1 != 0.NETコードには、チェックで誤検知が発生する「パフォーマンスリーク」があり、後続の4つのチェックが無駄になります。「フォールスルー」の場合に注意してください。この誤検知のため、正確性を維持するために、3回ではなく、4回の最終チェックが必要です。0x7efefeffまたはの使用によって証明される0x81010100）と、最上位バイトに関する情報の「左方向への出力」（つまり、損失）が発生します。これがここでの実際の問題です。対照的に、私はアンダーフロー計算を使用して、各バイトの計算を隣接するバイトから独立させます。私の方法では、誤検知や「フォールスルー」処理がなく、すべてのケースで決定的な結果が得られます。if-elseを混乱させる可能性があるためです。この問題は、8バイトのスキャナーにとってより重要です。ルックアップを使用しないと、4バイトのギャングワイズスキャナーと比較して、最終チェックで2倍の条件が発生するためです。if-elseもちろん、この細かな点すべてに関心がない場合は、コードをコピーして使用するだけです。私はそれをかなり徹底的にユニットテストし、すべての整形式の入力に対して正しい動作を検証しました。したがって、コア機能を使用する準備ができている間に、引数チェックを追加することをお勧めします。
[編集：]
String.IndexOf（String s、Char char、int ix_start、int count） ...高速です！
上記の方法は私のプロジェクトで非常にうまく機能したので、16ビット検索をカバーするように拡張しました。これは、の代わりに16ビットのshort、ushort、またはcharプリミティブを検索するように適合された同じコードですbyte。この適応された方法は、上から適応された独自のそれぞれの単体テスト方法論に対しても独立して検証されました。
static MyStaticClass()
{
dbj16 = new sbyte[64];
/* dbj16[0x3A] = 0; */
dbj16[0x33] = 1;
dbj16[0x05] = 2;
dbj16[0x00] = 3;
}
readonly static sbyte[] dbj16;
public static int IndexOf(ushort* src, ushort v, int i, int c)
{
ulong t;
ushort* p, pEnd;
for (p = src + i; ((long)p & 7) != 0; c--, p++)
if (c == 0)
return -1;
else if (*p == v)
return (int)(p - src);
ulong r = ((ulong)v << 16) | v;
r |= r << 32;
for (pEnd = p + (c & ~7); p < pEnd; p += 4)
{
t = *(ulong*)p ^ r;
t = (t - 0x0001000100010001) & ~t & 0x8000800080008000;
if (t != 0)
{
i = dbj16[(t & (ulong)-(long)t) * 0x07EDD5E59A4E28C2 >> 58];
return (int)(p - src) + i;
}
}
for (pEnd += c & 7; p < pEnd; p++)
if (*p == v)
return (int)(p - src);
return -1;
}
以下は、残りの16ビットプリミティブでこれにアクセスするためのさまざまなオーバーロードに加えてString（最後に表示されているもの）です。
public static int IndexOf(this char[] rg, char v) => IndexOf(rg, v, 0, rg.Length);
public static int IndexOf(this char[] rg, char v, int i, int c = -1)
{
if (rg != null && (c = c < 0 ? rg.Length - i : c) > 0)
fixed (char* p = rg)
return IndexOf((ushort*)p, v, i, c < 0 ? rg.Length - i : c);
return -1;
}
public static int IndexOf(this short[] rg, short v) => IndexOf(rg, v, 0, rg.Length);
public static int IndexOf(this short[] rg, short v, int i, int c = -1)
{
if (rg != null && (c = c < 0 ? rg.Length - i : c) > 0)
fixed (short* p = rg)
return IndexOf((ushort*)p, (ushort)v, i, c < 0 ? rg.Length - i : c);
return -1;
}
public static int IndexOf(this ushort[] rg, ushort v) => IndexOf(rg, v, 0, rg.Length);
public static int IndexOf(this ushort[] rg, ushort v, int i, int c = -1)
{
if (rg != null && (c = c < 0 ? rg.Length - i : c) > 0)
fixed (ushort* p = rg)
return IndexOf(p, v, i, c < 0 ? rg.Length - i : c);
return -1;
}
public static int IndexOf(String s, Char ch, int i = 0, int c = -1)
{
if (s != null && (c = c < 0 ? s.Length - i : c) > 0)
fixed (char* p = s)
return IndexOf((ushort*)p, ch, i, c);
return -1;
}
Stringこの高性能の置換バージョンの関数がそのように呼び出されることはないため、オーバーロードは拡張メソッドとしてマークされていないことに注意してください（同じ名前の組み込みメソッドは常に拡張メソッドよりも優先されます）。インスタンスの拡張機能として使用するにはString、このメソッドの名前を変更できます。例として、Intellisenseリストの組み込みメソッド名の横にIndexOf__(this String s,...)表示されるようにします。これは、オプトインするのに役立つ可能性があります。それ以外の場合、拡張構文が必要ない場合は、この最適化されたバージョンを、の代わりに使用するときに、独自のクラスの静的メソッドとして直接呼び出すようにしてください。s.IndexOf(Char ch)