 一定更快这条共识的实测复盘)
面试里背得最顺的一句话是朴素搜索是 O(n·m)KMP 是 O(nm)所以 KMP 一定更快。我一度也这么信。直到上周把一个 640KB 的日志做关键字提取手写的 KMP 比同事三行indexOf慢了整整一个数量级——这不对劲。于是我把朴素、KMP、Boyer-Moore-HorspoolBMH和 V8 内置String.indexOf拉到同一张基准上用可控文本跑了中位数结论和教科书不太一样。背景为什么字符串搜索值得较真字符串搜索是工程里出现频率最高的小操作日志关键字提取、模板引擎匹配、协议解析、浏览器地址栏高亮、IDE 符号查找……单次看着便宜可一旦放进热路径每行日志、每个请求、每个 token复杂度的常数因子会被放大成实打实的延迟。问题就出在共识两个字。教科书把朴素算法钉在 O(n·m) 的耻辱柱上把 KMP 捧成 O(nm) 的优等生却很少讲清楚O(nm) 的保证到底在什么输入下才兑现又是什么让 KMP 在另一些输入下反而更慢。本次实测想回答的就是这件事。解剖朴素、KMP、BMH 到底差在哪三种手写的算法差异全在失配后怎么移动指针朴素Brute Force文本每个位置 i 都从头比对 pattern失配就 i1 重来。最坏情况每移一位都要比 m 个字符于是 O(n·m)。但它的隐藏优势是在几乎不匹配的真实文本里第一次比对就失败实际只做约 2n 次比较——常数极小。KMP预处理 pattern 出一张lps最长公共前后缀表失配时利用已匹配前缀跳过不必比的位置搜索阶段严格 O(n)。代价是每次失配都要查lps表、维护两个指针常数比朴素大。BMHBoyer-Moore-Horspool只看 pattern 最后一个字符做坏字符跳转平均能一次跳过接近 m 个字符实际表现常常优于 KMP且代码更短。内置indexOfV8 并不是教科书实现而是 SIMD Two-Way 风格的工业级搜索单条指令比对多个字节是这次的天花板基线。图1四种字符串搜索算法的机制差异。KMP 的快来自失配时的前缀复用但每次复用都要付出查表与双指针的常数成本。实证一随机文本里KMP 并没有更快先用最像生产的输入10 万字符的随机英文文本、pattern 搜不到典型找关键字但不存在的场景。Node v22、固定种子、每配置取中位数。结果单次搜索耗时毫秒文本规模pattern 长朴素KMPBMHindexOf10K50.00980.02240.00750.0013100K1000.36370.28170.01320.00921M1006.57013.98020.18620.1065关键发现在搜不到的随机文本里KMP 并不稳赢朴素。pattern 只有 5 个字符时KMP 反而比朴素慢 2.3 倍0.0224 vs 0.0098 ms——因为朴素几乎第一步就失配而 KMP 的查表与双指针纯属 overhead。即便在 1M 规模朴素与 KMP 的差距也只在 1.6 倍以内来回拉锯。换句话说O(nm) 的保证在随机文本里几乎兑现不出收益。图2随机文本、短 pattern 的场景下KMP 的常数开销让它跑不过朴素BMH 与 indexOf 则早已把两者甩开。实证二对抗文本里朴素搜索当场爆炸那 KMP 的保证什么时候才兑现答案是当文本逼出朴素的最坏情况——大量部分匹配。构造文本全是apattern 是a×(m-1)b永不整段命中但每个对齐都要比 m−1 个a才失败朴素立刻退化成 O(n·m)文本规模pattern 长朴素KMPBMHindexOf10K1004.51150.07560.05420.0255100K10050.61570.72890.71100.2606200K10074.79532.21450.89620.5161100KB 的a文本、pattern 长 100 时朴素 50.6msKMP 0.73ms——朴素慢了 69 倍。这就是 O(nm) 保证的意义它把对手能构造的最坏输入从指数级拉回线性。但注意BMH 和 indexOf 同样扛住了这场爆炸KMP 并非唯一的解药。图3当文本制造大量部分匹配朴素的 O(n·m) 最坏情况被彻底激活KMP/BMH/indexOf 都保持线性但朴素一支独大。实证三真正赢麻的是 BMH 和内置 indexOf把三张表合起来看真正的赢家从来不是 KMP。在 1M 随机文本、pattern 长 100 的场景里IndexOf 0.107msBMH 0.186msKMP 3.98ms朴素 6.57ms。内置indexOf比手写的 KMP 快 37 倍、比朴素快 62 倍BMH 也比 KMP 快 21 倍。哪怕是 KMP 的主场对抗文本IndexOf 仍是最快的那个0.26ms vs KMP 0.73ms。原因不难想V8 的indexOf用 SIMD 一次比对十几个字节BMH 靠坏字符跳转几乎跳着走而 KMP 再怎么优化也是逐字符 查表。手写 KMP 的价值只存在于你不能调内置、又没法引入 BMH的极少数受限环境。图4综合来看内置 indexOf 与 BMH 把 KMP 和朴素同时甩开手写 KMP 在性能上并不占优。局限这次没测什么诚实边界避免被当成银弹只测了单 pattern、单次搜索。多关键字如一次性匹配上千条攻击特征该上 Aho-Corasick那是另一篇文章。文本是内存字符串超大规模外存搜索要考虑 IO 而非算法常数。BMH 在极小字母表如 DNA 的 A/C/G/T上坏字符跳转收益下降KMP/Z 算法在小字母表更稳——本次没覆盖。数字来自单台机器Windows / AMD64 / Node v22的中位数不同 V8 版本、不同 CPU 会有浮动但相对排序稳定。结论与下一步一句话方法论别再为了O(nm)手写 KMP。普通搜索直接用内置indexOf要手写就选 BMH只有多 pattern 才考虑 Aho-Corasick。KMP 的复杂度保证只在对手能构造最坏输入的对抗场景下才值钱而那种场景下 BMH 和内置实现同样线性KMP 并不特殊。开源地址矩阵门户https://github.com/wangzifan396-wzf/WB单文件工具聚合器https://github.com/wangzifan396-wzf/nano-workbenchGitHub 组织主页https://github.com/wangzifan396-wzf
面试里背得最顺的一句话是朴素搜索是 O(n·m)KMP 是 O(nm)所以 KMP 一定更快。我一度也这么信。直到上周把一个 640KB 的日志做关键字提取手写的 KMP 比同事三行indexOf慢了整整一个数量级——这不对劲。于是我把朴素、KMP、Boyer-Moore-HorspoolBMH和 V8 内置String.indexOf拉到同一张基准上用可控文本跑了中位数结论和教科书不太一样。背景为什么字符串搜索值得较真字符串搜索是工程里出现频率最高的小操作日志关键字提取、模板引擎匹配、协议解析、浏览器地址栏高亮、IDE 符号查找……单次看着便宜可一旦放进热路径每行日志、每个请求、每个 token复杂度的常数因子会被放大成实打实的延迟。问题就出在共识两个字。教科书把朴素算法钉在 O(n·m) 的耻辱柱上把 KMP 捧成 O(nm) 的优等生却很少讲清楚O(nm) 的保证到底在什么输入下才兑现又是什么让 KMP 在另一些输入下反而更慢。本次实测想回答的就是这件事。解剖朴素、KMP、BMH 到底差在哪三种手写的算法差异全在失配后怎么移动指针朴素Brute Force文本每个位置 i 都从头比对 pattern失配就 i1 重来。最坏情况每移一位都要比 m 个字符于是 O(n·m)。但它的隐藏优势是在几乎不匹配的真实文本里第一次比对就失败实际只做约 2n 次比较——常数极小。KMP预处理 pattern 出一张lps最长公共前后缀表失配时利用已匹配前缀跳过不必比的位置搜索阶段严格 O(n)。代价是每次失配都要查lps表、维护两个指针常数比朴素大。BMHBoyer-Moore-Horspool只看 pattern 最后一个字符做坏字符跳转平均能一次跳过接近 m 个字符实际表现常常优于 KMP且代码更短。内置indexOfV8 并不是教科书实现而是 SIMD Two-Way 风格的工业级搜索单条指令比对多个字节是这次的天花板基线。图1四种字符串搜索算法的机制差异。KMP 的快来自失配时的前缀复用但每次复用都要付出查表与双指针的常数成本。实证一随机文本里KMP 并没有更快先用最像生产的输入10 万字符的随机英文文本、pattern 搜不到典型找关键字但不存在的场景。Node v22、固定种子、每配置取中位数。结果单次搜索耗时毫秒文本规模pattern 长朴素KMPBMHindexOf10K50.00980.02240.00750.0013100K1000.36370.28170.01320.00921M1006.57013.98020.18620.1065关键发现在搜不到的随机文本里KMP 并不稳赢朴素。pattern 只有 5 个字符时KMP 反而比朴素慢 2.3 倍0.0224 vs 0.0098 ms——因为朴素几乎第一步就失配而 KMP 的查表与双指针纯属 overhead。即便在 1M 规模朴素与 KMP 的差距也只在 1.6 倍以内来回拉锯。换句话说O(nm) 的保证在随机文本里几乎兑现不出收益。图2随机文本、短 pattern 的场景下KMP 的常数开销让它跑不过朴素BMH 与 indexOf 则早已把两者甩开。实证二对抗文本里朴素搜索当场爆炸那 KMP 的保证什么时候才兑现答案是当文本逼出朴素的最坏情况——大量部分匹配。构造文本全是apattern 是a×(m-1)b永不整段命中但每个对齐都要比 m−1 个a才失败朴素立刻退化成 O(n·m)文本规模pattern 长朴素KMPBMHindexOf10K1004.51150.07560.05420.0255100K10050.61570.72890.71100.2606200K10074.79532.21450.89620.5161100KB 的a文本、pattern 长 100 时朴素 50.6msKMP 0.73ms——朴素慢了 69 倍。这就是 O(nm) 保证的意义它把对手能构造的最坏输入从指数级拉回线性。但注意BMH 和 indexOf 同样扛住了这场爆炸KMP 并非唯一的解药。图3当文本制造大量部分匹配朴素的 O(n·m) 最坏情况被彻底激活KMP/BMH/indexOf 都保持线性但朴素一支独大。实证三真正赢麻的是 BMH 和内置 indexOf把三张表合起来看真正的赢家从来不是 KMP。在 1M 随机文本、pattern 长 100 的场景里IndexOf 0.107msBMH 0.186msKMP 3.98ms朴素 6.57ms。内置indexOf比手写的 KMP 快 37 倍、比朴素快 62 倍BMH 也比 KMP 快 21 倍。哪怕是 KMP 的主场对抗文本IndexOf 仍是最快的那个0.26ms vs KMP 0.73ms。原因不难想V8 的indexOf用 SIMD 一次比对十几个字节BMH 靠坏字符跳转几乎跳着走而 KMP 再怎么优化也是逐字符 查表。手写 KMP 的价值只存在于你不能调内置、又没法引入 BMH的极少数受限环境。图4综合来看内置 indexOf 与 BMH 把 KMP 和朴素同时甩开手写 KMP 在性能上并不占优。局限这次没测什么诚实边界避免被当成银弹只测了单 pattern、单次搜索。多关键字如一次性匹配上千条攻击特征该上 Aho-Corasick那是另一篇文章。文本是内存字符串超大规模外存搜索要考虑 IO 而非算法常数。BMH 在极小字母表如 DNA 的 A/C/G/T上坏字符跳转收益下降KMP/Z 算法在小字母表更稳——本次没覆盖。数字来自单台机器Windows / AMD64 / Node v22的中位数不同 V8 版本、不同 CPU 会有浮动但相对排序稳定。结论与下一步一句话方法论别再为了O(nm)手写 KMP。普通搜索直接用内置indexOf要手写就选 BMH只有多 pattern 才考虑 Aho-Corasick。KMP 的复杂度保证只在对手能构造最坏输入的对抗场景下才值钱而那种场景下 BMH 和内置实现同样线性KMP 并不特殊。开源地址矩阵门户https://github.com/wangzifan396-wzf/WB单文件工具聚合器https://github.com/wangzifan396-wzf/nano-workbenchGitHub 组织主页https://github.com/wangzifan396-wzf
