你只要接觸過網(wǎng)絡(luò)編程、算法刷題、信號(hào)處理或者FPGA開發(fā)中的任何一個(gè)方向大概率都被“滑動(dòng)窗口”這個(gè)詞撞翻過。問題是這四個(gè)方向里的人說起滑動(dòng)窗口腦中浮現(xiàn)的東西完全不是一回事搞網(wǎng)絡(luò)的想到的是TCP頭里的16位窗口字段刷題的想到的是雙指針和雙端隊(duì)列做信號(hào)的想到的是均值濾波的那一排移位寄存器寫Verilog的則盯著時(shí)鐘沿上那一串?dāng)?shù)據(jù)搬移。但它們的名字都叫滑動(dòng)窗口而且底層邏輯出奇地一致在連續(xù)的數(shù)據(jù)流上用一個(gè)固定大小的窗格一格一格地往前平移只關(guān)注窗格內(nèi)的那部分信息。這篇東西我想把滑動(dòng)窗口的幾個(gè)典型戰(zhàn)場(chǎng)從頭到尾串一遍。不是教科書式的逐條背誦而是站在實(shí)際工程和面試、筆試的交叉點(diǎn)上講清楚它為什么好使、在哪里容易翻車、以及不同領(lǐng)域之間那些能互相借用的思路。適合三類人看正在準(zhǔn)備網(wǎng)絡(luò)和算法方向面試的開發(fā)者、做嵌入式或者信號(hào)采集時(shí)需要濾波方案的硬件工程師、以及純粹想搞明白“為啥哪哪都有它”的技術(shù)愛好者。1. 為什么幾乎所有技術(shù)方向都在聊“滑動(dòng)窗口”滑動(dòng)窗口不是某一個(gè)算法的名字而是一類處理連續(xù)數(shù)據(jù)問題的通用思路。它的核心動(dòng)作就四個(gè)字固定大小、整體平移。數(shù)據(jù)源源不斷涌過來你不可能全部記住那就定義一個(gè)容積固定的窗口只管窗口內(nèi)的數(shù)據(jù)窗口往前挪一步扔掉隊(duì)尾的舊數(shù)據(jù)納入隊(duì)首的新數(shù)據(jù)。這個(gè)思路之所以被網(wǎng)絡(luò)、算法、信號(hào)處理、硬件設(shè)計(jì)同時(shí)選中是因?yàn)樗谡鎸?shí)場(chǎng)景里命中了一個(gè)共同的痛點(diǎn)數(shù)據(jù)是無限的但計(jì)算資源和存儲(chǔ)資源是有限的。TCP要在一個(gè)不可靠的網(wǎng)絡(luò)上實(shí)現(xiàn)可靠、高效的傳輸不可能把已經(jīng)發(fā)出去的所有數(shù)據(jù)都留著等確認(rèn)那樣內(nèi)存直接爆掉算法題里求一個(gè)幾千萬元素的數(shù)組的連續(xù)子數(shù)組最大值每次重新遍歷窗口內(nèi)的k個(gè)元素復(fù)雜度是O(n*k)數(shù)據(jù)量一大就完蛋傳感器數(shù)據(jù)源源不斷往外吐單片機(jī)不可能把所有歷史采樣點(diǎn)都存下來做平均只能記住最近N個(gè)點(diǎn)。滑動(dòng)窗口解決的就是在“資源有限”和“數(shù)據(jù)無限”之間找到那個(gè)可操作的折中。從另一個(gè)角度看滑動(dòng)窗口的本質(zhì)是對(duì)時(shí)間或空間局部性的利用。絕大部分連續(xù)數(shù)據(jù)都有這么個(gè)特點(diǎn)相隔很近的數(shù)據(jù)之間關(guān)聯(lián)性強(qiáng)相隔很遠(yuǎn)的數(shù)據(jù)基本沒關(guān)系。TCP里的確認(rèn)和重傳只需要關(guān)心發(fā)送窗口內(nèi)的包圖像濾波只需要關(guān)心鄰域內(nèi)的像素溫度傳感器當(dāng)前時(shí)刻的讀數(shù)跟五分鐘前的相關(guān)性很弱跟前幾個(gè)采樣點(diǎn)的相關(guān)性才強(qiáng)。滑動(dòng)窗口就是這種局部性的數(shù)學(xué)化表達(dá)你要做決策只需要局部的信息不需要全局的信息。所以學(xué)習(xí)滑動(dòng)窗口的正確姿勢(shì)是把它當(dāng)作一種“建模視角”來理解而不是背幾個(gè)代碼模板。先掌握它在不同場(chǎng)景下的形態(tài)再反過來看它的本質(zhì)你就會(huì)發(fā)現(xiàn)網(wǎng)絡(luò)里的rwnd、算法里的雙指針、濾波里的平均值本質(zhì)上都在做同一件事在一個(gè)有限的窗口內(nèi)利用局部信息完成對(duì)無限數(shù)據(jù)流的處理。2. TCP滑動(dòng)窗口流量控制、擁塞控制背后那套連續(xù)傳數(shù)據(jù)邏輯網(wǎng)絡(luò)側(cè)的滑動(dòng)窗口是TCP協(xié)議最核心的機(jī)制之一。面試?yán)锍柕娜挝帐?、流量控制、擁塞控制慢啟?dòng)、快重傳、快恢復(fù)全部跟窗口有關(guān)。但很多人把這三個(gè)概念背得滾瓜爛熟一問“窗口到底是怎么動(dòng)的”就卡殼。我盡量用一段實(shí)際的數(shù)據(jù)傳輸過程把這幾個(gè)概念全部串起來。2.1 三次握手里埋下的初始窗口契約TCP建立連接三次握手有SYN、SYNACK、ACK三個(gè)報(bào)文。很多教材只強(qiáng)調(diào)了“雙方確認(rèn)彼此收發(fā)能力”卻忽略了一個(gè)重要細(xì)節(jié)前兩次握手時(shí)雙方就已經(jīng)在通告自己的接收窗口大小了。SYN報(bào)文里有窗口字段SYNACK報(bào)文里也有窗口字段雖然SYN報(bào)文里這個(gè)字段往往沒被大家注意但它已經(jīng)向?qū)Χ诵媪恕拔业慕邮站彌_區(qū)現(xiàn)在能裝下多少數(shù)據(jù)”。三次握手結(jié)束之后連接的雙方各自持有兩個(gè)關(guān)鍵數(shù)字自己的發(fā)送窗口受對(duì)端通告的接收窗口限制和對(duì)端的接收窗口自己通告的。這個(gè)時(shí)候一個(gè)可以開始發(fā)數(shù)據(jù)的管道就建好了。如果中間有人把連接建立過程抓包下來看會(huì)在第二個(gè)報(bào)文的Options里看到窗口擴(kuò)大因子Window Scale這個(gè)字段同樣被很多人忽略但它關(guān)系到窗口字段只有16位上限的問題。TCP頭里的窗口字段只有16位最大值65535字節(jié)也就是64KB這在局域網(wǎng)里還行在高速長(zhǎng)距離鏈路上遠(yuǎn)遠(yuǎn)不夠。窗口擴(kuò)大因子通過選項(xiàng)協(xié)商最多能將窗口左移14位也就是擴(kuò)大到1GB級(jí)別。實(shí)際抓包時(shí)如果你發(fā)現(xiàn)窗口數(shù)值特別大多半就是帶了Scale因子。2.2 接收窗口與發(fā)送窗口流量控制的實(shí)際動(dòng)作連接建立起來之后數(shù)據(jù)開始流動(dòng)。發(fā)送方并不是一股腦把能發(fā)的全發(fā)出去它維護(hù)著一個(gè)發(fā)送窗口窗口大小等于對(duì)端通告的接收窗口rwnd和本地?fù)砣翱赾wnd中的較小值。為什么取較小值因?yàn)榻邮沾翱谑墙邮辗降奶幚砟芰ι舷迵砣翱谑蔷W(wǎng)絡(luò)路徑的承載能力上限木桶效應(yīng)哪個(gè)小聽哪個(gè)。接收方通告的rwnd反映的是接收緩沖區(qū)實(shí)時(shí)的剩余空間。接收方每發(fā)一個(gè)ACK都會(huì)在TCP頭的窗口字段里填上最新的剩余緩沖大小。這里有一個(gè)特別容易誤解的點(diǎn)ACK的作用不只是確認(rèn)數(shù)據(jù)到了它同時(shí)還在“開閘”。如果接收方應(yīng)用程序處理數(shù)據(jù)的速度跟不上接收速度接收緩沖區(qū)就會(huì)逐漸被占滿rwnd會(huì)越來越小直到變成0。當(dāng)發(fā)送方收到窗口為0的通告就必須停下來進(jìn)入持續(xù)計(jì)時(shí)器Persist Timer狀態(tài)周期性發(fā)送窗口探測(cè)報(bào)文問問接收方“緩沖騰出來了嗎”。這整個(gè)機(jī)制就是流量控制最樸素的樣子讓發(fā)送方的速度適配接收方的速度。2.3 擁塞控制慢啟動(dòng)、快重傳、快恢復(fù)窗口如何動(dòng)態(tài)變化流量控制管的是收發(fā)兩端的能力匹配擁塞控制管的則是一條鏈路或者一個(gè)網(wǎng)絡(luò)路徑的承載能力。接收方緩沖區(qū)明明是空的但如果發(fā)送方拼命往網(wǎng)絡(luò)里灌數(shù)據(jù)路由器可能撐不住出現(xiàn)丟包所以TCP還得自己限速。這個(gè)限速就是通過調(diào)整擁塞窗口cwnd實(shí)現(xiàn)的。慢啟動(dòng)名字聽著慢實(shí)際一點(diǎn)都不慢。連接剛建立cwnd通常初始化為一個(gè)MSS最大報(bào)文段長(zhǎng)度然后每收到一個(gè)ACKcwnd增加一個(gè)MSS。指數(shù)級(jí)增長(zhǎng)發(fā)1個(gè)包等確認(rèn)確認(rèn)后cwnd變成2再發(fā)2個(gè)確認(rèn)后變成4、8、16……一直到ssthresh慢啟動(dòng)門限。超過門限之后進(jìn)入擁塞避免階段cwnd的增速從指數(shù)變成線性每經(jīng)過一個(gè)RTT增加一個(gè)MSS。判斷網(wǎng)絡(luò)是否擁塞TCP用丟包作為主要信號(hào)。如果發(fā)生超時(shí)重傳說明網(wǎng)絡(luò)已經(jīng)堵得很厲害ssthresh會(huì)減半cwnd直接回到初始值重新慢啟動(dòng)。如果是快速重傳收到3個(gè)重復(fù)ACK說明有個(gè)包丟了但后續(xù)數(shù)據(jù)還在流通則進(jìn)入快恢復(fù)ssthresh減半cwnd設(shè)為新的ssthresh然后繼續(xù)線性增長(zhǎng)。這套機(jī)制翻譯成人話就是網(wǎng)絡(luò)狀況不明時(shí)先試探性加速慢啟動(dòng)接近上限就穩(wěn)著來擁塞避免一旦發(fā)現(xiàn)丟包就大幅收斂快重傳快恢復(fù)之后再慢慢回到之前的水平。2.4 抓包實(shí)戰(zhàn)怎么一眼看出窗口在縮小我在排查線上連接問題的時(shí)候最常干的一件事就是抓包看窗口。如果發(fā)現(xiàn)客戶端到服務(wù)器的數(shù)據(jù)吞吐突然掉到零先看最后一個(gè)ACK里通告的rwnd是不是0如果是問題基本出在接收方應(yīng)用層沒及時(shí)讀數(shù)據(jù)導(dǎo)致接收緩沖被打滿這個(gè)時(shí)候該去查接收方的業(yè)務(wù)代碼而不是在網(wǎng)絡(luò)鏈路上找原因。如果rwnd一直很大但吞吐還是上不去那就要看是不是發(fā)送方的cwnd受限或者丟包導(dǎo)致的快恢復(fù)頻繁觸發(fā)。一個(gè)實(shí)用的觀察技巧抓包軟件里會(huì)對(duì)TCP流自動(dòng)計(jì)算“窗口已用空間”也就是接收緩沖區(qū)被占用的字節(jié)數(shù)。你盯著這個(gè)值看如果它一直往上漲說明接收方消費(fèi)速度跟不上如果它始終在低位徘徊說明鏈路或者發(fā)送方的擁塞控制才是瓶頸。這個(gè)判斷比單純看“帶寬有多大”要實(shí)在得多。3. 算法面試?yán)锏幕瑒?dòng)窗口最大值、最小值、連續(xù)子數(shù)組的暴力破解優(yōu)化從網(wǎng)絡(luò)切回算法題。刷LeetCode的人對(duì)滑動(dòng)窗口應(yīng)該最熟了因?yàn)橛幸淮箢愵}暴力解法寫著簡(jiǎn)單但數(shù)據(jù)規(guī)模一大就超時(shí)拉出滑動(dòng)窗口就完美干掉冗余計(jì)算。這里我不打算只貼題解而是講清楚幾個(gè)關(guān)鍵模板背后的推導(dǎo)邏輯。3.1 標(biāo)準(zhǔn)雙指針框架“右擴(kuò)左縮”的通用寫法滑動(dòng)窗口在算法題里的最常見形態(tài)是配合雙指針維護(hù)一個(gè)區(qū)間。右指針負(fù)責(zé)往窗口里加元素左指針負(fù)責(zé)在窗口不滿足條件時(shí)收縮。通用框架長(zhǎng)這樣left 0 cur 0 # 當(dāng)前窗口的某種累計(jì)狀態(tài) ans float(inf) for right in range(n): # 1. 將 nums[right] 加入窗口更新 cur cur nums[right] # 2. while 循環(huán)收縮左邊界 while cur target: ans min(ans, right - left 1) # 更新答案 cur - nums[left] # 移除 nums[left] left 1關(guān)鍵點(diǎn)在于while循環(huán)的執(zhí)行時(shí)機(jī)每次右指針前進(jìn)都要把窗口調(diào)整到合法狀態(tài)然后記錄答案。這個(gè)框架能解的問題包括“長(zhǎng)度最小的子數(shù)組”“無重復(fù)字符的最長(zhǎng)子串”“字符串的排列匹配”等等。本質(zhì)上是利用窗口的連續(xù)性把原本需要O(n2)枚舉的子區(qū)間壓縮成O(n)的左右指針移動(dòng)。3.2 求滑動(dòng)窗口最大值/最小值雙端隊(duì)列才是主角如果只是求窗口內(nèi)元素的某個(gè)簡(jiǎn)單統(tǒng)計(jì)量和、長(zhǎng)度雙指針框架就夠了。但要求窗口內(nèi)的最大值或最小值尤其是每個(gè)窗口位置都要輸出一個(gè)最值的時(shí)候難點(diǎn)就變了窗口滑動(dòng)時(shí)你要同時(shí)處理加入新元素、移除舊元素、求當(dāng)前窗口最值這三個(gè)操作。最直接的做法是維護(hù)一個(gè)大根堆但堆只能高效地支持“加入元素”和“獲取最大值”當(dāng)窗口左邊界的元素要彈出時(shí)堆不知道該刪哪個(gè)除非用懶刪除技巧要么就時(shí)間復(fù)雜度退化。面試?yán)锔鼧?biāo)準(zhǔn)的解法是維護(hù)一個(gè)單調(diào)雙端隊(duì)列隊(duì)列里的元素下標(biāo)對(duì)應(yīng)的值從隊(duì)首到隊(duì)尾嚴(yán)格遞減求最大值時(shí)。每次新增一個(gè)元素時(shí)把隊(duì)尾所有比它小的元素全部彈出因?yàn)樗饶切┡f元素更晚被淘汰窗口內(nèi)它在的時(shí)刻更久值又更大舊元素在它面前毫無存在感。然后檢查隊(duì)首元素是否已經(jīng)滑出窗口左邊界滑出就彈出。最后隊(duì)首元素就是當(dāng)前窗口的最大值。from collections import deque def maxSlidingWindow(nums, k): q deque() res [] for i, v in enumerate(nums): # 維護(hù) q 內(nèi)元素按 nums 值單調(diào)遞減 while q and nums[q[-1]] v: q.pop() q.append(i) # 移除滑出窗口的下標(biāo) if q[0] i - k: q.popleft() # 窗口滿 k 個(gè)元素后開始記錄結(jié)果 if i k - 1: res.append(nums[q[0]]) return res這段代碼表面看只是壓入和彈出核心邏輯就一句話舊元素如果值又小又早過期就永遠(yuǎn)不可能成為窗口最大值直接丟掉。這就是單調(diào)隊(duì)列的優(yōu)化本質(zhì)它把不可能當(dāng)答案的候選提前剪枝了而不是等它到隊(duì)首再慢慢淘汰。求最小值同理把隊(duì)列改成從隊(duì)首到隊(duì)尾單調(diào)遞增即可。3.3 暴力優(yōu)化與復(fù)雜度分析為什么窗口能省一個(gè)量級(jí)拿“長(zhǎng)度為k的子數(shù)組的最大值”舉例。暴力解法是每個(gè)窗口重新遍歷一遍k個(gè)元素復(fù)雜度O(nk)n是數(shù)組長(zhǎng)度用單調(diào)隊(duì)列每個(gè)元素最多入隊(duì)一次、出隊(duì)一次整體O(n)空間O(k)。從O(nk)到O(n)數(shù)據(jù)量1萬時(shí)暴力要跑上億次基礎(chǔ)操作隊(duì)列解法只要幾萬次這個(gè)差距在真實(shí)業(yè)務(wù)里就是“跑幾分鐘”和“毫秒級(jí)返回”的差距。另一個(gè)容易忽略的復(fù)雜度細(xì)節(jié)是“窗口在數(shù)據(jù)流上的持久化”。比如處理傳感器實(shí)時(shí)數(shù)據(jù)數(shù)組是無窮的暴力遍歷緩存的方式根本不可行滑動(dòng)窗口配合增量更新比如維護(hù)窗口內(nèi)的和滑動(dòng)時(shí)加新減舊才能做到每個(gè)新數(shù)據(jù)到來自動(dòng)計(jì)算一次結(jié)果O(1)更新。這就是為什么滑動(dòng)窗口算法在流式計(jì)算、實(shí)時(shí)監(jiān)控里被大量使用——不只是面試題它在工程上就是剛需。4. 滑動(dòng)窗口濾波工程里治噪聲的那排移位寄存器接著聊另一個(gè)工程陣地——信號(hào)處理。嵌入式設(shè)備采樣回來的數(shù)據(jù)噪聲是常態(tài)。ADC讀回來的原始值跳來跳去直接拿去做控制控制量也會(huì)跟著抖?；瑒?dòng)窗口濾波也叫移動(dòng)平均濾波是最簡(jiǎn)單也最常用的一招。4.1 滑動(dòng)窗口濾波器的本質(zhì)N點(diǎn)平均值它的數(shù)學(xué)表達(dá)式非常樸素y[n] (x[n] x[n-1] ... x[n-N1]) / N也就是輸出等于當(dāng)前時(shí)刻往前N個(gè)輸入點(diǎn)的算術(shù)平均。窗口每滑動(dòng)一次納入一個(gè)新的采樣點(diǎn)丟掉最舊的一個(gè)采樣點(diǎn)。跟算法題里的“窗口內(nèi)求和”一模一樣工程實(shí)現(xiàn)時(shí)為了效率還能用增量更新sum[n] sum[n-1] x[n] - x[n-N]然后y[n] sum[n] / N。這樣每次更新只做一次加法和一次減法不涉及循環(huán)累加計(jì)算量恒定。但N的選擇是個(gè)兩難。窗口越大平滑效果越好噪聲抑制越狠但窗口越大滯后也越明顯。這里就引出一個(gè)常被說起的問題滑動(dòng)窗口濾波器的延遲。4.2 延時(shí)問題為什么輸出總是慢半拍滑動(dòng)窗口均值濾波本質(zhì)上是一個(gè)N階FIR濾波器它的相位響應(yīng)是線性的群延遲恒定為(N-1)/2個(gè)采樣周期。也就是說輸出波形整體會(huì)比輸入波形滯后(N-1)/2拍。比如采樣率1kHz窗口取32點(diǎn)輸出就會(huì)滯后15.5毫秒。對(duì)于要求實(shí)時(shí)性的控制系統(tǒng)比如無人機(jī)的姿態(tài)環(huán)、電機(jī)轉(zhuǎn)速環(huán)這個(gè)延遲可能直接導(dǎo)致系統(tǒng)不穩(wěn)定。面試或者方案評(píng)審時(shí)問“為什么用了滑動(dòng)窗口濾波之后曲線變遲鈍了”答案就在這個(gè)群延遲公式里。工程師可以做的不是消滅延遲FIR線性相位濾波器的延遲是固有屬性而是去平衡。如果既要平滑又要低延遲可以考慮用更短窗口配合更高級(jí)的濾波算法如加權(quán)移動(dòng)平均、一階低通濾波或者對(duì)輸出做相位補(bǔ)償預(yù)測(cè)。從工程經(jīng)驗(yàn)看純滑動(dòng)窗口平均適合用在“后處理/監(jiān)控/報(bào)表”這種對(duì)實(shí)時(shí)性要求不高的場(chǎng)景不適合用在“閉環(huán)控制反饋鏈”的核心路徑上。4.3 整型環(huán)境下如何避免浮點(diǎn)運(yùn)算MCU上如果不想引入浮點(diǎn)運(yùn)算單元滑動(dòng)窗口平均全用整數(shù)實(shí)現(xiàn)很順手。一個(gè)常見技巧是把窗口大小選成2的冪比如8、16、32這樣除法就能用右移代替。sum sum x - x_old; y sum 5; 一次除法都不要。代價(jià)是窗口大小只能取2的冪不是每個(gè)場(chǎng)景都能接受但絕大多數(shù)溫度采樣、電流采樣場(chǎng)景窗口長(zhǎng)度取16還是32差別不大用移位換性能很劃算。另一個(gè)坑是累加和溢出。32位單片機(jī)ADC采樣值可能是16位的65535窗口取64sum最大值約420萬還好但如果窗口取255sum就可能超過20位在某些32位DSP上仍沒問題一旦換到16位MCU就危險(xiǎn)了。一個(gè)務(wù)實(shí)的做法是采樣值先歸一化或者限幅或者在每次累加后定期整體衰減防止底噪累積造成偏移。4.4 滑動(dòng)窗口濾波的Verilog實(shí)現(xiàn)思路寫Verilog的兄弟看了上面的整數(shù)實(shí)現(xiàn)應(yīng)該立刻能想到移位寄存器。確實(shí)滑動(dòng)窗口均值濾波在FPGA上就是一個(gè)N拍移位寄存器加一個(gè)累加器。module sliding_window_avg #( parameter N 8, // 窗口大小建議2的冪 parameter DATA_W 16 )( input logic clk, input logic rst_n, input logic valid_in, input logic [DATA_W-1:0] data_in, output logic [DATA_W3:0] avg_out, output logic valid_out ); logic [DATA_W-1:0] shift_reg [N]; logic [DATA_W3:0] sum; always_ff (posedge clk or negedge rst_n) begin if (!rst_n) begin foreach (shift_reg[i]) shift_reg[i] 0; sum 0; end else if (valid_in) begin // 增量更新加上新數(shù)據(jù)減去最舊數(shù)據(jù) sum sum data_in - shift_reg[N-1]; // 移位寄存器整體后移 for (int i N-1; i 0; i--) shift_reg[i] shift_reg[i-1]; shift_reg[0] data_in; end end assign avg_out sum $clog2(N); endmodule幾個(gè)容易踩的細(xì)節(jié)。第一數(shù)據(jù)的位寬必須預(yù)留累加和的空間否則溢出悄無聲息輸出直接橫跳第二窗口長(zhǎng)度N必須參數(shù)化但求和右移位數(shù)要跟N嚴(yán)格對(duì)應(yīng)N是2的冪時(shí)直接右移log2(N)否則就要用除法器資源成倍增加第三上電初始化時(shí)shift_reg和sum必須清零否則前N個(gè)周期的輸出是垃圾數(shù)據(jù)第四valid_in時(shí)序上必須穩(wěn)定如果數(shù)據(jù)源有斷續(xù)要處理好“窗口內(nèi)只有部分有效數(shù)據(jù)”的情況否則會(huì)把噪聲也平均進(jìn)去。5. 滑動(dòng)窗口的邊界問題窗口大小、步長(zhǎng)、重疊這些坑一次說清前面幾個(gè)章節(jié)把四個(gè)領(lǐng)域的滑動(dòng)窗口都過了一遍。這最后一章我想挑出幾個(gè)跨領(lǐng)域都會(huì)遇到的邊界問題整理成一種“通用注意事項(xiàng)”來看因?yàn)檫@些問題在哪個(gè)領(lǐng)域都出現(xiàn)過而且如果第一次遇到特別容易被卡住。5.1 窗口大小和步長(zhǎng)不能默認(rèn)所有情況都“每來一個(gè)數(shù)據(jù)挪一格”很多滑動(dòng)窗口的默認(rèn)假設(shè)是“步長(zhǎng)為1”也就是每產(chǎn)生一個(gè)新數(shù)據(jù)窗口整體向前移動(dòng)1個(gè)單元。但在很多實(shí)際業(yè)務(wù)里步長(zhǎng)不一定是1。比如做音頻頻譜分析每幀數(shù)據(jù)1024個(gè)采樣點(diǎn)幀移512個(gè)點(diǎn)相鄰幀之間有一半的重疊做目標(biāo)檢測(cè)的滑窗掃描窗口大小是固定像素步長(zhǎng)可能是8像素或16像素。步長(zhǎng)一旦變大輸出頻率下降但計(jì)算量也下降步長(zhǎng)變小相鄰窗口重疊多輸出更平滑但算力開銷更大。步長(zhǎng)設(shè)計(jì)上沒有標(biāo)準(zhǔn)答案只有一個(gè)原則步長(zhǎng)不能超過窗口大小否則數(shù)據(jù)流的某些區(qū)域會(huì)被漏掉。比如在圖像滑窗檢測(cè)里步長(zhǎng)超過目標(biāo)尺寸的一半目標(biāo)就可能剛好落在兩個(gè)窗口的縫隙里檢測(cè)不到。窗口重疊率一般取50%到75%之間具體看你對(duì)漏檢和算力之間的偏好。5.2 窗口初始化階段前N-1個(gè)點(diǎn)為什么是臟數(shù)據(jù)只要窗口沒存滿滑動(dòng)窗口的輸出就處于“亞健康”狀態(tài)。TCP的慢啟動(dòng)之所以初始窗口很小就是因?yàn)檫B接剛建立沒有足夠的信息來判斷網(wǎng)絡(luò)狀態(tài)濾波器的前N-1個(gè)輸出之所以不準(zhǔn)是因?yàn)榇翱诶镉行?shù)據(jù)不足移位寄存器里還存著上電時(shí)的隨機(jī)值或零值算法題里如果上來就返回窗口最大值而窗口還沒攢夠k個(gè)元素結(jié)果就是錯(cuò)的。工程上的常見做法要么在輸出前等待窗口填滿要么用“數(shù)據(jù)不足N個(gè)時(shí)先求已有數(shù)據(jù)的平均”這種修正。對(duì)于嵌入式濾波通常上電后先不輸出濾波結(jié)果等窗口填滿后再開放輸出并且把使能信號(hào)跟valid信號(hào)對(duì)齊防止控制邏輯拿到垃圾數(shù)據(jù)。5.3 資源與實(shí)時(shí)性的終極權(quán)衡把四個(gè)場(chǎng)景放在一起對(duì)比會(huì)發(fā)現(xiàn)在“窗口”這個(gè)問題上所有領(lǐng)域的根本矛盾都一樣窗口大了統(tǒng)計(jì)上更可靠但動(dòng)態(tài)響應(yīng)變差窗口小了反應(yīng)快但又不夠平滑。TCP的擁塞控制窗口太大網(wǎng)絡(luò)緩存被塞滿時(shí)延爆炸窗口太小帶寬利用不上去。濾波窗口太大控制信號(hào)滯后引起振蕩太小噪聲濾不干凈。算法題里的窗口如果太小符合條件的子串找不到太大窗口合法條件容易被破壞。所以滑動(dòng)窗口不是“調(diào)得越大越好”也不是“越小越靈敏”而是要圍繞你的目標(biāo)函數(shù)做權(quán)衡。你關(guān)心的是吞吐率那就用類似TCP的機(jī)制動(dòng)態(tài)調(diào)整窗口你關(guān)心的是平滑度那就固定窗口但接受延遲你關(guān)心的是響應(yīng)速度那就縮小窗口并提高采樣率。我在項(xiàng)目里常用的一個(gè)方法把窗口大小做成可在線調(diào)整的參數(shù)然后用一組仿真數(shù)據(jù)或者歷史數(shù)據(jù)掃一遍不同窗口下的性能指標(biāo)畫成曲線去選。這種做法本質(zhì)上跟網(wǎng)絡(luò)里TCP的自動(dòng)調(diào)整一樣只是把“擁塞窗口”換成了“濾波窗口”。手動(dòng)調(diào)參不可怕可怕的是不知道自己在調(diào)什么——只要搞清楚窗口變大、變小分別會(huì)犧牲什么、獲得什么你手里的滑動(dòng)窗口就真正變成你的工具了。6. 一點(diǎn)實(shí)操體會(huì)這幾個(gè)領(lǐng)域的滑動(dòng)窗口我都實(shí)際寫過代碼、抓過包、調(diào)過參數(shù)。最大的體會(huì)是它之所以能在那么多地方出現(xiàn)是因?yàn)樗选盁o限的數(shù)據(jù)流”變成了“有限的局部視角”而計(jì)算機(jī)系統(tǒng)里幾乎所有優(yōu)雅的方案都是對(duì)“有限資源”的巧妙利用。如果你正打算掌握它我的建議很直接先把算法題里的單調(diào)隊(duì)列寫熟練這是理解“窗口內(nèi)如何高效維護(hù)信息”的直觀入口然后動(dòng)手實(shí)現(xiàn)一遍Verilog的滑動(dòng)平均濾波器去體會(huì)“數(shù)據(jù)搬運(yùn)”在硬件上的真實(shí)代價(jià)最后去抓一次真實(shí)環(huán)境下的TCP傳輸包看看rwnd和cwnd到底是怎么動(dòng)態(tài)變化的。這三件事做下來你對(duì)滑動(dòng)窗口的理解一定比背十篇八股文都扎實(shí)。