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

关键词：

【中文标题】如何实现滑动窗口或减少这些嵌套循环？【英文标题】：How to implement sliding window or reduce these nested loops? 【发布时间】：2020-03-19 00:09:36 【问题描述】：

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

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

我在这里遇到了一个卡住的地方，希望能提供任何帮助。谢谢！

【问题讨论】：

【参考方案1】：

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

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

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

但是，有很多选择。我喜欢 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) 的实施很慢。

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

【讨论】：

如何减少python中嵌套循环的时间

】如何减少python中嵌套循环的时间【英文标题】：howtoreducethetimeofanestedloopinpython【发布时间】：2022-01-0417:59:16【问题描述】：我正在从ESPN获取球员数据，但我发现自己的问题是获取每个变量的等待时间很长，如何提高效率？playe... 查看详情

如何减少这些 if 条件的嵌套？

】如何减少这些if条件的嵌套？【英文标题】：Howtoreducethenestingoftheseif-conditionals?【发布时间】：2012-05-1308:40:48【问题描述】：我有一个小问题:D我找不到合适的搜索词，所以我写了这个问题。我怎么变短？我知道这个逻辑||但是... 查看详情

算法和数据结构解析-5:滑动窗口问题(代码片段)

1.简介滑动窗口算法是在给定特定窗口大小的数组或字符串上执行要求的操作，它的原理与网络传输TCP协议中的滑动窗口协议（SlidingWindowProtocol）基本一致。这种技术可以将一部分问题中的嵌套循环转变为一个单循环&... 查看详情

如何使用 PySpark 进行嵌套的 for-each 循环

】如何使用PySpark进行嵌套的for-each循环【英文标题】：howtodoanestedfor-eachloopwithPySpark【发布时间】：2016-08-2522:54:29【问题描述】：想象一个大型数据集（>40GBparquet文件），其中包含数千个变量的值观察值作为三元组（变量、时... 查看详情

jetpackcompose之手势使用

...手势整体框架，做到心中有图。这个含义都懂就不解释，实现点击采用的修饰符clickable，如下：滚动修饰符实现使用的修饰符为：verticalScroll或horizontalScroll，您无需转换或偏移内容。可滚动修饰符实现使用修饰符为：scrollable，... 查看详情

javascript性能优化9——减少判断层级减少循环体活动(代码片段)

目录一、减少判断层级1.引入2.实现场景原始代码总结二、减少循环体活动1.引入2.实现场景原始代码优化后的代码二次优化一、减少判断层级1.引入减少判断层级对我们的代码的性能影响，主要在当我们编写代码的时候有可能... 查看详情

滑动窗口slidingwindowalgorithm(代码片段)

应用及优点：1.可用于解决数组或者字符串的子元素问题。2.用单循环代替了嵌套循环问题，时间复杂度低。3.用双指针维护动态窗口。 相关算法题：LongestSubstringWithoutRepeatingCharacters无重复最长子串FindAllAnagramsinaString（找到字... 查看详情

tcp通过滑动窗口和拥塞窗口实现限流，能抵御ddos攻击吗

　　tcp可以通过滑动窗口和拥塞算法实现流量控制，限制上行和下行的流量，但是却不能抵御ddos攻击。　　限流只是限制访问流量的大小，是无法区分正常流量和异常攻击流量的。　　限流可以控制本软件或者应用的流量大小... 查看详情

如何阻止调度 Redux 操作的嵌套 React 组件，这些操作会更新状态，以免陷入无限循环？

】如何阻止调度Redux操作的嵌套React组件，这些操作会更新状态，以免陷入无限循环？【英文标题】：HowdoIstopnestedReactcomponentsthatdispatchReduxactionswhichupdatestatefromgettingstuckinaninfiniteloop?【发布时间】：2021-03-1912:45:44【问题描述】：我... 查看详情

使用具有多个参数和索引的lapply/sapply减少函数内的嵌套循环(代码片段)

我有两个观察向量，我想要计算哪些参数最适合这些观察。因此，我已经定义了似然函数。我正在努力从嵌套for循环到使用sapply。我的目标是返回观察“芽”概率的（50x1）向量。>bud[1]1.721.121.011.141.561.041.001.391.38[10]0.991.661.552.2... 查看详情

如何改进大数据的矢量化滑动窗口？

】如何改进大数据的矢量化滑动窗口？【英文标题】：Howtoimprovevectorizedslidingwindowforbigdata?【发布时间】：2021-02-2523:17:11【问题描述】：我需要在具有600万个时间步长和每个时间步长8个特征的时间序列上使用python中的滑动窗口。... 查看详情

c#减少嵌套循环(代码片段)

最近在解决性能优化的问题，看到了一堆嵌套循环，四五层级的循环真的有点过分了，在数据量成万，十万级别的时候，真的非常影响性能。当然，除了关注明显的循环例如for、foreach，还应该关注隐晦一点的循环，例如datatable.s... 查看详情

如何在 React Js 中使用 map 实现嵌套循环

】如何在ReactJs中使用map实现嵌套循环【英文标题】：HowtoimplementnestedloopusingmapinreactJs【发布时间】：2020-03-2519:06:13【问题描述】：我知道有很多线程已经回答了这个在reactjs中使用map的嵌套循环问题，但是我很困惑如何在我的代... 查看详情

循环滑动窗口迭代

】循环滑动窗口迭代【英文标题】：CyclicalSlidingWindowIteration【发布时间】：2015-05-2316:54:41【问题描述】：考虑一些给定的序列和窗口长度，比如lista=[13*i+1foriinrange(24)]（这样In[61]:aOut[61]:[1,14,27,40,...,287,300])和窗口长度3.我想取这个... 查看详情

如何实现“嵌套类型或无效”特征？

】如何实现“嵌套类型或无效”特征？【英文标题】：Howtoimplementa"eithernestedtypeorvoid"trait?【发布时间】：2021-01-2622:38:50【问题描述】：我正在处理一些可能定义了嵌套类型的类。每当没有定义这个嵌套类型时，我就假装... 查看详情

使用 Faust 的滑动窗口

...ust【发布时间】：2021-10-2909:22:22【问题描述】：有谁知道如何使用Faust实现滑动窗口？这个想法是在10、30、60和300秒的窗口中计算键的出现次数，但我们需要在1秒或每次更新的基础上进行。我有一个狡猾的解决方法，这似乎非常... 查看详情

使用 Faust 的滑动窗口

...ust【发布时间】：2021-10-2909:22:22【问题描述】：有谁知道如何使用Faust实现滑动窗口？这个想法是在10、30、60和300秒的窗口中计算键的出现次数，但我们需要在1秒或每次更新的基础上进行。我有一个狡猾的解决方法，这似乎非常... 查看详情

嵌套滑动吸顶效果(代码片段)

...吸顶效果，首先我们要先创造出“顶”来，那么如何创造“顶”呢？常见的实现方式有很多，比如：通过两个相同的顶部控件显示或隐藏来实现通过动态layout顶部控件来实现通过重写ItemDecoration来实现通过Coordi... 查看详情