c# - 在 byte[] 中查找 byte[] 并在字符串中查找字符串的速度 - 为什么后者更快？

Question

我有一项任务需要在文件中查找序列。在做测试应用程序时，我将文件读取为字符串 (File.ReadAllText) 并使用 string.IndexOf 查找序列。当我尝试用字节实现相同的算法时(将文件作为字节数组读取并在字节数组中查找字节数组)，我注意到在 byte[] 中查找 byte[] 大约比在字符串中查找字符串慢 3 倍.我确保彻底检查它，并且完全相同的代码，一个使用 byte[]，另一个使用字符串，执行时间是原来的 3 倍 - 例如，字节为 16 秒，字符串为 ~5 秒。

为了查找字节数组，我使用了此处描述的方法 byte[] array pattern search 。为了查找字符串，我使用了字符串类的内置 IndexOf 函数。这是我尝试过的 byte[] 的 IndexOf 实现之一:

    public int IndexOf(byte[] source, byte[] pattern, int startpos = 0)
    {
        int search_limit = source.Length - pattern.Length;
        for (int i = startpos; i < search_limit; i++)
        {
            if (source[i] == pattern[0])
            {
                bool found = true;
                for (int j = 1; j < pattern.Length; j++)
                {
                    if (source[i + j] != pattern[j])
                    {
                        found = false;
                        break;
                    }
                }
                if (found)
                    return i;
            }
        }
        return -1;
    }

基本上，在字节数组中查找下一个字节序列的匹配项所花的时间是在字符串中查找字符序列的下一个匹配项的时间的三倍。我的问题是 - 为什么？

有谁知道 .Net 如何处理查找字符串中的字符，它做了什么样的优化，它使用了什么算法？有没有比我在这里使用的算法更快的算法？也许有人知道我在这里做错了什么，所以花费的时间比应该的多？我真的不明白在字符串中查找字符串的速度是在 byte[] 中查找 byte[] 的 3 倍...

更新:我已经按照建议尝试了不安全算法。内容如下:

public static unsafe long IndexOfFast(byte[] Haystack, byte[] Needle, long startpos = 0)
    {
        long i = startpos;
        fixed (byte* H = Haystack) fixed (byte* N = Needle)
        {
            for (byte* hNext = H + startpos, hEnd = H + Haystack.LongLength; hNext < hEnd; i++, hNext++)
            {

                    bool Found = true;
                    for (byte* hInc = hNext, nInc = N, nEnd = N + Needle.LongLength; Found && nInc < nEnd; Found = *nInc == *hInc, nInc++, hInc++) ;
                    if (Found) return i;

            }
            return -1;
        }
    }
}

奇怪的是，事实证明它慢了一倍!我更改了它以添加我的个人调整(在尝试遍历 needle 之前检查第一个字母)现在看起来像这样:

public static unsafe long IndexOfFast(byte[] Haystack, byte[] Needle, long startpos = 0)
    {
        long i = startpos;
        fixed (byte* H = Haystack) fixed (byte* N = Needle)
        {
            for (byte* hNext = H + startpos, hEnd = H + Haystack.LongLength; hNext < hEnd; i++, hNext++)
            {
                if (*hNext == *N)
                {
                    bool Found = true;
                    for (byte* hInc = hNext+1, nInc = N+1, nEnd = N + Needle.LongLength; Found && nInc < nEnd; Found = *nInc == *hInc, nInc++, hInc++) ;
                    if (Found) return i;
                }
            }
            return -1;
        }
    }

现在，它的执行时间与安全的完全相同。我的问题又来了——有什么想法吗？与安全相比，它不应该更快，因为它不安全并且使用指针操作吗？

Answer 1

Basically, looking up next match for sequence of bytes in bytes array takes three time as long as looking up next match for sequence of chars in string. My question is - WHY?

因为字符串搜索算法已经过大量优化；它是用紧凑的非托管代码编写的，不会花时间检查数组边界。如果您以相同的方式优化您的字节搜索算法，它会一样快；字符串搜索算法使用与您正在使用的相同的朴素算法。

您的算法很好——这是标准的“朴素”搜索，尽管凯文声称，朴素算法在实践中几乎总是典型数据 最快的。在现代硬件上，遍历数组寻找字节的速度快得令人难以置信。这取决于你的问题的大小；如果您正在寻找人类基因组中间的长 DNA 串，那么 Boyer-Moore 完全值得花费预处理费用。如果您要在一个 20 KB 的文件中寻找 0xDEADBEEF，那么如果它得到有效实现，您就不会击败朴素算法。

为了获得最大速度，您在这里应该做的是关闭安全系统并使用不安全的指针算法编写代码。