精华内容
下载资源
问答
  • 2021-10-18 19:57:16

    滑动窗口

    基本概念

    滑动窗口是一种基于双指针的一种思想,两个指针指向的元素之间形成一个窗口。

    分类:窗口有两类,一种是固定大小类的窗口,一类是大小动态变化的窗口。

    应用

    利用滑动窗口获取平滑的数据,如一段连续时间的数据平均值,能够有更好的稳定性,如温度监测。

    什么情况可以用滑动窗口来解决实际问题呢?

    1. 一般给出的数据结构是数组或者字符串
    2. 求取某个子串或者子序列最长最短等最值问题或者求某个目标值时
    3. 该问题本身可以通过暴力求解

    核心思路

    窗口的形成

    在具体使用之前,我们知道窗口实际是两个指针之间形成的区域,那关键就是这两个指针是如何移动的。

    1. 初始时,左右指针left,right都指向第0个元素,窗口为[left,right),注意这里是左闭右开,因此初始窗口[0,0)区间没有元素,符合我们的初始定义
      在这里插入图片描述

    2. 开始循环遍历整个数组元素,判断当前right指针是否超过整个数组的长度,是退出循环,否则执行第3步

    3. 然后right指针开始向右移动一个长度,并更新窗口内的区间数据

    在这里插入图片描述

    1. 当窗口区间的数据满足我们的要求时,右指针right就保持不变,左指针left开始移动,直到移动到一个不再满足要求的区间时,left不再移动位置

    在这里插入图片描述

    1. 执行第2步

    这中间,窗口的更新与维护是很重要的一环,新元素加入窗口,旧元素移出窗口,都需要及时地更新与这个窗口范围相关的数据。

    上述说明主要是两个while循环,可以简单抽象成一个模板如下:

    int left = 0,right =0;
    while(right指针未越界){
      char ch = arr[right++];
      //右指针移动,更新窗口
      ...
      
      //窗口数据满足条件 对于固定窗口而言,就是窗口的大小>=固定值;对于动态窗口,就是从left出发,窗口不断扩充,第一次满足题意的位置
      while(窗口数据满足条件){
      	//记录或者更新全局数据
      	...
      	
      	//右指针不动,左指针开始移动一位
      	char tmp = arr[left++];
      	
      	//左指针移动,窗口缩小,更新窗口数据
      	...
      }
      //返回结果
      ...
    }
    

    下面就结合所说的方法来看实际的栗子,主要的变化是窗口数据满足的条件,应该根据不同的要求来具体实现。

    实战

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

    给定两个字符串 s 和 p,找到 s 中所有 p 的 异位词 的子串,返回这些子串的起始索引。不考虑答案输出的顺序。
    
    异位词 指由相同字母重排列形成的字符串(包括相同的字符串)。
    
    输入: s = "cbaebabacd", p = "abc"
    输出: [0,6]
    解释:
    起始索引等于 0 的子串是 "cba", 它是 "abc" 的异位词。
    起始索引等于 6 的子串是 "bac", 它是 "abc" 的异位词。
    

    分析

    题目的意思从字符串s中选取固定长度的子串,使得子串和给出的p字符串的字符种类相同,且每一种字符的数量也相同,称之为异位词。要求求出所有符合要求的子串的起始位置。

    暴力的解法是选取所有子串然后与给定的字符串p进行比较,复杂度较高。

    使用滑动窗口的方法来解决,并且是个固定大小的滑动窗口。

    窗口内数据满足条件后,开始进行收缩,这个条件是窗口内的字符串和给出的字符串,字符种类一样,且每一类字符的数量也一致。从这个描述来看可以使用两个个map来记录数据,一个记录窗口内的字符种类和数量,记作window,这个map需要根据窗口的变化来实时更新;一个记录给定字符串的种类和数量,记作map,这是一个固定的map,不会更新。

    如果存在一个窗口,window和map相同,即字符种类和大小完全一样,那么当前的left是一个可行的位置,将其添加到集合。那如何判断map和window是一样的呢?暴力的方法,就是按每类字符去对比,字符种类一样,每类数量一致,复杂度是O(n),那有没有更好的方法呢?
    在这里插入图片描述

    事实上,我们就是要在移动指针形成窗口的过程中,判断window和map是否一致。map是固定的,可以按每一类字符来比较,初始化一个计数器valid=0,如果窗口内某类字符完全一致,那么valid加1,最后如果valid==map.size()那么说明我们找到了一个解。

    当然我们引入的valid,就需要根据窗口的更新来更新。

    窗口更新(移入数据)

    更新window:如果该字符在map中,那么需要加入到window计数器中;否则计数器不更新

    更新valid:数据移入窗口时,如果当前字符在给定的map中,我们要的字符种类出现了,如果这类字符的数量和给定map中该类字符的数量也一致,那么说明该类字符我们就搞定了。

    窗口更新(移出数据)

    更新valid:数据移出窗口时,如果该字符在map中,说明是我们要处理的字符,其字符数量和map中一致时,此时要移出窗口,valid要减1。

    更新window:如果该字符在map中,那window计数器对于该计数器需要减1

    具体代码如下:

        public List<Integer> findAnagrams(String s, String p) {
            List<Integer> res = new ArrayList<>();
    
            Map<Character, Integer> map = new HashMap<>();
            Map<Character, Integer> window = new HashMap<>();
    
            char[] pattern = p.toCharArray();
            char[] arr = s.toCharArray();
    
            for (char a : pattern) {
                map.put(a, map.getOrDefault(a, 0) + 1);
            }
            int left = 0, right = 0;
            int valid = 0;
            while (right < s.length()) {
                char ch = arr[right];
                right++;
                /**
                 * 新元素加入窗口:什么时候当前元素可以加入窗口并新增valid计数?
                 * 当前元素在 map 中,那么把它加入到window中,加入后,如果在窗口内 该元素的数量和要求该元素数量一致,那么valid++,即该元素满足要求
                 */
                if (map.containsKey(ch)) {
                    //加入窗口
                    window.put(ch, window.getOrDefault(ch, 0) + 1);
                    // 不能写== 比较的是两个地址
                    if (window.get(ch).equals(map.get(ch))) {
                        valid++;
                    }
                }
                //判断窗口内元素是否满足条件,两个条件:1)固定窗口,当前窗口数量等于 模式字符串p的长度 2)当前窗口内组成的字符串和模式字符串 是异位词
                while (right - left == p.length()) {
                    //固定窗口,判断当前窗口是否是异位词,如果是说明找到了一个位置,把left加入到结果集中
                    if (valid == map.size()) {
                        res.add(left);
                    }
                    //right 不动,左指针开始向右,arr[left]元素移出窗口,同时该元素在window中对于的数目也要减去1
                    char tmp = arr[left];
                    left++;
                    if (map.containsKey(tmp)) {
                        if (map.get(tmp).equals(window.get(tmp))) {
                            valid--;
                        }
                        window.put(tmp, window.get(tmp) - 1);
                    }
                }
            }
            return res;
        }
    

    LC76. 最小覆盖子串

    分析

    和LC438很相似,但是本题是一个动态窗口,解题方法同LC438也一致,只是不需要对窗口的大小进行限制。当窗口内的数据满足条件时,就可以进行窗口的收缩了。

    代码如下:

        public String minWindow(String s, String t) {
            int start = 0, len = s.length() + 1;
            char[] pattern = t.toCharArray();
            char[] arr = s.toCharArray();
            Map<Character, Integer> map = new HashMap<>();
            Map<Character, Integer> window = new HashMap<>();
    
            for (char a : pattern) {
                map.put(a, map.getOrDefault(a, 0) + 1);
            }
            int left = 0, right = 0, valid = 0;
            while (right < s.length()) {
                char ch = arr[right++];
                if (map.containsKey(ch)) {
                    window.put(ch, window.getOrDefault(ch, 0) + 1);
                    if (window.get(ch).equals(map.get(ch))) {
                        valid++;
                    }
                }
                //满足条件的窗口 这里不是固定窗口,对窗口大小不限制,当map和window中的数据一致,满足条件,开始收缩
                while (valid == map.size()) {
                    // 当前已经满足要求,更新并记录数据,同时收缩窗口
                    if (right - left < len) {
                        start = left;
                        len = right - left;
                    }
                    char tmp = arr[left++];
                    if (map.containsKey(tmp)) {
                 // 当前要移出的字符种类和数量和map一致,移出后不一致,valid--
                        if (window.get(tmp).equals(map.get(tmp))) {
                            valid--;
                        }
                        window.put(tmp, window.get(tmp) - 1);
                    }
                }
            }
            return len == s.length()+1 ? "" : s.substring(start, start + len);
        }
    

    事实上,当valid==map.size()时,在窗口window内可能出现比map中对应字符数量多的情况,但是valid并没有变大,是因为在更新valid的时候,只有与map中字符数目相同才更新,如果已经满足了该条件,那么只更新window,不更新valid。

    举个例子,s=“BBNAC”,t=“ABC”

    第一个满足条件的窗口,B字符出现了2次,但map中只出现了1次。

    在移出的时候,只有当当前窗口中该移出字符的数量刚好等于map中该字符的数量时,valid才会-1,表示当前窗口已经不满足要求了,第二个while循环也就不会再继续了,又开始进行right指针的移动了。
    在这里插入图片描述

    最后

    本文对滑动窗口类的一些问题进行了分析,总结了一个模板,并结合Leetcode上的一些例子进行了应用实战。Leetcode相关类型的例子还有LC3、LC513、LC1052等,可以参考利用上述方法进行练习。

    迟来的本周更新总算赶上了,希望后续能够保持,与君共勉!

    更多信息可关注微信公众号:惊鸿只为卿
    在这里插入图片描述

    欢迎点赞、关注、分享、在看!

    更多相关内容
  • Qt 实现 自定义窗口标题栏

    千次下载 热门讨论 2016-12-07 17:06:46
    以上代码用Qt实现了自定义窗口标题栏,非常实用,提供了窗口图标、窗口标题、最小化、最大化、关闭按钮等几个部分。可以应用到每一个窗口中去,保持每个窗口外观的一致性,同时自定义的标题栏也比系统自带的漂亮很多...
  • TCP滑动窗口详解

    千次阅读 多人点赞 2021-09-10 21:38:57
    滑动窗口的大小 发送窗口的大小要取决于接收窗口,如果发送窗口大于接收窗口的大小,会导致接收窗口无法完全接收数据包,导致一些数据包被丢弃,导致发送窗口的超时重传,浪费资源。 tcp报文头部中有一个window字段...

    相较于UDP,TCP有以下区别:
    1、可靠传输
    2、流量控制

    这两个功能都是依靠滑动窗口来实现的,本文就来解密TCP中的滑动窗口

    TCP实现可靠传输依靠的有 序列号自动重传滑动窗口确认应答等机制。

    序列号

    首先我们说下序列号,TCP中将要发送的数据包的每个字节都分配了序列号,用来唯一标识一个字节。序列号随着数据包的发送而增加。

    只有为每个字节分配一个序列号,每个数据包都对应着一个序列号区间,才能确定哪个数据包发送出现意外了。

    序列号的初始化是由操作系统分配的,是一个32位的数字。

    TCP初始化序列号不能设置为一个固定值,因为这样容易被攻击者猜出后续序列号,从而遭到攻击。

    RFC1948中提出了一个较好的初始化序列号ISN随机生成算法。

    ISN = M + F(localhost, localport, remotehost, remoteport).
    

    M是一个计时器,这个计时器每隔4us加1。

    F是一个随机算法,根据源IP、目的IP、源端口、目的端口生成一个随机数值。

    确认应答

    当接收方收到一个数据包后,会直接返回一个ACK包,或者延迟一段时间返回一个ACK包,一次性确认多个数据包。

    ACK包中有一个ack字段,代表着seq小于ack的数据包都已经被接收完毕。
    在这里插入图片描述

    自动重传 ARQ

    ARQ的详解分析可以看我的另一篇文章ARQ详解

    当TCP发送端发送了一个TCP数据包的时候,会设置一个定时器,如果在定时器期间没有收到接收方对这个数据包的确认应答包,也成为ACK包,就会重新发送对应的TCP数据包。

    自动重传有以下两个原因:
    1、数据包丢失
    2、ack数据包丢失

    在这里插入图片描述

    超时时间的选择
    超时时间既不能太长,又不能太短。

    超时时间过长存在的问题:
    当发生丢包的时候,需要等待好长时间才会重新发送,这个时候TCP就处于等待时期,什么也干不了,浪费资源,发送效率低下。

    超时时间过短存在的问题:
    如果超时时间太短,会发生多次发送重复包的情况。当ACK包还在路上的时候,由于超时时间太短而导致发送端重复的发送不必要的数据包。会加重网络的负担,导致网络阻塞等问题。网络发生阻塞的话,会进一步正反馈导致更多的重传。

    重传超时时间简称为RTO

    RTO是略大于RTT的。

    RTT指的是一个数据包从发送到接收到ACK确认包的花费时间,RTT是会随着网络的变化而变化,是会波动的。

    滑动窗口的出现原因

    滑动窗口 分为 发送窗口接收窗口

    发送窗口 用来 发送数据

    接收窗口 用来 接收数据

    客户端和服务器端 都有一个 发送窗口接收窗口

    在这里插入图片描述

    为什么会引入滑动窗口呢?

    如果不存在发送窗口的话,TCP发送一个数据包后会等待ACK包,因为必须要保存对应的数据包,数据包很有可能需要重新发送。

    这样的话发送效率会很慢。大部分时间都在等待。
    在这里插入图片描述

    引入了发送窗口,发送窗口的做法是:

    只要处于发送窗口范围中的数据包都可以被发送,不需要等待前面数据包的ack包。

    如果发送窗口的大小为3个TCP数据包,那么发送方就可以连续发送3个TCP数据包,而不用等待前2个数据包的ack包。

    在这里插入图片描述

    滑动窗口详解

    发送窗口

    在这里插入图片描述

    发送窗口存在于操作系统中开辟的一块缓冲区,用来存放当前需要发送的数据。本质是一个循环数组的实现。利用三个指针来维护相关的区域。

    发送窗口就是一个循环利用的缓冲区,应用层发送数据,就是往缓冲区中写入数据。收到ACK后,就相当于从缓冲区中移除数据,不过并不会真正移除数据,只需要后移对应的指针就可以了。

    应用层会将数据写入到缓冲区中,当超过缓冲区的最大地址后,就循环利用头部,覆盖头部的数据。

    发送缓冲区分为四个部分:

    1、已经收到ack包的数据
    已经收到ack包的数据,代表接收窗口已经接收了对应的数据,可以被新数据覆盖。

    2、已经发送还未接收到ack包的数据
    已经发送出去,但是还未收到接收方对应的ack包

    3、允许发送但是还未发送的数据
    允许发送但是还未发送的数据。

    4、不允许发送的数据。

    发送窗口之外的数据,排队等待后续发送。

    区间2 和 区间3 构成了发送窗口,两个区间的大小总和对应着发送窗口的大小

    TCP中用三个指针来区分这个四个部分
    在这里插入图片描述
    指针1: 指向第一个已发送但是未接收到ack的字节
    指针2: 指向第一个允许发送但是还未发送的字节
    指针3: 发送窗口的大小

    这时还允许发送数据,就会将可用窗口中的数据发送给接收窗口。

    在这里插入图片描述

    这个时候,可用窗口大小为0,这个时候会等待接收方发送ack包。

    如果这个时候如果接收一个ack包为37,这个时候发送窗口会向右边移动5位,52-56会变成可用窗口。
    在这里插入图片描述

    接收窗口

    接收窗口中的字节序列号都是与发送窗口一一对应的。
    在这里插入图片描述

    接收窗口也是存在于操作系统中开辟的一块缓冲区,用于接收数据。缓冲区本质是一个循环数组的实现。利用两个指针来维护相关的区域。

    接收窗口存在于一个循环利用的缓冲区,接收数据 就是往缓冲区中写入数据。应用层读取数据后,就相当于从缓冲区中移除数据,不过并不会真正移除数据,只需要后移对应的指针就可以了。

    当数据写入超过缓冲区的最大地址后,就循环利用头部,覆盖头部的数据。

    缓冲区分为三部分:
    1、应用层已经读取的数据
    已经接收到的数据,并且已经发送了ack包,并且已经被应用层读取。

    2、接收窗口中的数据
    接收窗口中存储的是当前允许被接收的数据。

    接收窗口允许无序接收数据包,所以接收窗口中有一部分数据接收到了,一部分没接收到,将无序的数据包直接缓存到接收窗口中。

    因为无序的接收数据包,接收窗口中是存在空隙的,因为先发送的数据包由于网络原因,反而可能会后到接收方。

    当数据包缓存到接收窗口中,就会返回ack包,ack包中会携带SACK信息,也就是选择重选信息。

    3、还未收到的数据
    还不能接收数据的区域,也就是接收窗口之外的数据。

    接收窗口由一个RCV_NEXT和接收窗口大小WND来维护。

    RCV_NEXT
    下一个希望接收的数据包的序列号,当接收到对应的数据包后,会将RCV_NEXT右移,右移到缓冲区中第一个为空的位置。

    同时将WND 减去 移动的个数。

    WND
    接收窗口的大小。

    WND有以下两种变化:

    1、接收窗口 有序的接收到对应的数据包,WND会减去对应的数据包长度。

    2、应用程序读取了数据包,会将WDN增加对应的数据包的长度

    接收窗口详情

    接收窗口接收数据包后,即使应用程序没有读取对应的数据包,也会立马返回ack应答包,ack应答包中会携带当前接收窗口的大小WND和接收窗口的数据包缓存信息。

    1、当数据包的seq == RCV_NEXT的数据包的时候,将接收窗口的RCV_NEXT右移到缓冲区中第一个为空的位置,WND减去对应的移动字节数;

    2、当数据包的seq > RCV_NEXT 并且 seq < RCV_NEXT+ WND的时候,会将其加入到滑动窗口中对应的位置。

    3、如果数据包的seq < RCV_NEXT,说明该数据包已经被接收了,但是对应的ack包因为阻塞或者异常没有发送到发送方。
    这时接收方会利用其发送窗口发送一个ack包。

    4、当应用程序将接收到的数据包读取之后,会将WND加上对应的读取数据包的大小。

    滑动窗口的大小

    发送窗口的大小要取决于接收窗口,如果发送窗口大于接收窗口的大小,会导致接收窗口无法完全接收数据包,导致一些数据包被丢弃,导致发送窗口的超时重传,浪费资源。

    tcp报文头部中有一个window字段,代表着接收窗口的接收数据能力,发送窗口会根据window字段来调整发送窗口大小,保证接收窗口正常接收数据包。

    发送窗口的大小不能超过接收窗口的大小,否则接收窗口不能正常接收数据。

    总结

    客户端和服务器都各自维护一个发送窗口和发送窗口,用来流水线模式的发送和接收数据。

    发送窗口和接收窗口的本质是在操作系统中开辟的一块循环利用的缓冲区,用于存储要发送和接收数据。本质是一个循环数组的实现。利用若干指针来维护相关的区域。当数据写入超过缓冲区的最大地址后,就循环利用头部,覆盖头部的数据。

    发送窗口就是一个循环利用的缓冲区,应用层发送数据,就是往缓冲区中写入数据。收到ACK后,就相当于从缓冲区中移除数据,不过并不会真正移除数据,只需要后移对应的指针就可以了。

    发送缓冲区分为四个部分:

    1、已经收到ack包的数据
    已经收到ack包的数据,代表接收窗口已经接收了对应的数据,可以被新数据覆盖。

    2、已经发送还未接收到ack包的数据
    已经发送出去,但是还未收到接收方对应的ack包

    3、允许发送但是还未发送的数据
    允许发送但是还未发送的数据。

    4、不允许发送的数据。

    发送窗口之外的数据,排队等待后续发送。

    区间2 和 区间3 构成了发送窗口,两个区间的大小总和对应着发送窗口的大小

    接收窗口接收数据包后,会立马返回ack应答包,即使应用程序没有读取对应的数据包。

    接收窗口也是一个循环利用的缓冲区,接收数据 就是往缓冲区中写入数据。应用层读取数据后,就相当于从缓冲区中移除数据,不过并不会真正移除数据,只需要后移对应的指针就可以了。

    接收窗口详情

    接收窗口接收数据包后,即使应用程序没有读取对应的数据包,也会立马返回ack应答包,ack应答包中会携带当前接收窗口的大小WND和接收窗口的数据包缓存信息。

    1、当数据包的seq == RCV_NEXT的数据包的时候,将接收窗口的RCV_NEXT右移到缓冲区中第一个为空的位置,WND减去对应的移动字节数;

    2、当数据包的seq > RCV_NEXT 并且 seq < RCV_NEXT+ WND的时候,会将其加入到滑动窗口中对应的位置。

    3、如果数据包的seq < RCV_NEXT,说明该数据包已经被接收了,但是对应的ack包因为阻塞或者异常没有发送到发送方。
    这时接收方会利用其发送窗口发送一个ack包。

    4、当应用程序将接收到的数据包读取之后,会将WND加上对应的读取数据包的大小。

    展开全文
  • Flink窗口-时间窗口

    千次阅读 热门讨论 2021-05-23 22:25:10
    时间窗口中,时间是什么时间?时间窗口特点是什么?

    (一)时间窗口的本质

    前篇中,我们已经初略讲解了Flink中的数量窗口与时间窗口。

    无论是哪一种窗口,他们的作用都类似于计算器(计算数量、时间)仅仅只是让数据堆积(不会像默认的流处理,来一条处理一条),只有当满足触发计算时机的时候,便开始计算,比如五个数据才计算,或者五秒钟才计算一次…

    image-20210523163345564

    时间窗口的核心,便是时间的定义,与数据窗口不同的是,我们只能定义时间窗口的时间范围,无法从定义上确定每个时间窗口元素的个数;比如我们定义了时间窗口五秒钟触发一次,但我们无法确定,上一个五秒与下一个五秒窗口中数据量一致…

    那么时间窗口究竟如何使用呢?时间指的是什么时间呢?哎,让我们来一探究竟!

    (二)Time

    时间窗口中时间指的是什么时间呢?

    Flink程序支持针对三种时间进行数据处理:EventTime、IngestionTime、ProcessingTime

    EventTime:事件时间

    即事件元素中本身的时间(通常指时间元素中含有某时间列)

    IngestionTime:摄入时间

    事件元素到达Flink的时间

    ProcessingTime:处理时间

    事件元素经过第一个Flink算子处理时的时间

    1.12版本默认是根据EventTime,之前版本默认是采用ProcessingTime

    我们可以手动指定根据什么时间来处理事件

    Ex:

    image-20210523221211689

    渐渐的,摄入时间(IngestionTime)越来越不推荐使用了,实际上就生产而言,我们更多选择是根据业务采用不同的窗口分配器,选择根据事件时间还是处理时间进行计算。

    image-20210523221358301

    (三)基于处理时间的时间窗口

    (1)滚动窗口

    官网示例

    image-20210524212020340

    时间滚动窗口核心代码

    image-20210524212228548

    时间间隔可以通过使用Time.milliseconds(x)Time.seconds(x)Time.minutes(x)…等等指定窗口大小(毫秒、秒、分、时、天…)。

    EX:设置了每隔五秒滚动一次,即每五秒触发一次窗口计算逻辑

    TumblingProcessingTimeWindows.of(Time.seconds(5))
    

    如果按照窗口区间来划分的话,将会是这样(假如第一个事件元素的处理时间为12点,那么每五秒滚动窗口生命周期将会按照如下进行)

    image-20210523222433020

    即每五秒窗口执行一次,但需要注意的是,由于我们采用了KeyBy ,每个不同的KEY 均会有各自的窗口不断触发,但仍每个并行度的subTask只能同时处理一个KEY的数据。

    代码示例

    image-20210524210518602

    public class TumbleWindowFunction extends RichWindowFunction<Location,List<Location>, Integer,TimeWindow> {
        public TumbleWindowFunction() {}
        String uuid;
        /**
         * @param window 当前窗口
         * @param locations 入站数据集合
         * @param out 出站数据收集器 泛型为出站数据类型
         */
        @Override
        public void apply(Integer integer, TimeWindow window, Iterable<Location> locations, Collector<List<Location>> out) {
            out.collect(Lists.newArrayList(locations));
        }
    
        @Override
        public void open(Configuration parameters) throws Exception {
            uuid = UUID.randomUUID().toString();
            System.out.println(uuid + "窗口打开了");
        }
    
        @Override
        public void close() throws Exception {
            System.out.println(uuid + "窗口关闭了");
        }
    }
    

    image-20210524210625885

    滚动窗口也是支持时间偏移量的

    // TumblingEventTimeWindows.of(窗口大小, 偏移量) 例如窗口大小为5s,偏移时间为5s
    TumblingEventTimeWindows.of(Time.seconds(5), Time.seconds(5))
    

    image-20210524213101420

    注意:偏移量必须小于窗口大小

    image-20210524213509213

    image-20210524213250285


    (2)滑动窗口

    image-20210524213633885

    image-20210524211627254

    时间滑动窗口核心代码

    // 设置窗口为滑动处理时间滑动窗口,且窗口大小为10s,滑动为5s 即每十秒,计算一次最近五秒的数据
    SlidingProcessingTimeWindows.of(Time.seconds(10), Time.seconds(5))
    

    滑动窗口也支持偏移量设置

    image-20210524213728699

    image-20210524214416337

    (3)偏移量说明

    如果窗口是基于事件时间,在中国时区内,必须指定的偏移量Time.hours(-8)


    (四)基于事件时间的时间窗口

    (1)为什么需要事件时间

    有时候,我们的业务决定了我们必须以事件事件进行处理

    比如,某用户在2021-05-24 11:59:28进行了支付操作,由于某原因(网络延迟、数据量过大…)此条支付消息到Flink时已经 2021-05-24 12:01:10了,如果我们现在要计算平台在2021-05-24 11:00-2021-05-24 12:00这个时间段的支付总量,那么此条数据就应包括进来…如果按照处理时间计算,那么此条数据归属窗口则是2021-05-24 12:01:10之内(后)了,就会导致2021-05-24 11:00-2021-05-24 12:00这个时间段的支付总量漏计算了数据。

    正是由于这些场景的存在,Flink推出了基于事件时间的处理窗口,根据事件本身的事件进行归属窗口分配,然后触发对应窗口计算

    (2)什么是事件时间

    事件时间,就是事件元素中,本身携带着的一列时间属性(必须为1970后的时间戳)

    (3)事件时间示例

    image-20210524222632865

    模拟定位数据源产生

    image-20210524222959442

    核心代码

    指定窗口分配器为TumblingEventTimeWindows,且窗口大小为10s

    TumblingEventTimeWindows.of(Time.seconds(10))
    

    启动Job发现…报错

    image-20210524222812703

    完整错误信息:

    Caused by: java.lang.RuntimeException: Record has Long.MIN_VALUE timestamp (= no timestamp marker).
        Is the time characteristic set to 'ProcessingTime', or did you forget to call 
        'DataStream.assignTimestampsAndWatermarks(...)'?
    

    错误意思是当前时间没有时间戳标记,您需要将其切换为基于处理时间ProcessTime进行作业或者是您忘记了设置Watermarks

    image-20210524223321045

    这难道不是时间戳标记吗?为什么还是提示说找不到时间戳标记呢?

    因为Flink不会识别事件中的时间列(避免属性中出现多个时间列无法选择),我们必须要手动指定事件元素的时间列属性

    根据错误提示,我们便来玩上一玩

    image-20210524223711088

    指定水印,设置事件时间列

    dataStreamSource.assignTimestampsAndWatermarks();

    我们先将DEMO跑起来,后边有watermaker-blog详细讲解水印机制

    EX:

    SingleOutputStreamOperator<Location> watermarks = locationSource.
        assignTimestampsAndWatermarks(WatermarkStrategy.
                                      <Location>forBoundedOutOfOrderness(Duration.ofSeconds(5))
                                      // 设置事件时间为devTime属性
                                      .withTimestampAssigner((event, timestamp) -> event.getDevTime()));
    

    image-20210524224049886
    先放出设置后运算结果吧,WaterMaker后边会详细讲到以及验证!

    image-20210526202050360

    (五)时间窗口大小说明

    时间窗口大小由size决定

    image-20210526223636949

    时间窗口运行示例:

    image-20210526223711582

    注意点:时间窗口大小为左闭右开属性,即**image-20210526223809615**窗口中,包含着12:00:05的数据,但不含12:00:10的数据

    注意:一个事件窗口窗口中最大的时间(根据窗口的类型 ,ex:所有元素中 最大的摄入时间、处理时间、事件时间)为窗口结束毫秒时间戳-1


    (六)时间窗口的生命周期

    (1)默认

    一旦应属于该窗口的第一个元素到达,就会创建一个窗口,并且当时间(事件时间、处理时间、摄入时间)超过其结束时间戳(可加上用户指定的时间)后 ,该窗口将被完全删除,Flink只会删除基于时间的窗口。

    Ex:采用基于处理时间的开窗策略,该策略每5分钟创建一次不重叠(或翻滚)的窗口

    现在第一个元素的处理时间为2021-05-26:12:00,那么Flink会创建一个2021-05-26 12:00 - 2021-05-26 12:05的时间窗口,当处理时间大于等于12:05时,便会触发该窗口进行计算,且计算后将此窗口删除,后续在无法打开2021-05-26 12:00 - 2021-05-26 12:05这个窗口

    (2)设置延迟

    但在使用事件时间窗口时,元素可能会延迟到达,Flink 用来跟踪事件时间进度的水印已经超过了元素所属窗口的结束时间戳。有关Flink 如何处理事件时间的更深入讨论,请参阅 事件时间,尤其是后期元素

    默认情况下,当水印超过窗口末尾时,将删除后期元素。但是,Flink 允许为窗口操作符指定最大允许延迟。Allowed lateness 指定元素在被丢弃之前可以延迟多少时间,其默认值为 0。 在 watermark 已经通过窗口末尾之后但在它通过窗口末尾之前到达的元素加上允许的延迟,仍然添加到窗口中。根据使用的触发器,延迟但未丢弃的元素可能会导致窗口再次触发。对于EventTimeTrigger.

    为了完成这项工作,Flink 会保持窗口的状态直到它们允许的延迟到期。一旦发生这种情况,Flink 会移除窗口并删除其状态,如窗口生命周期部分所述。

    默认情况下,允许的延迟设置为0。也就是说,到达水印之后的元素将被丢弃。

    展开全文
  • Mysql 窗口函数

    千次阅读 多人点赞 2022-03-04 23:36:32
    一, MySQl 8.0 窗口函数 窗口函数适用场景: 对分组统计结果中的每一条记录进行计算的场景下, 使用窗口函数更好; 可以跟Hive的对比着看: 点我, 特么的花了一晚上整理, 没想到跟Hive 的基本一致, 还不因为好久没复习...

    一, MySQl 8.0 窗口函数

    窗口函数适用场景: 对分组统计结果中的每一条记录进行计算的场景下, 使用窗口函数更好, 注意, 是每一条!! 因为MySQL的普通聚合函数的结果(如 group by)是每一组只有一条记录!!!

    可以跟Hive的对比着看: 点我, 特么的花了一晚上整理, 没想到跟Hive 的基本一致, 还不因为好久没复习博客了, 淦

    注意: mysql 因为没有array数据结构, 无法像Hive一样 行列进行转换;

    1.1 窗口函数分类

    • MySQL从8.0版本开始支持窗口函数。窗口函数的作用类似于在查询中对数据进行分组,不同的是,分组操作会把分组的结果聚合成一条记录,而窗口函数是将分组的结果置于每一条数据记录中
    • 窗口函数可以分为静态窗口函数动态窗口函数
      • 静态窗口函数的窗口大小是固定的, 不会因为记录的不同而不同;
      • 动态窗口函数的窗口大小会随着记录的不同而变化;

    窗口函数总体上可以分为序号函数, 分布函数, 前后函数, 首尾函数和其他函数;

    在这里插入图片描述

    1.2 语法结构

    • 窗口函数的语法结构:
      • 函数 OVER ([PARTITION BY 字段名 ORDER BY 字段名 ASC|DESC])
      • 或者是 函数 OVER 窗口名 … WInDOW 窗口名 AS ([PARTITION BY 字段名 ORDER BY 字段名 ASC|DESC])

    OVER 关键字指定窗口的范围;

    • 如果省略后面括号中的内容,则窗口会包含满足WHERE条件的所有记录,窗口函数会基于所有满足WHERE条件的记录进行计算。
    • 如果OVER关键字后面的括号不为空,则可以使用如下语法设置窗口。

    PARTITION BY 子句: 指定窗口函数按照哪些字段进行分组, 分组后, 窗口函数可以在每个分组中分别执行;
    ORDER BY 子句: 指定窗口函数按照哪些字段进行排序, 执行排序操作使窗口函数按照排序后的数据记录的顺序进行编号;
    FRAME 子句: 为分区中的某个子集定义规则, 可以用来作为滑动窗口使用;


    1.3 窗口函数🌰

    准备表和数据:

    • 创建表:
    
    CREATE TABLE goods(
    
        id INT PRIMARY KEY AUTO_INCREMENT,
        category_id INT,
        category VARCHAR(15),
        NAME VARCHAR(30),
        price DECIMAL(10,2),
        stock INT,
        upper_time DATETIME
    );
    
    • 插入数据:
    INSERT INTO goods(category_id,category,NAME,price,stock,upper_time)
    VALUES
    (1, '女装/女士精品', 'T恤', 39.90, 1000, '2020-11-10 00:00:00'),
    (1, '女装/女士精品', '连衣裙', 79.90, 2500, '2020-11-10 00:00:00'),
    (1, '女装/女士精品', '卫衣', 89.90, 1500, '2020-11-10 00:00:00'),
    (1, '女装/女士精品', '牛仔裤', 89.90, 3500, '2020-11-10 00:00:00'),
    (1, '女装/女士精品', '百褶裙', 29.90, 500, '2020-11-10 00:00:00'),
    (1, '女装/女士精品', '呢绒外套', 399.90, 1200, '2020-11-10 00:00:00'),
    (2, '户外运动', '自行车', 399.90, 1000, '2020-11-10 00:00:00'),
    (2, '户外运动', '山地自行车', 1399.90, 2500, '2020-11-10 00:00:00'),
    (2, '户外运动', '登山杖', 59.90, 1500, '2020-11-10 00:00:00'),
    (2, '户外运动', '骑行装备', 399.90, 3500, '2020-11-10 00:00:00'),
    (2, '户外运动', '运动外套', 799.90, 500, '2020-11-10 00:00:00'),
    (2, '户外运动', '滑板', 499.90, 1200, '2020-11-10 00:00:00');
    

    下面针对goods表中的数据来验证每个窗口函数的功能。

    1. 序号函数

    序号函数是按照一定的分组规则对每一组的数据排序并创建一个序号列

    1.1 row_number() - 单纯的对每一组数据编号

    函数功能
    row_number() 对数据中的序号进行顺序显示

    [案例]

    1.1 查询 goods 数据表中每个商品分类下价格降序排列的各个商品信息。

    
    SELECT 
    	*,
    	ROW_NUMBER() OVER (PARTITION BY category ORDER BY price DESC) AS row_num
    FROM goods;
    

    在这里插入图片描述

    1.2 查询 goods 数据表中每个商品分类下价格最高的3种商品信息。

    SELECT 
    	*	
    FROM 
    	(
    	SELECT 
    		*,
    		ROW_NUMBER() OVER (PARTITION BY category ORDER BY price DESC) AS top3Price 
    	FROM goods
    	) AS t
    
    WHERE 
    	top3Price <= 3
    

    在这里插入图片描述

    在名称为“女装/女士精品”的商品类别中,有两款商品的价格为89.90元,分别是卫衣和牛仔裤。两款商品的序号都应该为2,而不是一个为2,另一个为3。此时,可以使用RANK()函数和DENSE_RANK()函数解决;

    1.2 rank() - 排序每一组的某一字段, 同等级同序号前后不连续

    函数功能
    rank()对序号进行并列排序, 指定字段数值相同(同一等级),则会产生相同序号记录,且产生序号间隙,
    如, 1,1,3,4 而不会是 1,2,3,4(row_number的结果), 也不是 1,1,2,3,4 (dense_rank的结果)
    rank函数没有参数,但需要指定按照那个字段进行排名,所以使用rank函数必须用order by参数,order by的排序字段就是排名字段

    1.3

    在这里插入图片描述

    1.4 使用RANK()函数获取 goods 数据表中类别为“女装/女士精品”的价格最高的4款商品信息。

    // 常规思路
    SELECT *
    FROM goods
    WHERE category = '女装/女士精品'
    ORDER BY price DESC
    LIMIT 4
    
    #窗口函数rank: 并列
    SELECT 
    	*,
    	RANK() OVER (PARTITION BY category ORDER BY price DESC) AS top4Price
    FROM 
    	goods
    WHERE 
    	category = '女装/女士精品'
    LIMIT 4;
    

    在这里插入图片描述

    1.3 dense_rank() - 排序每一组的某一字段, 同等级同序号前后也连续

    函数功能
    dense_rank()对序号进行并列排序, 指定字段数值相同(同一等级),则会产生相同序号记录,且产生序号间隙,

    1.5

    在这里插入图片描述

    1.6

    在这里插入图片描述

    可以看到,使用DENSE_RANK()函数得出的行号为1、2、2、3,相同价格的商品序号相同,且后面的商品序号是连续的

    2. 分布函数

    2.1 percent_rank() - 等级值百分比, (rank - 1)/ (rows - 1)

    函数功能
    percent_rank()计算分区或结果集中行的百分位数排名
    每行按照公式(rank-1)/ (rows-1)进行计算。其中,rank为RANK()函数产生的序号rows当前窗口(当前组)的总行数

    在这里插入图片描述

    2.2 cume_dist() - 累积分布值, <=当前rank值的行数 / 分组内总行数

    函数功能
    cume_dist()分组内<=当前rank值的行数 / 分组内总行数

    在这里插入图片描述

    3. 前后函数

    3.1 LAG(expr, n) - 返回当前行的前n行(本组内)的expr值

    函数功能
    LAG(expr, n)返回当前行的前n行(本组)的expr值
    lag允许你在每一个分组内, 从当前行向前看n行数据
    n(也叫offset)是从当前行偏移的行数,以获取值。offset必须是一个非负整数。如果offset为零,则LAG()函数计算当前行的值。如果省略 offset,则LAG()函数默认使用n=1, 向前看一个数据。

    在这里插入图片描述

    3.2 LEAD(expr, n)

    函数功能
    LEAD(expr, n)返回当前行的后n行(本组)的expr值

    在这里插入图片描述

    4. 首位函数

    4.1 first_value(expr) , last_value(expr)

    在这里插入图片描述

    5. 其他函数

    5.1 nth_value(expr, n)

    在这里插入图片描述

    5.2 ntile(n)

    在这里插入图片描述

    展开全文
  • MFC普通窗口重绘

    热门讨论 2013-09-20 10:34:11
    MFC普通窗口重绘,有什么不懂的可以随时到我的博客留言http://www.gymsaga.com/,我会尽早解答您的问题,更多MFC实例讲解,请登陆我的博客。
  • VC++界面编程之--阴影窗口实现详解

    热门讨论 2013-09-14 20:22:46
    对于我们这些控件狂来说,窗口阴影也是一个必不可少的实现需求。虽说其没多大用,但对于增加窗口立体感来说,那是挺有帮助的。 我实现了一个类似于360界面的阴影效果,其可以支持正常窗口,也支持半透明窗口。 阴影...
  • 文章目录一、前言二、使用Spy++工具分析窗口三、C#通过Windows API捕获窗口,获取窗口文本四、附录:Windows窗口消息 一、前言 项目是Unity开发的,上架了QQ游戏大厅,需要兼容XP系统。 QQ游戏大厅启动游戏的流程是...
  • 对于多窗口的情况,一般有两种解决方法:一种是主窗口获取子窗口中控件的属性,另一种是通过信号与槽机制,一般是子窗口通过发射信号的形式传递数据,主窗口的槽函数获取这些数据。
  • 有KEY窗口和无KEY窗口的区别是什么?各自特性是什么?
  • 电脑关闭窗口快捷键

    千次阅读 2021-08-02 01:17:15
    一、电脑上关闭所有窗口的快捷键Alt+F4,关闭当前所有窗口。电脑中关闭窗口的快捷方法:工具/原料电脑方法/步骤1、关闭当前窗口,按住键盘上的ALT键不放,再按下F4键。2、依次关闭多个窗口,按一次Alt+F4键即可关闭...
  • 做 Windows 桌面应用开发的小伙伴们对“模态窗口”(Modal Dialog)一定不陌生。如果你希望在模态窗口之上做更多的事情,或者自己实现一套模态窗口类似的机制,那么你可能需要了解模态窗口的本质。 本文不会太深,...
  • tkinter创建嵌套子窗口

    千次阅读 2020-08-23 16:34:34
    纯tkinter实现嵌套子窗口
  • 窗口函数

    千次阅读 2021-01-11 19:12:30
    关于使用窗口函数 当你使用group by分区时,窗口函数的范围为group by分区的范围,即: select name, count(*)over(rows between UNBOUNDED PRECEDING and current row) from business where date_format...
  • 窗口后台鼠标连点器

    热门讨论 2012-08-01 19:12:03
    窗口后台鼠标连点器,在后台同时操作多个窗口。切换到一个窗口上,只需要将鼠标移动到需要连点的地方,然后按F2就可以启动连点了,再按F2该窗口停止。可以自由设置单击鼠标间隔时间及单击方式,使用非常简单
  • 现在,很多的操作系统都是视窗操作系统,比如:Windows、...1、窗口的组成1)边框和工作区 每个窗口都有四个边,将鼠标移到边上,指针会变成双箭头,这时拖动就可以改变窗口的大小,中间就是工作区;2)标题栏 每个...
  • MySQL - SQL窗口函数

    千次阅读 多人点赞 2019-11-25 13:08:19
    窗口函数解决的问题包括:1)排名问题2)top N问题 应用工作中, 面试中. 2.学习/操作 //注意,mysql版本8已至此窗口函数这个功能, 如果低于该版本, 会出现SQL报错! 一.窗口函数有什么用...
  • 使用C++编写一个可视化窗口

    万次阅读 多人点赞 2021-02-17 04:01:49
    初学C++时,控制台会给我们提供一个黑窗口,而这篇文章所做的就是:创建一个属于图形界面窗口,而不是使用控制台黑窗口 如图,这是一个标题为XSZY的窗口 看完这篇文章,你想要的窗口大小,图标等都可以自己定义 甚至...
  • //发送此消息给MDI子窗口当用户点击此窗口的标题栏,或当窗口被激活,移动,改变大小 WM_QUEUESYNC = &H0023; //此消息由基于计算机的训练程序发送,通过WH_JOURNALPALYBACK的hook程序分离出用户输入消息 WM_...
  • 滑动窗口协议(GBN, SR)

    千次阅读 2021-10-22 15:59:28
    文章目录前言一、流水线协议二、滑动窗口协议1.GBN(回退N重传协议)2.SR(选择重传协议)总结 前言 提示:以下是本篇文章正文内容 一、流水线协议 我们知道Rdt 3.0: 停等操作过程中浪费了大量的时间: 从而在Rdt ...
  • 滑动窗口算法

    千次阅读 多人点赞 2019-07-13 22:02:14
    什么是滑动窗口算法 我们学习过计算机网络都知道为了避免拥塞发生,在网络传输时有滑动窗口协议控制传输时流量。该协议允许发送方在停止并等待确认前发送多个数据分组。由于发送方不必每发一个分组就停下来等待确认...
  • 获取窗口句柄

    千次阅读 2021-02-12 13:34:51
    1、使用FindWindow函数获取窗口句柄示例:使用FindWindow函数获取窗口句柄,然后获得窗口大小和标题,并且移动窗口到指定位置。#include #include #include #include int main(int argc, char* argv[]){//根据窗口名...
  • Flink SQL中的窗口函数

    千次阅读 2020-07-22 18:48:48
    1 OVER窗口       OVER窗口(OVER Window)是传统数据库的标准开窗,不同于GROUP BY Window,OVER Window中的每一个元素都对应一个窗口窗口元素是与当前元素相邻的元素集合,流数据...
  • Flink窗口-计数窗口(CountWindow)

    千次阅读 2021-05-23 17:56:38
    文章目录 Flink窗口-CountWindow使用 (一)数量窗口的本质 (二)数量窗口的使用 (1)调用Window API (2)Window触发时执行计算逻辑 ① 匿名内部类方式 ② 自定义WindowFunction ③ 示例演示 Flink窗口-Count...
  • JavaScript Window窗口对象

    千次阅读 多人点赞 2020-01-18 11:49:05
    文章目录一、Window对象概述1、Window对象属性2、Window对象方法3、如何使用二、对话框1、警告对话框2、确认对话框3、提示对话框三、打开与关闭窗口1、打开窗口2、关闭窗口(1)关闭当前窗口(2)关闭子窗口四、控制...
  • 1、摘要 Transformer在NLP领域取得不错表现,如何更好地处理图像成为行业所面临地问题。...移位窗口方案将自我注意计算限制在非重叠的局部窗口上,同时允许跨窗口连接,从而提高了效率。 ...
  • 算法学习之滑动窗口(java版)

    千次阅读 2020-07-13 21:56:20
    算法学习之滑动窗口(java版) 文章目录算法学习之滑动窗口(java版)框架例题最小覆盖子串字符串排列找所有字母异位的词最长无重复子串总结 滑动窗口实际上是通过双指针实现的,[left,right]之间的范围就是窗口。通常...
  • CSS3/jQuery自定义弹出窗口 多种弹出动画

    千次下载 热门讨论 2014-06-01 21:09:31
    这是一款利用jQuery和CSS3实现的自定义弹出窗口,这可比浏览器默认的弹出窗口漂亮多了。弹出窗口中可以自定义html,十分灵活。另外最重要的一个特点是,它利用了jQuery和CSS3可以实现很多种弹出窗口动画效果,挺酷的...
  • Qt窗口自适应窗口大小的设置方法

    千次阅读 2021-07-12 10:15:21
    对于在窗口中的各个窗口控件(如groupbox)进行栅格布局,最后再对整个窗口进行栅格布局,最后即实现了窗口中所有控件随窗口大小调整。 2、窗口中表格自适应内容长度的设置 窗口的表格设置成自动适应表格...
  • 展开全部首先分析需要32313133353236313431303231363533e4b893e5b19e31333363376530的GUI技术...窗口使用(JFrame),按钮使用(JButton)。设想一个符合题目需求的场景两个窗口关联并且跳转,最常见的场景就是登陆了。...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 2,691,623
精华内容 1,076,649
关键字:

窗口