Ist*_*tel 7 c# string search byte bytearray
我有一个任务,我需要在文件中查找序列.在进行测试应用程序时,我将文件读取为字符串(File.ReadAllText)并使用string.IndexOf来查找序列.当我尝试用字节实现相同的算法(将文件作为字节数组读取并在字节数组中查找字节数组)时,我注意到在byte []中查找byte []的速度大约是在字符串中查找字符串的3倍.我确保彻底检查它,完全相同的代码,一个使用byte []和其他使用字符串,执行时需要3倍 - 比如16s for byte vs~5s for string.
为了查找字节数组,我使用了这里描述的方法byte []数组模式搜索.为了查找字符串,我使用了字符串类的内置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;
}
}
}
奇怪的是,它实际上证明是两倍的速度!我更改了它以添加我的个人调整(在尝试迭代针之前检查第一个字母)现在看起来像这样:
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;
}
}
现在,执行安全的时间与完全相同.我的问题又来了 - 任何想法为什么？与安全相比,它不应该更快,因为它不安全并且使用指针操作吗？
Eri*_*ert 11
基本上,只要查找字符串中字符序列的下一个匹配,就会查找字节序列中的字节序列的下一个匹配.我的问题是 - 为什么？
因为字符串搜索算法已经过大量优化; 它是用严格的非托管代码编写的,不需要花时间检查数组边界.如果你以同样的方式优化你的字节搜索算法,它会同样快; 字符串搜索算法使用您正在使用的相同天真算法.
你的算法很好 - 这是标准的"幼稚"搜索,尽管凯文的声称,但天真的算法实际上几乎总是在典型数据上最快.在现代硬件上浏览阵列寻找字节非常快.这取决于你的问题的大小; 如果你正在寻找人类基因组中间的长DNA链,那么Boyer-Moore完全值得花费预处理.如果您正在寻找0xDEADBEEF一个20 KB的文件,那么如果它有效实施,您就不会打败天真的算法.
为了获得最大速度,您应该在此处关闭安全系统并使用不安全的指针算法编写代码.
您的字节搜索算法效率极低！
所有其他字符串搜索所比较的基线算法是Boyer-Moore。我敢打赌 .NET 字符串搜索会使用它或它的变体。还有其他的，但是为字节实现 Boyer-Moore 会给你带来更好的性能。
编辑：所以来救援！ 以下是字节数组的 Boyer-Moore 的简单 C# 实现
使用计时数字进行编辑： Eric 的评论让我非常感兴趣，因为我一直听说 .Net 字符串搜索使用 Boyer-Moore。我真的很感激一个真正知道告诉我其他情况的人。想一想就完全有道理了。我决定对 Boyer-Moore 与 Naive 字节搜索进行计时，发现 Eric 对于小针和小干草堆来说绝对正确，Naive 搜索速度快了 13 倍以上。但令我惊讶的是“收支平衡”点远低于我的预期。Boyer-Moore 显着改善了图案尺寸（或我计时中的针尺寸），因此您正在寻找的图案越大，搜索速度越快。对于 8 字节针，Naive 搜索与 Boyer-Moore 的搜索结果并列，搜索 500-600 字节的大海捞针。对于更大的干草堆，博耶-摩尔的效果明显更好，尤其是使用更大的针时。对于 20KB 的大海捞针和 64 字节的针，Boyer-Moore 的速度快了 10 倍。
完整的时间数字如下，有兴趣的朋友可以参考。
所有测试都使用上面链接的简单 Boyer-Moore 和他发布的 Op 的朴素字节搜索算法，进行 100 万次搜索迭代。
1000000 iterations, haystack size = 20 bytes, needle size = 8 bytes
20ms total : Naive Search
268ms total : Boyer-Moore Search
1000000 iterations, haystack size = 600 bytes, needle size = 8 bytes
608ms total : Naive Search
582ms total : Boyer-Moore Search
1000000 iterations, haystack size = 2000 bytes, needle size = 8 bytes
2011ms total : Naive Search
1339ms total : Boyer-Moore Search
1000000 iterations, haystack size = 2000 bytes, needle size = 32 bytes
1865ms total : Naive Search
563ms total : Boyer-Moore Search
1000000 iterations, haystack size = 2000 bytes, needle size = 64 bytes
1883ms total : Naive Search
466ms total : Boyer-Moore Search
1000000 iterations, haystack size = 20000 bytes, needle size = 8 bytes
18899ms total : Naive Search
10753ms total : Boyer-Moore Search
1000000 iterations, haystack size = 20000 bytes, needle size = 32 bytes
18639ms total : Naive Search
3114ms total : Boyer-Moore Search
1000000 iterations, haystack size = 20000 bytes, needle size = 64 bytes
18866ms total : Naive Search
1807ms total : Boyer-Moore Search