滑动窗口算法

Ⅰ 滑动窗口技术工作原理

滑动窗口针对图像的算法的一般描述是:在规模为 W×H 的图像中，按一定规律移动 w×h 的窗口(W>>w， H>>h)，对窗口内像素点的像素值进行一系列运算，运算结束后窗口向右或向下移动一步，直到完成对整幅图像的处理。

如果问的是滑动窗口协议的话，网络随便搜索下，N多回答。

Ⅱ 算法总结之滑动窗口

滑动窗口类问题是面试当中的高频题，问题本身其实并不复杂，但是实现起来细节思考非常的多，想着想着可能因为变量变化，指针移动等等问题，导致程序反复删来改去，有思路，但是程序写不出是这类问题最大的障碍。
本文会将 LeetCode 里面的大部分滑动窗口问题分析、总结、分类，并提供一个可以参考的模版

滑动窗口这类问题一般需要用到 双指针 来进行求解，另外一类比较特殊则是需要用到特定的数据结构，如 Map，队列等。

题目问法大致有这几种

1 . 给两个字符串，一长一短，问其中短的是否在长的中满足一定的条件存在

2 . 给一个字符串或者数组，问这个字符串的子串或者子数组是否满足一定的条件

除此之外，还有一些其他的问法，但是不变的是，这类题目脱离不开主串（主数组）和子串（子数组）的关系，要求的时间复杂度往往是 O ( N ) O(N) O(N) ，空间复杂度往往是 O ( 1 ) O(1) O(1) 的。

根据前面的描述，滑动窗口就是这类题目的重点，换句话说， 窗口的移动 就是重点！我们要控制前后指针的移动来控制窗口，这样的移动是有条件的，也就是要想清楚在什么情况下移动，在什么情况下保持不变。
思路是保证右指针每次往前移动一格，每次移动都会有新的一个元素进入窗口，这时条件可能就会发生改变，然后根据当前条件来决定左指针是否移动，以及移动多少格。

无重复字符的最长子串

给定一个字符串，请你找出其中不含有重复字符的最长子串的长度。

示例

解题思路

输入只有一个字符串，要求子串里面不能够有重复的元素，这里 count 都不需要定义，直接判断哈希散列里面的元素是不是在窗口内即可，是的话得移动左指针去重。
建立一个 128 位大小的整型数组，用来建立字符和其出现位置之间的映射。维护一个滑动窗口，窗口内的都是没有重复的字符，去尽可能的扩大窗口的大小，窗口不停的向右滑动。

替换后的最长重复字符

给你一个仅由大写英文字母组成的字符串，你可以将任意位置上的字符替换成另外的字符，总共可最多替换 k 次。在执行上述操作后，找到包含重复字母的最长子串的长度。

示例

解题思路

最简单的方法就是把哈希散列遍历一边找到最大的字符数量，但是仔细想想如果我们每次新进元素都更新这个最大数量，且只更新一次，我们保存的是当前遍历过的全局的最大值，它肯定是比实际的最大值大的，我们左指针移动的条件是 right - left + 1 - count > k，保存的结果是 result = Math.max(result, right - left + 1)； 这里 count 比实际偏大的话，虽然导致左指针不能移动，但是不会记录当前的结果，所以最后的答案并不会受影响。

长度为 K 的无重复字符子串

给你一个字符串 S，找出所有长度为 K 且不含重复字符的子串，请你返回全部满足要求的子串的数目。

示例

解题思路

根据题意我们发现相当于窗口大小固定为K，同时在窗口内必须没有重复的字符。我们用左右指针可以计算出当前窗口的大小right - left + 1，同时再利用一个count对字符种类进行计数（也可以直接用一个boolean值即可），那么很容易可以得出当right - left + 1 > K 或者 count > 0时需要移动左指针了。剩下的部分就是愉快地套用模板啦。

至多包含两个不同字符的最长子串

给定一个字符串 s ，找出至多包含两个不同字符的最长子串 t 。

示例

解题思路

