时间戳

首页 > 解决方案 > 如何实现滑动窗口或减少这些嵌套循环？

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

问题描述

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

我添加括号中的所有内容只是为了显示它们是什么类型。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 语句或某个要查找的集合替换内部循环与嵌套循环基本相同，因此不会这样做。我一直无法实现滑动窗口（甚至不确定我们可以）。

我在这里遇到了一个卡住的地方，不胜感激。谢谢！

标签： javaalgorithmloopsoptimization

解决方案

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

有一种有效的滑动窗口技术，称为 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)速度很慢。

您可能想改用 a BufferedInputStream(FileInputStream(...))。这将按顺序为您提供一个字节。使用适用于此限制的字符串搜索。Knuth-Morris-Pratt 会很好，或者如果字符串真的被限制为 8 个字节，那么整个事情都适合long. 使用它直接将所有 8 个字符与文件中的前 8 个字符与一个==.

推荐阅读