【TIS-100 攻略】第 18 關(guān)：信號窗口篩選器
本文首發(fā)于 B 站《TIS-100》文集（https://www.bilibili.com/read/readlist/rl626023）。原創(chuàng)不易，轉(zhuǎn)載請注明出處。
第 18 關(guān)《信號窗口篩選器》（Signal Window Filter）關(guān)卡展示
本關(guān)的 IN 會不斷提供數(shù)字，你要隨時將【前 3 個數(shù)之和】和【前 5 個數(shù)之和】輸出給 OUT.3 和 OUT.5。如果窗口中的數(shù)字不足?3 個／5 個，視空位為 0，即輸出【前方所有數(shù)之和】。
本關(guān)我們首先想到的，自然是用棧將【前 5 個數(shù)】存起來，然后 OUT.3 上方的節(jié)點(diǎn)只取其中三個數(shù)字相加，而?OUT.5 上方的節(jié)點(diǎn)將這些數(shù)字全部加起來。代碼如下：
本關(guān)使用到了 7 個節(jié)點(diǎn)，單純的方向已經(jīng)不便于描述了，因此我將寫有代碼的節(jié)點(diǎn)都標(biāo)上了編號，后續(xù)我會用【x 號節(jié)點(diǎn)】這樣的描述來指代。
1 號節(jié)點(diǎn)的位置不好，和棧離得老遠(yuǎn)了，所以它把收到的數(shù)字傳給 2 號節(jié)點(diǎn)，由它來干活（mov up right）。接下來看 2 號節(jié)點(diǎn)的邏輯：
由于最遠(yuǎn)需要追溯到前 4 個數(shù)字，所以 2 號節(jié)點(diǎn)在收到第一個數(shù)字前，要往棧里補(bǔ) 4 個 0（mov 0 right）
（mov 0 right）
（mov 0 right）
（mov 0 right）
然后，每從 1 號節(jié)點(diǎn)收到一個數(shù)字，就往下方的 4 號節(jié)點(diǎn)傳（mov left down）。
傳完后，需要折返到第 5 行，準(zhǔn)備好傳下一個數(shù)字（jmp 5）。如果任由程序跳回第 1 行的話，會往棧里寫入多余的 0。
4 號節(jié)點(diǎn)將 2 號節(jié)點(diǎn)發(fā)來的【當(dāng)前數(shù)】傳給右邊的 5 號節(jié)點(diǎn)。5 號節(jié)點(diǎn)的位置非常好，夾在兩個棧中間，它要做的工作就是將棧中的數(shù)字取出來，發(fā)給左邊，取完后再將?；謴?fù)原樣。4 號節(jié)點(diǎn)接下來要等待 5 號節(jié)點(diǎn)將棧中的數(shù)字取出，所以這時候我們先看 5 號節(jié)點(diǎn)的邏輯：
5 號節(jié)點(diǎn)收到【當(dāng)前數(shù)】后，將它存入右下角的棧里暫存（mov left down）。
緊接著從右上角的節(jié)點(diǎn)里取出【前 1~3 個數(shù)】，統(tǒng)統(tǒng)扔到右下角的棧里暫存（mov up down）
（mov up down）
（mov up down）
由于【前 4 個數(shù)】在本次使用后，以后都不需要再次使用，所以取出【前 4 個數(shù)】后，直接扔給左邊的節(jié)點(diǎn)，無需暫存（mov up left）。
對于剩下的【前 3 個數(shù)】、【前 2 個數(shù)】、【前 1 個數(shù)】和【當(dāng)前數(shù)】這四個數(shù)，每個數(shù)都要往左邊發(fā)兩遍，而且它們還要在將來用到，不能像【前 4 個數(shù)】那樣丟棄，而是要放回到棧里。這部分操作較為復(fù)雜，將同樣的邏輯復(fù)寫四遍的話，代碼空間不夠用，因此這里我們寫成循環(huán)的方式。首先將 bak 置為 4（mov 4 acc）
（swp）
接下來，我們從下方的棧里取一個數(shù)字（mov up acc），
將它向左邊發(fā)兩遍（mov acc left）
（mov acc left）后，
扔回右上角的棧里（mov acc up）。
每這樣做一次，就令 bak 減去 1（swp）
（sub 1）并判斷 bak 是否減到了 0。
尚未減到 0 時，說明右下角的棧沒有被取空，跳回第 7 行繼續(xù)?。╦nz 7），直到 bak 減到 0 后，最近的 5 個數(shù)字就全部發(fā)給了左邊。此時跳回第 1 行，等待左邊發(fā)來下一次的數(shù)字。
現(xiàn)在回過頭來看 4 號節(jié)點(diǎn)。
4 號節(jié)點(diǎn)把當(dāng)前數(shù)發(fā)給 5 號節(jié)點(diǎn)后（mov up right），
就開始等待 5 號節(jié)點(diǎn)將最近 5 個數(shù)傳來。其中【前 4 個數(shù)】只會傳一遍，【前 3 個數(shù)～當(dāng)前數(shù)】都會被傳兩遍。4 號節(jié)點(diǎn)需要計(jì)算【前 4 個數(shù) + 前 3 個數(shù) + 前 2 個數(shù) + 前 1 個數(shù) + 當(dāng)前數(shù)】的值，而 2 號節(jié)點(diǎn)只需計(jì)算【前 2 個數(shù) + 前 1 個數(shù) + 當(dāng)前數(shù)】的值。當(dāng) 4 號節(jié)點(diǎn)收到【前 4 個數(shù)】的時候，將 acc 置為該數(shù)（mov right acc）；
對于【前 3 個數(shù)】，5 號節(jié)點(diǎn)由于代碼行數(shù)限制，也會發(fā)兩遍。但是這個數(shù) 3 號節(jié)點(diǎn)是不需要的，所以這兩份副本里，4 號節(jié)點(diǎn)需要丟棄掉其中一個（mov right nil），
并在收到另一個時，將它累加到自己的 acc 里（add right）。
對于剩下的【前 2 個數(shù)～當(dāng)前數(shù)】，5 號節(jié)點(diǎn)也會發(fā)兩遍，3 號節(jié)點(diǎn)和 4 號節(jié)點(diǎn)各需要一份，所以 4 號節(jié)點(diǎn)將其中一份傳給左邊（mov right left），
另一份累加到自己的 acc 里（add right）。
（mov right left）
（add right）
（mov right left）
（add right）
當(dāng) 5 號節(jié)點(diǎn)把所有該傳的數(shù)字都傳來后，本輪的和就計(jì)算完畢了，棧里的【前 3 個數(shù)～當(dāng)前數(shù)】就理所當(dāng)然地變成了【前 4 個數(shù)～前 1 個數(shù)】。此時 4 號節(jié)點(diǎn)把本次算好的【最近 5 個數(shù)的和】發(fā)給 7 號節(jié)點(diǎn)，讓 7 號節(jié)點(diǎn)把這個值送往 OUT.5 的輸出口（mov?acc down）。
以上代碼中我們用到了一個特殊的寄存器 nil：當(dāng)你讀取 nil 寄存器時，讀到的是恒 0（執(zhí)行 mov nil acc 后，acc 會被置為 0）；而如果你把一個值寫入 nil 寄存器，該值會被丟棄。注意 4 號節(jié)點(diǎn)里的 mov right nil 這行代碼，它的作用就是將 5 號節(jié)點(diǎn)第一次發(fā)來的【前 3 個數(shù)】丟棄。4 號節(jié)點(diǎn)的 acc 寄存器已經(jīng)被用來存儲累加和了，如果想要不使用 nil 寄存器把這個值丟棄的話，就只能存入 bak 寄存器。而存入 bak 寄存器則需要 3 行代碼（swp, mov right acc, swp），所以這里不如簡單點(diǎn)，直接丟給 nil 寄存器，讓 nil 寄存器銷毀掉這個值。
3 號節(jié)點(diǎn)的邏輯稍微簡單點(diǎn)，它會從 4 號節(jié)點(diǎn)收到【前 2 個數(shù)】、【前 1 個數(shù)】和【當(dāng)前數(shù)】，直接將它們累加起來發(fā)給下方的 6 號節(jié)點(diǎn)，讓 6 號節(jié)點(diǎn)把這個值送往 OUT.3 的輸出口（mov right acc, add right, add right, mov acc down）。
6 號節(jié)點(diǎn)和 7 號節(jié)點(diǎn)都是從它們的上方接收本次的計(jì)算結(jié)果并輸出（mov up down, mov up down）。
點(diǎn)擊左下角的【RUN】，稍等片刻，便會彈出結(jié)算界面：
利用【滑動窗口】算法優(yōu)化程序
以上方案并不是最優(yōu)的，因?yàn)槲覀冏隽颂嗟闹貜?fù)計(jì)算。以求最近 5 個數(shù)的和為例：
計(jì)算 sum[4] 時，我們讀取了?num[0~4] 的值，并將它們累加了起來，這無可厚非；可是計(jì)算 sum[5] 時，我們?nèi)匀焕侠蠈?shí)實(shí)地讀取了?num[1~5] 的值，并將它們累加了起來。這就導(dǎo)致了兩個問題：①num[1~4] 的這部分和被重復(fù)算了一遍，效率上有損失；②上一項(xiàng) sum[4] 的值沒有被有效利用。這時候，我們不妨換一種思路：
后一項(xiàng)可以由前一項(xiàng)推導(dǎo)而來，只要在前一項(xiàng)的基礎(chǔ)上，加上【當(dāng)前值】，減去【前 5 個數(shù)】，就 OK 了。
最近 3 個數(shù)的和同理，改為在前一項(xiàng)的基礎(chǔ)上加上【當(dāng)前值】并減去【前 3 個數(shù)】即可。這樣的話，我們計(jì)算任何一項(xiàng)結(jié)果，都只要在前一項(xiàng)的基礎(chǔ)上【加一個數(shù)】并【減一個數(shù)】，這樣我們的計(jì)算量就大大減少，效率肉眼可見地提升了。優(yōu)化后的代碼如下：
這次因?yàn)橐玫角?5 個數(shù)，所以棧里要多放一個 0，2 號節(jié)點(diǎn)寫了五句 mov 0 right。當(dāng)然你也可以改成計(jì)數(shù)循環(huán)的寫法，省去 1 行代碼行數(shù)（1: mov 5 acc,?2: mov 0 right, 3: sub 1, 4: jnz 2）。寫完 5 個 0 后，剩余的操作都是在 1、3、4、5 號節(jié)點(diǎn)間進(jìn)行，沒有 2 號節(jié)點(diǎn)什么事了。2 號節(jié)點(diǎn)此時一條 jro 0，永久停在當(dāng)前位置掛機(jī)。
1 號節(jié)點(diǎn)收到【當(dāng)前數(shù)】后，向 3 號節(jié)點(diǎn)發(fā)送 3 遍（mov up acc, mov acc down * 3）。這 3 次分別用在這 3 個地方：①作為【最近 3 個數(shù)之和】的累加項(xiàng)；②作為【最近 5 個數(shù)之和】的累加項(xiàng)；③存入棧里，作為將來要用到的【前 3 個數(shù)】及【前 5 個數(shù)】。
3 號節(jié)點(diǎn)在收到三個【當(dāng)前數(shù)】時，按照“先傳話，后干事”的原則，將前兩次收到的數(shù)發(fā)給右邊，然后第三次收到的數(shù)再累加到自己的 acc 里（mov up right, mov up right, add up）。
4 號節(jié)點(diǎn)會從 3 號節(jié)點(diǎn)收到兩個【當(dāng)前數(shù)】。同樣按照“先傳話，后干事”的原則，把第一次收到的數(shù)發(fā)給 5 號節(jié)點(diǎn)，把第二份收到的數(shù)累加到自己的 acc 里（mov left right, add left）。
接下來是 5 號節(jié)點(diǎn)：
5 號節(jié)點(diǎn)會從 4 號節(jié)點(diǎn)收到【當(dāng)前數(shù)】，將它放入右下角的棧里暫存（mov left down）。
接著從右上角的棧里取出【前 1 個數(shù)】和【前 2 個數(shù)】暫存到右下角（mov up down）
（mov up down）
取到【前 3 個數(shù)】時，將它復(fù)制一份（mov up acc）
發(fā)給左邊（mov acc left），
再存到右下角的棧里（mov acc down）。
取到【前 4 個數(shù)】時，直接扔下去（mov up down）。
取到【前 5 個數(shù)】時，拿出來直接扔給左邊，這個值以后就沒用了，可以直接廢棄掉了（mov up left）。
至此，右下角的棧里存著【前 4 個數(shù)～當(dāng)前數(shù)】這 5 個數(shù)字，將它們倒回右上角的棧（mov down up * 5）。同樣地，這 5 條同樣的語句也能改寫成循環(huán)的方式，以節(jié)省一行代碼（9: mov 5 acc, a: mov down up, b: sub 1, c: jnz a）。
4 號節(jié)點(diǎn)首先收到的是【前 3 個數(shù)】，這個數(shù)是 3 號節(jié)點(diǎn)要減去的，我們將這個數(shù)傳給 3 號節(jié)點(diǎn)（mov right left）；然后 4 號節(jié)點(diǎn)會收到【前 5 個數(shù)】，4 號節(jié)點(diǎn)減去這個數(shù)（sub right）。
3 號節(jié)點(diǎn)在收到 4 號節(jié)點(diǎn)發(fā)來的【前 3 個數(shù)】時，令 acc 減去這個數(shù)（sub right）。至此，3 號節(jié)點(diǎn)和 4 號節(jié)點(diǎn)都通過【滑動窗口】的方式計(jì)算好了最近 3 個數(shù)和最近 5 個數(shù)之和，他倆把算好的值分別發(fā)給下方的 6 號和 7 號節(jié)點(diǎn)（mov acc down, mov acc down）。
6 號節(jié)點(diǎn)和 7 號節(jié)點(diǎn)都是從它們的上方接收本次的計(jì)算結(jié)果并輸出（mov up down, mov up down）。
點(diǎn)擊左下角的【RUN】，稍等片刻，便會彈出結(jié)算界面：
運(yùn)行時長由原先的 2153 周期驟降到 973 周期，代碼行數(shù)也由 38 行減少到了 35 行，針不戳。如果你按照我的指示把兩段重復(fù)的代碼都改寫成了循環(huán)的形式，代碼行數(shù)甚至能減少到 33 行。
