如何实现滑动窗口或减少这些嵌套循环？

Question

我试图减少这些循环以优化一些代码。有人建议我使用滑动窗口技术，但似乎无法使其适合我的示例。

我添加括号中的所有内容只是为了表明它们是什么类型。file.get（..）方法从文件中的给定索引返回一个字节。由于这些文件很大，因此外循环可以（通常）在很大的范围内进行迭代。asciiCombo的范围是2-8个元素。

这是一个嵌套循环，我不确定如何减少它：

for (long i = offsetInBytes; i < (long) file.length; ++i) {
        int match = 0;
        for (int j = 0; j < (int[]) asciiCombo.length; ++j) {
            if (file.get(i + j) == asciiCombo[j]) {
                match++;
            } else {
                break;
            }
         }
}

用if语句或某个要查找的集合替换内部循环与嵌套循环本质上是相同的，因此不会执行。我一直无法实现滑动窗口（不确定是否可以实现）。

我一直在这里陷入困境，不胜感激。谢谢！

Answer 1

这是一个字符串搜索问题。

有一种有效的滑动窗口技术，称为 Rabin-Karp 算法：https://en.wikipedia.org/wiki/Rabin%E2%80%93Karp_algorithm

它需要一个“特殊”的哈希函数，允许您在滑动窗口前进时快速更新其哈希值。我将“特殊”放在引号中，因为最常见的字符串哈希方法（多项式哈希）实际上有效。

然而，还有很多替代方案。我喜欢 Knuth-Morris-Pratt：https://en.wikipedia.org/wiki/Knuth%E2%80%93Morris%E2%80%93Pratt_algorithm

该程序会为您正在搜索的字符串计算一个状态机，该状态机允许仅检查文件中的每个字节一次。

Boyer-Moore 也很受欢迎：https://en.wikipedia.org/wiki/Boyer%E2%80%93Moore_string-search_algorithm

但请注意，从我看到的代码以及您要查找的字符串通常只有 2-8 个字节长的声明来看，我不认为您选择的搜索算法是问题所在。在我看来，您的实施更有可能file.get(index)很慢。

您可能想使用 aBufferedInputStream(FileInputStream(...))来代替。这将按顺序一次给出一个字节。使用适用于此限制的字符串搜索。Knuth-Morris-Pratt 就可以了，或者如果字符串确实被限制为 8 个字节，那么整个字符串就适合一个long. 使用它直接将文件中的所有 8 个字符与前 8 个字符与 1 进行比较==。