类似于上一题，不过我们用count来记录当前窗口内字符的种类数量，当出现新字符以及滑动左指针时，做相应的判断来改变count，窗口大小始终保持在满足条件至多两个不同字符的情况下。

至多包含 K 个不同字符的最长子串

给定一个字符串 s ，找出 至多 包含 k 个不同字符的最长子串 T。

示例

解题思路

和上一题完全一样的思路，只需要把判断窗口条件的地方改成 count > k ，又一题困难被我们直接秒杀。

下面来看看两个字符串的情况

最小覆盖子串

给你一个字符串 S、一个字符串 T，请在字符串 S 里面找出：包含 T 所有字母的最小子串。

示例

解题思路

同样是两个字符串之间的关系问题，因为题目求的最小子串，也就是窗口的最小长度，说明这里的窗口大小是可变的，这里移动左指针的条件变成，只要左指针指向不需要的字符，就进行移动。

字符串的排列

给定两个字符串 s1 和 s2，写一个函数来判断 s2 是否包含 s1 的排列。

示例

解题思路

首先窗口是固定的，窗口长度就是s1的长度，也就是说，右指针移动到某个位置后，左指针必须跟着一同移动，且每次移动都是一格，count 用来记录窗口内满足条件的元素，直到 count 和窗口长度相等即可。

找到字符串中所有字母异位词

给定一个字符串 s 和一个非空字符串 p，找到 s 中所有是 p 的字母异位词的子串，返回这些子串的起始索引。字符串只包含小写英文字母，并且字符串 s 和 p 的长度都不超过 20100。

示例

解题思路

和上一题完全一致的思路，窗口固定为p串的长度。

最后来看看数组类型的题吧
最大连续1的个数 III

给定一个由若干 0 和 1 组成的数组 A，我们最多可以将 K 个值从 0 变成 1 。返回仅包含 1 的最长（连续）子数组的长度。

示例

解题思路

这题有点像上面的 替换后的最长重复字符，只不过把字符串换成了数组，由于只有两种数字 0 和 1，并且只求连续 1 的长度，我们可以连 hash 映射都不需要了，直接计算遍历到的 0 的个数即可。

K 个不同整数的子数组

给定一个正整数数组 A，如果 A 的某个子数组中不同整数的个数恰好为 K，则称 A 的这个连续、不一定独立的子数组为好子数组。

示例

解题思路

这题比较 tricky 的一个地方在于，这里不是求最小值最大值，而是要你计数。
但是如果每次仅仅加 1 的话又不太对，例如 A = [1,2,1,2,3], K = 2 这个例子，假如右指针移到 index 为 3 的位置，如果按之前的思路左指针根据 count 来移动，当前窗口是 [1,2,1,2]，但是怎么把 [2,1] 给考虑进去呢？
可以从数组和子数组的关系来思考！
假如 [1,2,1,2] 是符合条件的数组，如果要计数的话，[1,2,1,2] 要求的结果是否和 [1,2,1] 的结果存在联系？这两个数组的区别在于多了一个新进来的元素，之前子数组计数没考虑到这个元素，假如把这个元素放到之前符合条件的子数组中组成的新数组也是符合条件的，我们看看这个例子中所有满足条件的窗口以及对应的满足条件的子数组情况：

你可以看到对于一段连续的数组，新的元素进来，窗口增加 1，每次的增量都会在前一次增量的基础上加 1。当新的元素进来打破当前条件会使这个增量从新回到 1，这样我们左指针移动条件就是只要是移动不会改变条件，就移动，不然就停止。

至此，本文用同一个框架解决了多道滑动窗口的题目，这类问题思维复杂度并不高，但是出错点往往在细节。记忆常用的解题模版还是很有必要的，特别是对于这种变量名多，容易混淆的题型。有了这个框架，思考的点就转化为 “什么条件下移动左指针”，无关信息少了，思考加实现自然不是问题。

Ⅲ [OpenJudge 3866] 滑动窗口〔单调队列〕

