为了查找字节数组,我使用了这里描述的方法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;
}
}
}
奇怪的是,它实际上证明是慢两倍！我更改了它以添加我的个人调整(在尝试迭代针之前检查第一个字母)现在看起来像这样：
public static unsafe long IndexOfFast(byte[] Haystack,hNext++)
{
if (*hNext == *N)
{
bool Found = true;
for (byte* hInc = hNext+1,nInc = N+1,hInc++) ;
if (Found) return i;
}
}
return -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,那么如果它被有效实现你就不会打败天真的算法.
