String.Contains如何工作？

Question

可能重复:
.Net用于搜索字符串中的模式的算法是什么？

我的程序中有一个循环从文件中获取一行.然后检查该行是否包含字符串

if(line.Contains("String"))
{
    //Do other stuff
}

文件中有超过200万行,所以如果我可以加快速度甚至1/10毫秒,那么每次运行会节省3分钟以上.

所以...假设一条线长1000个字符,是否更快找到一个短或长的字符串,或者它没有区别？

line.Contains("ABCDEFGHIJKLMNOPQRSTUVWXYZ");

要么

line.Contains("ABCDEFG")

先感谢您.

Answer 1

String.Contains()沿着一条曲折的路线通过System.Globalization.CompareInfo进入CLR和NLS支持子系统,在那里我彻底迷失了.这包含高度优化的代码和令人印象深刻 更快地完成它的唯一方法是通过pingvvrt.dll中提供的标准CRT函数wcsstr

    [DllImport("msvcrt.dll", CharSet = CharSet.Unicode)]
    private static extern IntPtr wcsstr(string toSearch, string toFind);

如果找不到字符串,则返回IntPtr.Zero.我做了一些测量,使用String.IndexOf()而不是Contains()来测试各种字符串比较选项.所有时间都以纳秒为单位,在60个字符的字符串中搜索7个字符的字符串.由于字符串不存在,因此测量最坏情况.使用20个样本中的最短时间:

StringComparison.Ordinal (same as Contains) : 245 nanoseconds
StringComparison.OrdinalIgnoreCase : 327
StringComparison.InvariantCulture : 251
StringComparison.InvariantCultureIgnoreCase : 327
StringComparison.CurrentCulture : 275
StringComparison.CurrentCultureIgnoreCase : 340
wcsstr : 213

非常令人印象深刻的数字,与您期望这些功能所要求的相提并论.wcsstr()函数与String.Compare()执行相同类型的序数比较.由于CPU缓存局部性的影响,实际性能不太可能接近这些测量,因此它仅快13%,在统计上无显着改善.我只能得出结论,你的速度和你想象的一样快.wcsstr的微小改进是否值得,取决于你.

Answer 2

"通常,当搜索的密钥变得更长时,算法变得更快"

http://en.wikipedia.org/wiki/Boyer%E2%80%93Moore_string_search_algorithm