这是一篇题解笔记，这貌似被认为是一个经典题。题目链接： OpenJudge - 7:滑动窗口

总时间限制: 12000ms内存限制: 65536kB
描述
给定一个长度为n（n<=10^6）的数组。有一个大小为k的滑动窗口销迟从数组的最左端移动到胡斗态最右端。你可以看到窗口中的k个数字。窗口每次向右滑动一个数字的距离。
下面是一个例子：
数组是 [1 3 -1 -3 5 3 6 7]， k = 3。

你的任务是得到滑动窗口在每个位置时的最大值和最小值。

输入
输入包括两行。
第一行包括n和k，分别表示数组的长度和窗口的大小。
第二行包括n个数字。
输出
输出包括两行。
第一行包括窗口从左至右移动的每个位置的最小值。
第二行包括窗口从左至右移动的每个位置的最大值。
样例输入

样例输出

开始接触STL后，发现 set 和 map 真是强大好用，对这个题直接暴力用 multiset 模拟滑动窗口：

由于 set / multiset 底层是用红黑树实现，虽然是暴力，在OpenJudge上仍然能900ms通过。但是提交到 洛谷 上就有一个case超过1s报TLE，那就来研究一下此题“正确”的数据结构吧！

暴力做法使用的 set ，每次插入新的元素必须同时删除一个旧元素，旧元素在集合中的位置又必须通过再次查找得知，这当中查找、删除两步都在重复使用之前的时间戳确定的窗内其它元素的大小信息。我们不希望重复使用这些信息，毕竟整个过程中，我们关注的只是窗口内的最值。
应该采用更加简明的数据结构来存储这些数值，且它应该保存以下两个方面的信息：(1) 元素在数集内的 出现顺序 ，这方面较适合这里的情况的就是 队列 ；(2) 数集内的一种 层次大小结构 ，或者说单调结构，能够借其确保每次最大/最小值的询问都可以快速返回。这两条信息对应窗口的两个行为，一是元素的 进出 ，二是 最值 的询问。
有了这些前提，就可以动手设计这道题使用的数据结构（单调队列）了，其精巧地满足了我们的需求。在这个问题里，使用的是一个双端队列。

在窗口建立（从读入第一个数到读入第 size （窗口的大小）个数）和滑动的过程中，我们维护一个队列 ，它的行为和正常的队列一致，但是会自动淘汰那些不可能作为最小/大值询问结果的元素。以最小值为例，如果一个数 出现在数 的后边，但是比 和 都要小，那么在 插入以后，这两个数 就永远 没有机会 作为窗口的最小值输出。
要实现这一点，每当新元素要进入 ，我们都比较它与 前一个进入的元素（当前的 back ）的大小。如果新元素更小，则当前的 back 被淘汰，将它弹出，让下一个 back 与新元素比较；如果新元素更大或一路到达了 的头部，由于此后这元素可能成为最小值，将它先存储在队列的末尾。
我们只需再实现窗口左侧元素的弹出功能。好的情况下，让 弹出现存的第一个元素（ front ）即可；然而窗口左侧元素可能已经被淘汰， front 未必是它。不要紧，我们换成存储元素的下标，这样就能监测 的 front 是否该弹出了。
在整个算法中，我们做的比较几乎都是刚好必要的。每进入一个新元素，都至多需要 size 次比较，然而真正要这么多次比较的频率会很低（如果某次进入新元素需要 size 次比较，则说明窗口完全递增且新元素最小，而加入下一个元素要么会破坏这种递增，裤源要么会花费很少的比较次数，即不会总要比较 size 次），因此这个算法的性能应当是很好的。（2022/7/6 Edit：实际上直接可以看出均摊的时间复杂度为 。）

实际情况也是如此。采用单调队列后（用 std::list 实现），在OpenJudge上300ms通过：

Ⅳ 滑动窗口算法

在滑动窗口类型的问题中都会有两个指针，一个用于 延伸 现有窗口的 right 指针，和一个用于 收缩 窗口的 left 指针。在任意时刻，哪悄胡只有一个指针运动，而另一个保持静止。滑动窗口算法的时间复杂度为 ，因为 right 和 left 两个指针都只移动了 n 次。
该算法的大致逻辑如下：

