7
我有一个任务，我需要查找文件中的序列。在做测试应用程序时，我已经将文件读取为字符串（File.ReadAllText）并使用string.IndexOf来查找序列。当我试图用字节实现相同的算法（以字节数组读取文件并在字节数组中查找字节数组）时，我注意到在byte []中查找byte []的速度大约是在字符串中查找字符串的3倍。我一定要彻底检查它，并且完全相同的代码，使用byte []和其他使用字符串的代码需要执行3倍的数量 - 例如，字节为16秒，字符串为〜5秒。在字节[]中查找字节[]的速度和在字符串中的字符串 - 为什么后者更快？
为了查找字节数组，我使用了这里描述的方法byte[] array pattern search。为了查找字符串，我使用了string类的内置IndexOf函数。下面是的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处理查找字符串中的字符，它做了什么样的优化，它使用什么算法？有没有比我在这里使用的算法更快的算法？也许有人有一个想法，我在这里做错了，所以它需要更多的时间比它应该？我真的不明白如何在字符串中查找字符串可以是在字节[]中查找字节[]的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;
}
}
现在，它需要完全相同的时间来执行的安全可靠。我的问题再次 - 任何想法为什么？难道它不是更快，因为它是不安全的，并与指针相比，当与安全相比？
我会为字节数组实现[this algorithm]（http://en.wikipedia.org/wiki/Boyer%E2%80%93Moore_string_search_algorithm）并再次测试。 – I4V
那么，大多数字符串比较函数和'IndexOf'归结为内部CLR调用，通常是'InternalFindNLSStringEx'或'InternalCompareString'。本地CLR实现可能会更快。 – vcsjones
好的，现在你已经有了一个指针算术解决方案，如果你想使它更快，你将不得不开始考虑在那里实际上正在做什么机器操作。例如：更快的方法是：将一个字节从32位字中移出四次，或者制作四个掩码，一个字节位于四个位置，将字节数组视为int数组，并检查每个int以查看与掩码进行“与”操作时是否匹配任何掩码？后者可能会快几个周期。这是人们在优化此算法时所做的一些事情。 –