Mik*_*der 19 java string knuth-morris-pratt
我读了源代码,java.lang.String我惊讶地发现String.indexof()不使用Knuth-Morris-Pratt算法？众所周知,KMP更有效.那么为什么不用呢String.indexOf()？
我身边的人告诉我,对于短串KMP来说已经足够好了,但是如果你需要性能并打算使用大字符串那么这不是一个好选择.但他并没有告诉我细节.
所以,这是我的问题:
String.indexOf()？Joa*_*uer 21
KMP具有更好的最坏情况性能,但实际上需要一些前期计算(以生成偏移表).这还需要一个初始的内存分配,这也可能会影响性能.
对于(可能)在相对较短的字符串中搜索的常见用例,实际上这可能比原始实现更慢.
这与这样一个事实捆绑在一起:对于真正庞大的数据集,您可能会使用更专业的数据结构而不是简单的String方法,即增加的实现(以及可能的运行时)成本不值得投资.
请注意,这可能会在将来的Java版本中更改,因为未指定实际算法.
KMP和其他几个渐近有效的字符串搜索方法,如Boyer-Moore和Boyer-Moore-Horspool需要额外的内存 - 在KMP的情况下,O(m)内存,其中m是要搜索的子字符串的大小.虽然这通常是可以接受的,但是图书馆设计者必须进行权衡,以便他们的代码在许多不同的情况下表现得非常好.可能主要原因是由于KMP所需的预处理以及搜索阶段中更复杂的内循环,在许多常见情况下,常数因子减速可能使其比原始O(mn)子串搜索慢几倍(例如,在长字符串中搜索<10个字符的子字符串).也,
也许更好的问题是为什么主流语言运行时库尚未采用O(m + n)-time,O(1)空间算法(如双向算法).同样,答案可能是常见情况下的常数因素减缓.然而,在至少一个C运行时库实现中,相应的strstr()函数已被更新以使用该算法.
我周围的人告诉我,对于短字符串KMP是足够好的,但如果你需要性能而你打算使用大字符串那么这不是一个好的选择.
嗯,这完全是我的理解后退,这就是天真的O(mn)子串搜索对于短字符串来说已经足够好(并且可能是最好的),但最终会失去渐近更快的O(m + n)算法,如KMP随着琴弦变长.