接下来还是看几道典型的 leetcode 题目。

题目描述：

题目分析：
首先想到暴力解法，循环每个子区间，找到满足和大于等于 s 的子区间，更新最小长度。

此时时间复杂度 ，题目提示复杂度应为 ，那需要在常数次遍历中找到答案。在暴力解法中，我们先固定 i ，然后增加 j ，一次结束后，我们将 i 加 1 ，然后再循环 j ，重复的计算主要在这里。那是不是可以保持 j 在上一次循环结束的地方不动呢？我们知道上一次循环结束后 i 和 j 之间的子数组的和大于等于 s ，如果此时 j 不动，然后 i 加 1 ，那我们求得的和就需要减掉 nums[i] ，如果此时的子数组的和满足条件，那最小长度比开始更小了，那我们需要更新最小长度；如果此时子数组的和不满足条件，那我们继续增加 j ，来扩大子数组的长度。这也就是我们的滑动窗口思路。

题目描述：

联系滑动窗口算法，首先我们增大窗口，当条件满足时，缩小窗口。考虑到 t 中可能有重复字符，所以我们的判断条件还需要考虑每个字符的数量一致。

题目描述：

题目分析：
这道题需要关注的窗口为固定长度。我们先不考虑这个点，看看普通的滑动窗口解法：

这个李拦解法中，我们是等到子字符串满足条件了再来缩减窗口。由于题目所述为固定的窗口大小，那我们缩减窗口的条件可以改成如下形式：

题目描述：

和上一题类似，我们还是套运咐用滑动窗口模板：

题目描述：

题目分析：
题目的条件是无重复字符，那我们滑动窗口的条件便是：没有重复字符时，我们增大窗口，出现重复字符时我们缩小滑动窗口。需要注意的是我们更新结果再增加窗口的步骤中。

Ⅳ 四种限流算法原理

限流这里总结了四个算法分别是 计数器固定窗口算法、计数器滑动窗口算法、漏斗算法、令牌桶算法

计数器固定窗口算法是最基础也是最简单的一种限流算法。原理就是对一段固定时间窗口内的请求进行计数，如果请求数超过了阈值，则舍弃该请求；

如果没有达到设定的阈值，则接受该请求，且计数加1。当时间窗口结束时，重置计数器为0。

优点：实现简单容易理解

缺点： 流量曲线可能不够平滑，有"突刺现象"

计数器滑动窗口算法是计数器固定窗口算法的改进，解决了固定窗口切换时可能会产生两倍于阈值流量请求的缺点

滑动窗口算法在固定窗口的基础上，将一个计时窗口分成了若干个小窗口，然后每个小窗口维护一个独立的计数器，当请求的时间大于当前窗口的最大时间时，则将计时窗口向前平移一个小窗口。

平移时，将第一个小窗口的数据丢弃，然后将第二个小窗口设置为第一个小窗口，同时在最后新增一个小窗口，将新的请求放在新增的小窗口中。同时要保肢镇证整个窗口中所有小窗口的请求数目之后不能超过设定的阈值。

滑动窗口其实就是固定窗口的升级版。将计时窗口划分成一个小窗口，滑动窗口算法就退化成了固定窗口算法。而滑动窗口算法其实就是对请求数进行了更细粒度的限流。

窗口划分的越多，则限流越精准

请求来了之后会首先进到漏斗里，然后漏斗以恒定的速率将请求流出进行处理，从而起到平滑流量的作用。当请求的流量过大时，漏斗达到最大容量时会溢出，此时请求被丢弃。

从系统的角度来看，我们不知道什么时候会有请求来，也不知道请求会以多大的速率来，这就给系统的安全性埋下隐患。但是如果加了一层漏斗算法限流之后，就能晌陵够保证请求以恒定的速宴饥戚率流出。

