昨日在新生命团队钉钉群中,看到老师分享了他们实现的 IndexOf 算法,据说可以做到 O (1),第一反应是几乎不可能,了解之后得知是使用了 Boyer Moore 字符串搜索算法,据说这种算法常用于 IDE 工具的查找,比 KMP 更快,所以有了对各种常用字符串查找算法做一下 Benchmark 的想法。
PS:因为公众号本身的限制,源码的 GitHub 地址均无法正常跳转,可以翻到底部,阅读原文查看原始博客文章。
横向对比的各个字符串查找算法
string.IndexOf
此方法为 FLC 中实现的 string 类型的方法,以下源码均已开源在 GitHub 。
1 | // Determines the position within this string of the first occurence of the specified |
可以看到,默认使用了 StringComprison.CurrentCulture,关于其具体的定义,可以参照官方文档:
通常情况我们使用 CurrentCulture 或是 Ordinal 都能很好的满足需求。
继续向下看(源码为节选,省略了无关内容)
1 | [Pure] |
下面继续跟着源码来到 CompareInfo
1 | public unsafe virtual int IndexOf(String source, char value, CompareOptions options) |
可以看到,最终是调用了 InternalFindNLSStringEx
。
不同的选项被转换成了不同的 flag
1 | [Pure] |
可以看到继续前进涉及到了 CLR 层的 comnlsinfo
1 | // |
其中 COMPARE_OPTIONS_ORDINAL 涉及到的是 FastIndexOfString
1 |
|
其余的则是 IndexOfString
1 | FCIMPL7(INT32, COMNlsInfo::IndexOfString, |
Span<Char>.IndexOf
System.Span<T>
是在 .NET 中发挥关键作用的新值类型。使用它,可以表示任意内存的相邻区域,无论相应内存是与托管对象相关联,还是通过互操作由本机代码提供,亦或是位于堆栈上。除了具有上述用途外,它仍能确保安全访问和高性能特性,就像数组一样。
官方在 System.Memory.dll 中提供了 MemoryExtensions.IndexOf 方法,同样可以用于字符串的查找。
简单看一下源码
MemoryExtensions.Globalization.cs
1 | /// <summary> |
可以看到,只有 StringComparison.Ordinal 下,调用了 SpanHelpers.IndexOf 方法,其余参数下依旧采用了和 string.IndexOf 一致的 CompareInfo 处理。
SpanHelpers.IndexOf
1 | public static int IndexOf(ref byte searchSpace, int searchSpaceLength, ref byte value, int valueLength) |
Boyer Moore
截图来自维基百科词条:博耶 - 穆尔字符串搜索算法
这里直接上 C# 版本源码实现
1 | public static int BoyerMooreIndexOf(this string source, string pattern, int offset = 0, int count = -1) => BoyerMooreIndexOf(Encoding.UTF8.GetBytes(source), Encoding.UTF8.GetBytes(pattern), offset, count); |
KMP
截图来自维基百科词条:KMP 算法
同样直接上源码:
1 | public static int KMPSearch(this string text, string pattern) |
算法性能横向测试
本次横向对比了 IndexOf IndexOfOrdinal SpanIndexOf SpanIndexOfOrdinal BoyerMooreIndexOf KMPIndexOf,在查找样本长度 100, 10000, 1000000, 100000000 四种数据规模下,被查找字符串分别处于样本 开头、中间、结尾、随机位置 四种情况下的性能。
测试完整源码
Program.cs
1 | using BenchmarkDotNet.Attributes; |
测试结果
因为测试结果比较多,生成的图表一大堆,就不放了,直接放时间表。
1 |
|
Method | HaystackSize | Location | Mean | Error | StdDev | Median |
---|---|---|---|---|---|---|
IndexOf | 100 | Start | 1,907.369 ns | 10.5384 ns | 9.8576 ns | 1,909.585 ns |
IndexOfOrdinal | 100 | Start | 10.262 ns | 0.0898 ns | 0.0750 ns | 10.266 ns |
SpanIndexOf | 100 | Start | 6.445 ns | 0.1105 ns | 0.1033 ns | 6.402 ns |
SpanIndexOfOrdinal | 100 | Start | 11.435 ns | 0.1470 ns | 0.1148 ns | 11.426 ns |
BoyerMooreIndexOf | 100 | Start | 152.684 ns | 0.8215 ns | 0.6860 ns | 152.648 ns |
KMPIndexOf | 100 | Start | 4.804 ns | 0.0463 ns | 0.0387 ns | 4.797 ns |
IndexOf | 100 | Middle | 1,928.897 ns | 23.5317 ns | 20.8602 ns | 1,928.090 ns |
IndexOfOrdinal | 100 | Middle | 10.455 ns | 0.0554 ns | 0.0518 ns | 10.458 ns |
SpanIndexOf | 100 | Middle | 6.515 ns | 0.0611 ns | 0.0571 ns | 6.522 ns |
SpanIndexOfOrdinal | 100 | Middle | 11.298 ns | 0.0352 ns | 0.0329 ns | 11.296 ns |
BoyerMooreIndexOf | 100 | Middle | 152.590 ns | 3.0697 ns | 7.9786 ns | 150.171 ns |
KMPIndexOf | 100 | Middle | 4.900 ns | 0.0791 ns | 0.0661 ns | 4.907 ns |
IndexOf | 100 | End | 1,911.385 ns | 12.0498 ns | 11.2714 ns | 1,908.234 ns |
IndexOfOrdinal | 100 | End | 10.713 ns | 0.1678 ns | 0.1401 ns | 10.653 ns |
SpanIndexOf | 100 | End | 6.891 ns | 0.1039 ns | 0.0972 ns | 6.849 ns |
SpanIndexOfOrdinal | 100 | End | 11.380 ns | 0.0908 ns | 0.0805 ns | 11.378 ns |
BoyerMooreIndexOf | 100 | End | 149.144 ns | 2.7001 ns | 2.3936 ns | 148.958 ns |
KMPIndexOf | 100 | End | 4.750 ns | 0.0201 ns | 0.0188 ns | 4.753 ns |
IndexOf | 100 | Random | 1,926.007 ns | 37.7531 ns | 35.3143 ns | 1,925.254 ns |
IndexOfOrdinal | 100 | Random | 10.446 ns | 0.1609 ns | 0.1427 ns | 10.404 ns |
SpanIndexOf | 100 | Random | 6.384 ns | 0.0295 ns | 0.0261 ns | 6.383 ns |
SpanIndexOfOrdinal | 100 | Random | 11.130 ns | 0.0977 ns | 0.0816 ns | 11.109 ns |
BoyerMooreIndexOf | 100 | Random | 145.757 ns | 1.7552 ns | 1.4656 ns | 145.716 ns |
KMPIndexOf | 100 | Random | 4.769 ns | 0.0271 ns | 0.0253 ns | 4.770 ns |
IndexOf | 10000 | Start | 1,889.613 ns | 30.0781 ns | 28.1351 ns | 1,876.613 ns |
IndexOfOrdinal | 10000 | Start | 10.447 ns | 0.1852 ns | 0.1641 ns | 10.433 ns |
SpanIndexOf | 10000 | Start | 6.631 ns | 0.0485 ns | 0.0453 ns | 6.612 ns |
SpanIndexOfOrdinal | 10000 | Start | 11.409 ns | 0.0353 ns | 0.0331 ns | 11.413 ns |
BoyerMooreIndexOf | 10000 | Start | 149.268 ns | 2.6223 ns | 6.3331 ns | 146.790 ns |
KMPIndexOf | 10000 | Start | 4.882 ns | 0.0362 ns | 0.0282 ns | 4.874 ns |
IndexOf | 10000 | Middle | 1,925.414 ns | 14.1439 ns | 13.2303 ns | 1,924.021 ns |
IndexOfOrdinal | 10000 | Middle | 10.617 ns | 0.0675 ns | 0.0598 ns | 10.599 ns |
SpanIndexOf | 10000 | Middle | 6.610 ns | 0.0871 ns | 0.0772 ns | 6.610 ns |
SpanIndexOfOrdinal | 10000 | Middle | 11.441 ns | 0.0652 ns | 0.0610 ns | 11.437 ns |
BoyerMooreIndexOf | 10000 | Middle | 161.190 ns | 3.1946 ns | 3.2806 ns | 161.188 ns |
KMPIndexOf | 10000 | Middle | 4.930 ns | 0.0398 ns | 0.0372 ns | 4.934 ns |
IndexOf | 10000 | End | 1,924.827 ns | 13.6193 ns | 12.7395 ns | 1,922.824 ns |
IndexOfOrdinal | 10000 | End | 10.900 ns | 0.1292 ns | 0.1209 ns | 10.893 ns |
SpanIndexOf | 10000 | End | 6.816 ns | 0.0734 ns | 0.0651 ns | 6.825 ns |
SpanIndexOfOrdinal | 10000 | End | 11.402 ns | 0.0474 ns | 0.0396 ns | 11.387 ns |
BoyerMooreIndexOf | 10000 | End | 163.459 ns | 3.1810 ns | 3.6632 ns | 162.601 ns |
KMPIndexOf | 10000 | End | 5.143 ns | 0.0412 ns | 0.0385 ns | 5.145 ns |
IndexOf | 10000 | Random | 2,000.571 ns | 39.6725 ns | 38.9637 ns | 2,004.035 ns |
IndexOfOrdinal | 10000 | Random | 10.909 ns | 0.2449 ns | 0.5723 ns | 10.663 ns |
SpanIndexOf | 10000 | Random | 6.673 ns | 0.0237 ns | 0.0222 ns | 6.666 ns |
SpanIndexOfOrdinal | 10000 | Random | 10.826 ns | 0.1216 ns | 0.1078 ns | 10.797 ns |
BoyerMooreIndexOf | 10000 | Random | 163.361 ns | 3.6494 ns | 10.3528 ns | 161.226 ns |
KMPIndexOf | 10000 | Random | 4.882 ns | 0.0330 ns | 0.0309 ns | 4.872 ns |
IndexOf | 1000000 | Start | 1,917.655 ns | 5.6120 ns | 5.2495 ns | 1,917.252 ns |
IndexOfOrdinal | 1000000 | Start | 10.716 ns | 0.1213 ns | 0.1135 ns | 10.709 ns |
SpanIndexOf | 1000000 | Start | 6.572 ns | 0.0252 ns | 0.0197 ns | 6.572 ns |
SpanIndexOfOrdinal | 1000000 | Start | 11.066 ns | 0.0776 ns | 0.0726 ns | 11.066 ns |
BoyerMooreIndexOf | 1000000 | Start | 155.307 ns | 3.1059 ns | 3.6974 ns | 156.110 ns |
KMPIndexOf | 1000000 | Start | 4.843 ns | 0.0137 ns | 0.0122 ns | 4.846 ns |
IndexOf | 1000000 | Middle | 1,920.323 ns | 18.2098 ns | 17.0335 ns | 1,922.634 ns |
IndexOfOrdinal | 1000000 | Middle | 10.683 ns | 0.0894 ns | 0.0836 ns | 10.660 ns |
SpanIndexOf | 1000000 | Middle | 6.569 ns | 0.0653 ns | 0.0579 ns | 6.570 ns |
SpanIndexOfOrdinal | 1000000 | Middle | 11.046 ns | 0.0928 ns | 0.0868 ns | 11.040 ns |
BoyerMooreIndexOf | 1000000 | Middle | 153.735 ns | 3.0260 ns | 7.9716 ns | 149.605 ns |
KMPIndexOf | 1000000 | Middle | 4.948 ns | 0.0780 ns | 0.0730 ns | 4.944 ns |
IndexOf | 1000000 | End | 1,922.367 ns | 15.6553 ns | 13.8780 ns | 1,920.379 ns |
IndexOfOrdinal | 1000000 | End | 18.310 ns | 0.2918 ns | 0.2730 ns | 18.192 ns |
SpanIndexOf | 1000000 | End | 6.586 ns | 0.0560 ns | 0.0523 ns | 6.580 ns |
SpanIndexOfOrdinal | 1000000 | End | 10.961 ns | 0.0885 ns | 0.0785 ns | 10.963 ns |
BoyerMooreIndexOf | 1000000 | End | 152.627 ns | 2.9601 ns | 7.1490 ns | 151.619 ns |
KMPIndexOf | 1000000 | End | 4.875 ns | 0.0351 ns | 0.0328 ns | 4.859 ns |
IndexOf | 1000000 | Random | 1,911.500 ns | 6.8142 ns | 6.3740 ns | 1,912.532 ns |
IndexOfOrdinal | 1000000 | Random | 10.602 ns | 0.0849 ns | 0.0752 ns | 10.602 ns |
SpanIndexOf | 1000000 | Random | 6.673 ns | 0.0511 ns | 0.0478 ns | 6.673 ns |
SpanIndexOfOrdinal | 1000000 | Random | 11.070 ns | 0.1190 ns | 0.1113 ns | 11.049 ns |
BoyerMooreIndexOf | 1000000 | Random | 149.230 ns | 3.0118 ns | 5.0320 ns | 147.710 ns |
KMPIndexOf | 1000000 | Random | 4.858 ns | 0.0327 ns | 0.0290 ns | 4.859 ns |
IndexOf | 100000000 | Start | 1,915.633 ns | 14.4868 ns | 13.5510 ns | 1,917.496 ns |
IndexOfOrdinal | 100000000 | Start | 10.772 ns | 0.1435 ns | 0.1342 ns | 10.764 ns |
SpanIndexOf | 100000000 | Start | 6.827 ns | 0.0666 ns | 0.0623 ns | 6.806 ns |
SpanIndexOfOrdinal | 100000000 | Start | 10.977 ns | 0.0593 ns | 0.0526 ns | 10.989 ns |
BoyerMooreIndexOf | 100000000 | Start | 146.921 ns | 2.9779 ns | 2.6398 ns | 147.245 ns |
KMPIndexOf | 100000000 | Start | 4.833 ns | 0.0151 ns | 0.0134 ns | 4.832 ns |
IndexOf | 100000000 | Middle | 1,906.318 ns | 5.4295 ns | 5.0788 ns | 1,905.934 ns |
IndexOfOrdinal | 100000000 | Middle | 10.725 ns | 0.2305 ns | 0.2467 ns | 10.689 ns |
SpanIndexOf | 100000000 | Middle | 6.862 ns | 0.0724 ns | 0.0642 ns | 6.851 ns |
SpanIndexOfOrdinal | 100000000 | Middle | 11.001 ns | 0.0903 ns | 0.0845 ns | 11.019 ns |
BoyerMooreIndexOf | 100000000 | Middle | 152.705 ns | 2.4382 ns | 2.2807 ns | 152.401 ns |
KMPIndexOf | 100000000 | Middle | 4.850 ns | 0.0262 ns | 0.0245 ns | 4.846 ns |
IndexOf | 100000000 | End | 1,923.149 ns | 9.6492 ns | 9.0258 ns | 1,921.531 ns |
IndexOfOrdinal | 100000000 | End | 10.718 ns | 0.1682 ns | 0.1491 ns | 10.759 ns |
SpanIndexOf | 100000000 | End | 6.807 ns | 0.0234 ns | 0.0207 ns | 6.804 ns |
SpanIndexOfOrdinal | 100000000 | End | 11.071 ns | 0.1070 ns | 0.1001 ns | 11.076 ns |
BoyerMooreIndexOf | 100000000 | End | 147.044 ns | 2.9552 ns | 2.7643 ns | 147.472 ns |
KMPIndexOf | 100000000 | End | 4.966 ns | 0.1067 ns | 0.0891 ns | 4.949 ns |
IndexOf | 100000000 | Random | 1,925.095 ns | 30.9030 ns | 28.9067 ns | 1,923.878 ns |
IndexOfOrdinal | 100000000 | Random | 10.486 ns | 0.0910 ns | 0.0806 ns | 10.498 ns |
SpanIndexOf | 100000000 | Random | 7.009 ns | 0.1658 ns | 0.1628 ns | 7.015 ns |
SpanIndexOfOrdinal | 100000000 | Random | 11.080 ns | 0.0898 ns | 0.0840 ns | 11.112 ns |
BoyerMooreIndexOf | 100000000 | Random | 155.551 ns | 3.1132 ns | 4.2614 ns | 155.335 ns |
KMPIndexOf | 100000000 | Random | 4.887 ns | 0.0573 ns | 0.0536 ns | 4.871 ns |
总结
不同算法在数据集大小不同和关键字符串位置不同的情况下,表现都很稳定。
默认的 IndexOf 最好使用 StringComparison.Ordinal ,比默认的 StringComparison.CurrentCulture 快两个数量级,平均大约是 20 倍的差距。
算法效率由快到慢排序为 KMPIndexOf SpanIndexOf IndexOfOrdinal SpanIndexOfOrdinal BoyerMooreIndexOf IndexOf,效率比率大约为:
KMPIndexOf | SpanIndexOf | IndexOfOrdinal | SpanIndexOfOrdinal | BoyerMooreIndexOf | IndexOf |
---|---|---|---|---|---|
1 | 2 | 2.5 | 3 | 35 | 200 |
PS:以上结果仅为本人测试所得,供本人日后编程参考,不排除有代码 BUG 的可能,欢迎斧正。
点击下方卡片关注DotNet NB
一起交流学习
▲ 点击上方卡片关注DotNet NB,一起交流学习
请在公众号后台