算法在Java中.indexOf方法的选择 [英] Choice of algorithm for .indexOf method in Java

问题描述

我只是在看的Java 字符串类的<​​code> .indexOf（）法的实施，似乎的code笔者采用穷举算法找到一个给定的字符串中的子字符串。也就是说，该方法运行在O（MN），其中m和n是在源和目标串的长度，分别

I was just looking at the implementation of the Java String class's .indexOf() method and it seems the author of the code uses the brute force algorithm to find the substring in a given string. That is, the approach runs in O(mn), where m and n are the length of the source and target strings, respectively.

为什么不是作者使用更有效的算法类似拉宾，卡普，其中有邻运行时的复杂性（M + N），如果一个好的哈希函数提供？

Why didn't the author use a more efficient algorithm like Rabin-Karp, which has a runtime complexity of O(m + n) if a good hash function is provided ?

我可能会错过了后面的这个实现的原因完整的知识，因此想了解。

I might be missing out on the complete knowledge behind the reason for this implementation and hence wanted to understand.

推荐答案

我不知道肯定不为什么这个决定是，但如果我UAD猜测这可能是因为对小模式字符串（一个很常见的情况）天真蛮力算法大概是快如果不是一些渐近更快的算法类似拉宾 - 卡普，博耶 - 穆尔，或克努特 - 莫里斯 - 普拉特更快。这似乎是一个合理的默认算法，因为在很多情况下，你会寻找小弦的小图案，以及强大的配套设置的开销可能会媲美的天真的方法运行。

I don't know for sure why this decision was made, but if I uad to guess it's probably because for small pattern strings (a very common use case) the naive brute force algorithm is probably as fast if not faster than some of the asymptotically faster algorithms like Rabin-Karp, Boyer-Moore, or Knuth-Morris-Pratt. This seems like a reasonable default algorithm since in many cases you'll be searching small strings for small patterns, and the overhead from a powerful matched setup probably would be comparable to the runtime of the naive approach.

这表示，无处在Java规范做它要求使用这个算法。他们可以很容易地纷纷拿起拉宾，卡普作为默认算法。

That said, nowhere in the Java spec does it mandate the use of this algorithm. They could just as easily have picked Rabin-Karp as the default algorithm.

还有一个原因，他们可能都选择了这种方式，因为如果你想要做的快速文本搜索，正则表达式库提供更快的字符串匹配更强大的搜索功能。给用户带来简单的蛮力算法，在默认情况下，选项在需要时切换到更强大的工具集，似乎是平衡渐近效率的实际效率的好方法。

Another reason they may have opted for this approach is because if you want to do fast text searching, the regex library provides faster string matching with more powerful search capabilities. Giving users the simple brute force algorithm by default and the option to switch to a more powerful set of tools when needed seems like a good way to balance asymptotic efficiency with practical efficiency.

这篇关于算法在Java中.indexOf方法的选择的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！