我有一个任务,需要在文件中查找序列。在进行测试应用程序时,我将文件读取为字符串(File.ReadAllText),并使用string.IndexOf查找序列。当我尝试使用字节实现相同的算法(将文件作为字节数组读取,并在字节数组中查找字节数组)时,我注意到在字节数组中查找byte[]比在字符串中查找要慢大约3倍。我确保进行了彻底检查,并且完全相同的代码,一个使用byte[],另一个使用string,执行时间是3倍 - 例如,对于byte,需要16秒,而对于string,大约需要5秒。
基本上,在字节数组中查找下一个字节序列要比在字符串中查找下一个匹配项慢三倍。我的问题是 - 为什么?是否有人知道.NET如何处理在字符串中查找字符,它进行了哪种优化,使用了哪种算法?是否有比我正在使用的更快的算法?也许有人知道我在这里做错了什么,导致它所需的时间比应该的多?我真的不明白在字符串中查找字符串如何比在字节数组中查找字节数组快三倍...更新:我已经尝试了建议的不安全算法。它如下所示:
现在,执行不安全的代码和执行安全的代码所需的时间完全相同。我的问题是 - 有什么想法为什么会这样?因为它是不安全的并且使用指针,与安全代码相比,应该更快才对吗?
对于查找字节数组,我使用了这里描述的方法byte[] array pattern search。对于查找字符串,我使用了string类的内置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如何处理在字符串中查找字符,它进行了哪种优化,使用了哪种算法?是否有比我正在使用的更快的算法?也许有人知道我在这里做错了什么,导致它所需的时间比应该的多?我真的不明白在字符串中查找字符串如何比在字节数组中查找字节数组快三倍...更新:我已经尝试了建议的不安全算法。它如下所示:
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;
}
}
现在,执行不安全的代码和执行安全的代码所需的时间完全相同。我的问题是 - 有什么想法为什么会这样?因为它是不安全的并且使用指针,与安全代码相比,应该更快才对吗?
IndexOf
都归结为一个内部 CLR 调用,通常是InternalFindNLSStringEx
或InternalCompareString
中的一个。本地 CLR 实现可能会更快。 - vcsjones