12

我有一个字节数组，并希望找到特定字节的第一次出现（如果有的话）。

你们能帮我一个漂亮、优雅和有效的方法吗？

 /// 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)
{

}
4

3 回答 3

28 
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);
于 2009-06-10T10:59:34.060 回答
13

Array.IndexOf？

于 2009-06-10T10:59:50.363 回答
3

既然您提到了效率，这里是我编写的一些经过高度优化的 C# 代码，它使用本机寻址和最大 qword-aligned 读取来将内存访问次数减少 8 倍。如果有任何更快的方法，我会感到惊讶在.NET中扫描内存中的一个字节。

这将返回从 offset （相对于 address ）开始并持续到 length的内存范围内第一次出现字节 '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;
}

不要被你看到的一个乘法吓到；每次调用此函数最多只执行一次，以便进行最终的deBruijn 查找。用于此的只读查找表是一个简单的 64 字节值共享列表，需要一次性初始化：

// 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中研究对成组内存搜索的一般方法的另一种看法，但与我的代码相比，该代码具有明显的缺点：

  • 最重要的是，.NET 代码一次只扫描 4 个字节，而不是我的 8 个字节。
  • 这是一个非公共方法，因此您需要使用反射来调用它。
  • .NET 代码有一个“性能泄漏”，t1 != 0检查给出了一个误报，随后的四个检查被浪费了。注意他们的“失败”案例：由于这种误报，他们需要四次最终检查——从而允许失败——以保持正确性，而不仅仅是三个。
  • .NET 代码的误报是由基于从一个字节到下一个字节的进位溢出的固有劣质按位计算引起的。这会导致二进制补码不对称（通过使用常量0x7efefeff或来证明0x81010100）和偶尔的“左向出口”（即丢失）有关最高有效字节的信息，这是这里真正的问题。相反，我使用下溢计算，它使每个字节的计算独立于其邻居。我的方法在所有情况下都给出了结论性的结果，没有误报或“失败”处理。
  • 我的代码使用无分支技术进行最终查找。少数非分支逻辑操作（在这种情况下加上一个乘法）通常被认为有利于扩展if-else结构的性能，因为后者会破坏CPU 预测缓存。if-else这个问题对我的 8 字节扫描器来说更重要，因为与 4 字节的成组扫描器相比，如果不使用查找，我在最终检查中的条件会是原来的两倍。

当然，如果您不关心所有这些细节，您可以复制并使用代码；我已经对它进行了非常详尽的单元测试，并验证了所有格式正确的输入的正确行为。因此，当核心功能可以使用时，您可能需要添加参数检查。

[编辑：]

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实例的扩展，您可以更改此方法的名称。例如，IndexOf__(this String s,...)会导致它出现在Intellisense列表中的内置方法名称旁边，这可能有助于提醒您选择加入。否则，如果您不需要扩展语法，则可以确保在要使用此优化版本而不是.s.IndexOf(Char ch)

于 2017-10-11T01:01:31.337 回答