在系统看来，请求永远是以平滑的传输速率过来，从而起到来保护系统的作用。

漏斗特点：

令牌桶算法是对漏桶算法的一种改进，除了能够在限制调用的平均速率的同时还允许一定程度的流量突发。

计数器固定窗口算法实现简单，容易理解。和漏斗算法相比，新来的请求也能够被马上处理到。但是流量曲线可能不够平滑，有"突刺现象"，在窗口切换时可能会产生两倍于阈值流量的请求。

而计数器滑动窗口算法作为计数器固定窗口算法的一种改进，有效解决了窗口切换时可能会产生两倍于阈值流量请求的问题

漏斗算法能够对流量起到整流的作用，让随机不稳定的流量以固定的速率流出，但是不能解决流量突发的问题。

令牌桶算法作为漏斗算法的一种改进，除了能够起到平滑流量的作用，还允许一定程度的流量突发。

没有最好的算法，只有最合适的算法

比如令牌桶算法一般用于保护自身的系统，对调用者进行限流，保护自身的系统不被突发的流量打垮。如果自身的系统实际的处理能里强于配置的流量限制时，可以允许一定程度的流量突发，使得实际的处理速率，充分利用系统资源。

而漏斗算法一般用于保护第三方的系统，比如自身的系统需要调用第三方的接口，为了保护第三方的系统不被自身的调用打垮，便可以通过漏斗算法进行限流，保证自身的流量平稳的达到第三方的接口上。

算法是死的，场景是活的。没有最好的，只有最合适的。

Ⅵ 什么是滑窗迭代算法

TCP的首部中有一个很重要的字段就是16位长的窗口大小，它出现在每一个TCP数据报中，配合32位的确认序号，用于向对端通告本地socket的接收窗口大小。也就是说，如果本地socket发送一个TCP数据，其32位确认序号是5,窗口大小是5840，则用于告诉对端，对端已经发出的4个字节的数据已经收到并确认，接下来，本地socket最多能够接收从第5个字节开始的5840个字节长度的数据。这是由接收方进行的一种流量控制，接收方通过告诉发送方自己所能够接收数据的大小，达到控制发送方发送速度的目的。
结构体struct tcp_sock中有很多成员数据跟滑动窗口协议相关，需要注意的是这里讲的滑动窗口都是指本地socket的接收窗口。
成员window_clamp表示滑动窗口的最大值，滑动窗口的大小在变化的过程中不能超出这个值。它在TCP连接建立的时候被初始化，被置为最大的16位整数左移窗口的扩大因子，因为滑动窗口在TCP首部中以16位表示，window_clamp太大会导致滑动窗口不能在TCP首部中表示。
成员rx_opt是一个struct tcp_options_received结构体，它有两个成员snd_wscale和rcv_wscale，分别表示来自对端通告的滑动窗口扩大因子(本地发送数据报时需要遵守)，和本地接收滑动窗口的扩大因子。snd_wscale从来自对端的第一个SYN中获取。rcv_wscale在本地socket建立连接时初始化，它赋值的原则是使16位整数的最大值左移rcv_wscale后，至少可以达到整个接收缓存的最大值。接收缓存最大值在协议栈中由全局变量mysysctl_rmem_max表示，它是256*(256+sizeof(struct sk_buff))后的值，为107520，但sysctl_tcp_rmem[3]所表示的接收缓存的上限更大，为174760，所以，取后者，这样的话，rcv_wscale的值几乎可以说是固定的，为2。所以window_clamp的值就是 65535 << 2 = 262140。可见，window_clamp的值超出了接收缓存的最大值，但这没有关系，因为在滑动窗口增长的时候，会考虑接收缓存的大小这个因素的。
rcv_wnd表示当前的接收窗口的大小，这个值在接收到来自对端的数据后，会变动的。它的初始值取接收缓存大小的3/4跟MAX_TCP_WINDOW之间的最小值，MAX_TCP_WINDOW在系统中的定义为32767U。然后，还要根据mss的值作一个调整，调整逻辑是：如果mss大于3*1460，则如果当前的rcv_wnd大于两倍的mss，就取两倍的mss作为rcv_wnd的值；如果mss大于1460，则如果当前的rcv_wnd大于3倍的mss，就取3倍的mss作为rcv_wnd的新值；否则，如果rcv_wnd大于4倍的mss,就取4倍的mss作为rcv_wnd的新值，我们的实验环境的mss值为1448(因为tcp首部有12字节的时间戳选项)，所以rcv_wnd最后被调整为1448*4=5792。

