最近我一直在研究dna序列匹配算法和它们的比较。为了同样的目的，我实现了标准naive、kmp和robinkarp算法。
在用java（8gbram，inteli5处理器，1gb硬盘）执行之后，我注意到naive比kmp和rk工作得更快。
但当我知道dna序列多达100000个字符和4个字符的模式时，naive（6ms）仍然优于kmp（11ms）和rk（17ms），我感到惊讶。我很困惑为什么会发生这种情况，这怎么可能呢？
naive的工作速度真的有那么快吗？或者jvm抛出了一些随机的垃圾值，或者我把java的时间示例放错了地方？
非常感谢您的帮助。
1条答案
按热度按时间syqv5f0l1#
有许多因素可能是造成这种情况的原因。有几件事需要考虑：
一个四个字符的搜索字符串非常短-事实上，这是如此之小，一个天真的搜索可能会非常快。kmp和rabin-karp被认为是“快速”字符串搜索算法的原因是，它们平均最多扫描输入字符串的每个字符一个固定的次数。如果您有一个四个字符的字符串，那么您最多也会扫描输入的每个字符一个常量，它是一个低常量（4）。因此，这可能只是来自kmp和rabin-karp的常数因子项超过了天真搜索的成本(这类似于为什么许多排序算法在小输入大小的情况下会切换到插入排序——虽然插入排序对于大序列来说更糟糕，但它比小输入的“快速”排序算法快得多。）您可能想把事情混合起来，尝试不同的字符串长度、非随机输入等。
对于从基因组中提取的四个字符序列，有44=256个随机字符串的可能组合可供搜索。因此，在预期的情况下，您将在从正在搜索的字符串中读取最多256个四字符块之后找到该序列。这意味着您需要最多读取1024个字符才能找到字符串，因此基因组长度为100000个字符这一事实可能与此无关。您可能更准确地处理接近1000的“有效”字符串长度，并且，如第（1）部分所述，如果您对算法的输入较小，那么kmp和rabin karp的好处相对于它们增加的常数因子会减少。
这也可能是代码实现方式的产物。您使用的是哪种版本的kmp和rabin karp？
String.indexOf可能被jvm实现者进行了大量优化；您是否同样使用kmp和rabin karp的高度优化版本？