时间戳

首页 > 解决方案 > 为什么朴素算法比 KMP 和 Robin-Karp 更快？

java - 为什么朴素算法比 KMP 和 Robin-Karp 更快？

问题描述

最近我一直在研究 DNA 序列匹配算法及其比较。为了同样的目的，我已经实现了标准的 Naive、KMP 和 Robin-Karp 算法。
在 Java（8Gb RAM，Intel I5 处理器，1GB 硬盘）中执行后，我注意到 naive 的运行速度比 KMP 和 RK 快。
但是当我知道对于多达 100,000 个字符和 4 个字符的模式的 DNA 序列后，我感到惊讶，naive(6ms) 仍然优于 KMP(11ms) 和 RK(17ms)。我很困惑为什么会发生这种情况，这怎么可能？
天真的工作真的那么快还是 JVM 正在抛出一些随机垃圾值，或者我是否将 Java 的时间实例放在错误的位置？

任何帮助深表感谢。

标签： javastringalgorithmpattern-matching

解决方案

有许多因素可能导致这种情况。这里有几点需要考虑：

  1. 一个四字符的搜索字符串非常短——事实上，它是如此之小，以至于一个简单的搜索可能会非常快。KMP 和 Rabin-Karp 被认为是“快速”字符串搜索算法的原因是它们平均扫描输入字符串的每个字符，最多为恒定次数。如果您有一个四字符的字符串，您还将最多扫描输入的每个字符一个常数次数，这是一个低常数 (4)。所以这可能只是来自 KMP 和 Rabin-Karp 的常数因子项超过了天真的搜索的成本。（这类似于为什么许多排序算法切换到小输入大小的插入排序 - 虽然插入排序对于大序列更差，但它比小输入上的“快速”排序算法快得多。

  2. 对于从基因组中提取的四字符序列，有 4 4 = 256 种可能的随机字符串组合可供搜索。因此，按照预期，您会在从正在搜索的字符串中读取最多 256 个四字符块后找到该序列。这意味着您最多需要读取 1024 个字符才能找到您的字符串，因此基因组长度为 100,000 个字符的事实可能无关紧要。您可能更准确地处理接近 1000 的“有效”字符串长度，并且像第 (1) 部分一样，如果您对算法的输入较小，则 KMP 和 Rabin-Karp 的好处相对于它们增加的常数因子会减少。

  3. 这也可能是代码实现方式的产物。您使用的是哪个版本的 KMP 和 Rabin-Karp？String.indexOfJVM 实现者可能对它进行了大量优化；您是否同样使用高度优化的 KMP 和 Rabin-Karp 版本？

推荐阅读