Ⅶ 请问如何用python编写滑动窗口算法

用ActionChains这个模块里面的drag_and_drop 元素或者drag_and_drop_by_offset坐标

Ⅷ 熔断限流

限流： 原理是监控应用流量的QPS或并发线程数等指标，当达到指定阈值时对流量进行控制，避免液则系统被瞬时的流量高峰冲垮，保障应用高可用性。保护自身系统防止被外部调垮。

熔断： 调用远程服务，后端服务不可避免的会产生调用失败（超时或者异常），防止应用程序不断地尝试可能超时和失败的服务，能达到应用程序执行而不必等待下游服务修正错误服务。

降级： 是指牺牲非核心的业务功能，保证核心功能的稳定运行。在后台通过开关控制，降级部分非主流程的业务功能，减轻系统依赖和性能损耗，从而提升集群的整体吞吐率。

 Hystrix 的关注点在于以隔离和 熔断 为主的容错机制，超时或被熔断的调用将会快速失败，并可以提供 fallback 机制。Hystrix 提供两种隔离策略： 线程池隔离（Bulkhead Pattern） 和 信号量隔离。

线程池隔离： 针对不同的资源分别创建不同的线程池，不同服务调用都发生在不同的线程池中，在线程池排队、超时等阻塞情况时可以快速失败，并可以提供 fallback 机制。好处是隔离度比较高，单独处理某个资源；代价就是线程上下文切换的 overhead 比较大，会让机器资源碎片化，特别是对低延时的调用有比较大的影响。

信号量隔离： 限制对某个资源调用的并发数，更为轻量，开销更小。但缺点是无法对慢调用自动进行降级，只能等待客户端自己超时，因此仍然可能会出现级联阻塞的情况。

Sentinel 和 Hystrix 的熔断降级功能本质上都是基于熔断器模式（Circuit Breaker Pattern）。Sentinel 与 Hystrix 都支持基于 失败比率（异常比率） 的熔断降级， 在调用达到一定量级并且失败比率达到设定的阈值时自动进行熔断 ，此时所有对该资源的调用都会被 block，直到过了指定的时间窗口后才启发性地恢复。 Sentinel 还支持基于平均响应时间的熔断降级，可以在服务响应时间持续飙高的时候自动熔断 ，拒绝掉更多的请求，直到一段时间后才恢复。这样可以防止调用非常慢造成级联阻塞的情况。

Hystrix 和 Sentinel 的实时指标数据统计实现都是基于滑动窗口的。

Sentinel：轻量级和高性能， 可以针对不同的调用关系，以 不同的运行指标（如 QPS、并发调用数、系统负载等） 为基准，对资源调用进行流量控制，将随机的请求调整成合适的形状。

熔断策略： 平均响应时间 (DEGRADE_GRADE_RT)：时间窗口内接口调用RT超过一定时巧碰间，下一时间窗口自动熔断； 异常比例 (DEGRADE_GRADE_EXCEPTION_RATIO) ：每秒调用时间异常比例超过一定阈值，自动熔断； 异常数 (DEGRADE_GRADE_EXCEPTION_COUNT)：当资源近 1 分钟的异常数目超过阈值之后会进行熔断。

流量控制(Flow Control)，原理是监控应用流量的QPS或并发线程数等指标，当达到指定阈值时对流量进行控制，避免系统被瞬时的流量高峰冲垮，保障应用高可用性。

流量整形策略： 直接拒绝模式 ：即超出的请求直接拒绝。

慢启动预热模式 ：当流量激增的时候，控制流量通过的速率，让通过的流量缓慢增加，在一定时间内逐渐增加到阈值上限，给冷系统一个预热的时间，避免冷系统被压垮。

匀速器模式： 利用 Leaky Bucket 算法实现的匀速模式，严格控制了请求通过的时间间隔，同时堆积的请求将会排队，超过超时时长的请求直接被拒绝。

常用限流算法：

①计数器限流算法

通过一个计数器，限制每一秒钟能够接收的请求数。周期内，超过阈值后的请求就会被全部拒绝。

②滑动窗口算法（sentinel使用）

滑动窗口算法是将时间周期分为N个小周期（窗口），分别记录每个小周期内访问次闹宽棚数，然后根据时间将窗口往前滑动，统计时间窗口内调用次数。

③漏桶限流算法

实现一个容器，容量固定，访问请求到达时直接放入漏桶，如当前容量已达到上限（限流值），则进行丢弃（触发限流策略）。漏桶以固定的速率进行释放访问请求（即请求通过），直到漏桶为空。实际上消息中间件就使用了漏桶限流的思想，不管生产者的请求量有多大， 消息的处理能力取决于消费者。

④令牌桶限流算法

令牌桶是网络流量整形（Traffic Shaping）和速率限制（Rate Limiting）中最常使用的一种算法。对于每一个请求，都需要从令牌桶中获得一个令牌，如果没有获得令牌，则需要触发限流策略。

Ⅸ perl中的滑动窗口是怎么回事啊

滑动窗口是一种特别的数据结构和算法吧，搭神岁打个比方，有一个1，2，3，4，5，6，7，8，9，10的序列，滑动窗口大小知睁为3，窗口从最左边进入序列，那么，窗口内的数据就应该是，
【1，2，3】，4，5，6，……这样，【】表示窗口，
当窗口向右移动，就成了瞎槐1，【2，3，4】，5，6，……这样，
你可以利用这个结构，很快的找到从第几位开始，接下来的窗口大小内的数据是什么，在研究DNA碱基序列中可以很方便，你只需从窗口中取出碱基序列就可以做相应的事情，如果不行，可以将窗口向前移动继续查找。

Ⅹ Redis 限制频繁请求拦截处理

项目运维人员发现NGINX日志中短时间内有同一IP、同一用户、同一设备发出的大量请求，比用户正常行为产生的请求频率要高出很多，所以有对单位时间内访问频次限制的需求。

一般就会在服务器端将用户信息和访问信息做下关联，以此来实现访问频次限制。通常大家都会选择 Redis 来作为此中间件的存储介质。

几种最常用的限流算法：

固定窗口计数器算法概念如下：

固定窗口计数器是最为简单的算法，但这个算法有时会让通过请求量允许为限制的两倍。考虑如下情况：限制 1 秒内最多通过 5 个请求，在第一个窗口的最后半秒内通过了 5 个请求，第二个窗口的前半秒内又通过了 5 个请求。这样看来就是在 1 秒内通过了 10 个请求。

滑动窗口计数器算法概念如下：

滑动窗口计数器是通过将窗口再细分，并且按照时间"滑动"，这种算法避免了固定窗口计数器带来的双倍突发请求，但时间区间的精度越春厅高，算法所需的空间容量就越大。

漏桶算法概念如下：

漏桶算法多使用 队列 实现，服务的请求会存到队列中，服务的提供方则按照固定的速率从队列中取出请求并执行，过多的请求则放在队列中排队或直接拒绝。

漏桶算法的缺陷也很明显，当短时间内有大量的突发请求时，即便此时服务器没有任何负载，每个请求也都得在队列中等待一段时间才能被响应。

令牌桶算法概念如下：

令牌桶算法既能够将所有的请求平均分布到时间区间内，又能接受服务器能够纯凯承受范围内的突发请求，因此是目前使扒裤隐用较为广泛的一种限流算法。

业务对此要求不高，所以用了简单的固定窗口计数器算法。