概念地圖・FFT 蝶形圖
作者 山姆（謝冠生）・喵喵書評創辦人
發布
分類：系統
這一頁不只是把一個概念解釋一遍——一張自己畫的結構圖，加上拿台灣情境從頭走一次的實例演練、這個框架什麼時候會騙你，以及它接回 P.A.I.N. 之後長什麼樣。一頁必須交付的三層 →
FFT 蝶形圖：把重複算的那一段只算一次
一台主機的流量圖看起來像雜訊——上上下下，找不到形狀。可是把同一段資料換一種看法之後，裡面浮出三個固定的節拍：每天一次、每小時一次，還有一個每四十分鐘一次的。把時間軸上的起伏換算成頻率，那件事叫傅立葉轉換；讓它在你手邊那台機器上跑得完的，是這張蝶形圖。它長得像一張織好的網：8 個輸入從左邊進去，走三層，8 個頻率從右邊出來——中間那 12 個交叉，就是全部的工作量。
一個蝶形單元，做的是哪兩件事
整張網只有一種零件，它重複了 12 次。把最上面那一個拆開看，做的事短得一句話講得完：下面那支先乘一個數，然後跟上面那支加一次、減一次。
| 蝶形的一步 | 圖上怎麼畫 | 這一步在做什麼 |
|---|---|---|
| 下支先乘 W | 下面那條線進來之後，先過一個小方塊 | W 是旋轉因子，一個複數的乘數，每一層各不相同 |
| 上下相加 | 兩支併進上面那個節點 | 上輸出 ＝ 上支 ＋ W×下支 |
| 上下相減 | 兩支併進下面那個節點 | 下輸出 ＝ 上支 − W×下支，跟上一列共用同一次乘法，沒有多花錢 |
| 中間結果 | 兩層之間那一排小點 | 每一個點都被下一層的兩個蝶形讀走，而它只被算過一遍 |
| 輸入的排法 | 0、4、2、6、1、5、3、7 | 位元反轉排在輸入端，W 才掛在進來的下支上。兩件事要同進同出 |
表裡最容易滑過去的是最後一列。同一張網，只要把旋轉因子從「進來的下支」搬到「出去的減法那一支」，輸入的排法就得整個換回自然序、輸出反而變成位元反轉——那是另一種畫法，混在同一張圖上，跑出來的每一個頻率都會歪掉。這也是網路上抄來的蝶形圖最常壞的地方。
什麼樣的資料拆得動，三個條件
這張網不挑產業，它挑資料的形狀。三個條件，缺一個就白算。
一、取樣的間隔要一樣寬。網站代管商的流量是每 5 分鐘記一筆。監控代理重啟那幾分鐘漏掉四筆，如果你把前後直接接起來當成連續的，蝶形網不會抗議——它會把那個缺口讀成一段真實的波動，回你一堆不存在的頻率。缺口要嘛用前後兩筆補平，要嘛整段丟掉重取。自問：我這份資料，相鄰兩筆之間的距離，每一次都一樣嗎？
二、你要找的那個節拍，長度要超過兩個取樣間隔。5 分鐘取樣一次，40 分鐘的備份排程佔 8 個點，在圖上是一根乾淨的柱子。8 分鐘的那種心跳只佔 1.6 個點，它不會消失——它會偽裝成另一個頻率，看起來合理，位置卻是假的。要抓更短的節拍，只有一條路：把取樣間隔縮短。自問：我想抓的那個週期，撐得過兩個取樣間隔嗎？
三、你的窗要蓋得過那個週期好幾輪。1024 個點乘上 5 分鐘，是約 85 小時、約 3.6 天。每天一次的節拍在這段窗裡跑了三輪半，勉強站得住；每小時一次跑了八十幾輪，穩得像釘上去的。而每週一次的東西，在 3.6 天的窗裡連一輪都沒走完，圖上根本沒有它的格子，談不上強弱。自問：這段窗，夠那個週期走完幾輪？
一家網站代管商的流量訊號，一張蝶形網走一遍
底下這家台灣中部的網站代管商，是為了把這個結構講清楚而編出來的示意情境，沒有指涉任何真實公司。他們管著兩百多個客戶站，值班的人每天看同一張流量圖，看了三年，一直覺得那條線只是在抖。
- 取樣：每 5 分鐘記一次全站請求數，連續取 1024 個點——約 85 小時，約 3.6 天。長度剛好是 2 的次方，不必補零
- 先算一次帳：照定義直接算，1024 的平方 ＝ 1048576 次複數乘法。值班的人等不到答案
- 換成蝶形網：以 2 為底的 1024 的對數 ＝ 10 層，每層 512 個蝶形，512 × 10 ＝ 5120 次。1048576 對 5120
- 亮起來的第一根：每天一次——288 個取樣點。上班時段的高峰。跟直覺對得上
- 第二根：每小時一次——12 個點。整點觸發的排程任務。運維表上查得到
- 第三根：每四十分鐘一次——8 個點。翻排程表才發現是全站備份在掃磁碟。它三年來每天出現三十六次
- 沒出現的那一根：每週一次的結帳尖峰。窗只有 3.6 天，它連一輪都沒走完
值得記住的接縫在第三根。前兩根是他們早就知道的事，蝶形網只是幫忙確認；第三根不一樣——那個每四十分鐘一次的凸起，三年來每天出現三十六次，沒有任何人把它跟備份排程連在一起。它不夠大，不會觸發告警；它很規律，所以在時間軸上被眼睛當成背景。真正讓它現形的，是把 1048576 次乘法壓到 5120 次之後，值班的人終於願意每天跑一次這張圖——省下來的算力最後買到的東西，是一個「每天都跑得起」的習慣。至於那個結帳尖峰，得先把窗拉長到兩三週，才輪得到它出現。以上為說明結構用的示意情境，僅供理解框架之用。
這張蝶形網什麼時候會騙你
- 它指得出節拍，指不出原因。蝶形網把 40 分鐘那一格點亮，接下來是人去翻排程表、去問誰在那個時間動了磁碟。把「圖上有一根柱子」直接讀成「找到病灶了」，是這個工具最常見的誤用——它交出來的是一份嫌疑名單，後面那段查證跑不掉。愈是規律的訊號愈容易誤認，因為公司裡規律的東西太多了：排程、班表、電子報寄送時間，全都長得像同一根柱子。
- 窗長決定你看得見哪些週期。3.6 天的窗，能穩穩看到小時級與天級的節拍；每週一次、每月一次的東西在這張圖上不存在。麻煩的是它不存在得很安靜——圖上不會留一個空位提醒你少了什麼，只會給你一排看起來很完整的柱子。要看週級的節拍，窗至少得拉到兩三週，而窗一拉長，短週期又會被中間那些一次性的變動洗掉。窗長要當成取捨來調，隨手填一個數字就會漏掉東西。
- 位元反轉這一步，是抄程式碼最常出錯的地方。這張圖的輸入照 0、4、2、6、1、5、3、7 排，輸出照 0 到 7 排，旋轉因子乘在進來的下支上。另一種畫法把旋轉因子搬到輸出的減法那一支，輸入就換成自然序、輸出才反轉。兩種都對，混在一起就全歪——而且歪出來的東西長得很像頻譜，不會當場爆掉。驗收方法很土：拿一段已知頻率的正弦波餵進去，看那根柱子有沒有站在該站的位置。
用痛點的眼光數那些重複
蝶形圖上畫出來的是路線。
真正省下來的，藏在那些被兩邊共用、只算了一次的中間結果裡——每一層之間那一排小點，下一層的兩個蝶形都會來讀它，而它只被算過一遍。把這件事搬回公司裡，形狀是一樣的：哪一份報表的中間步驟，被三個部門各自重跑了一次？P.A.I.N. 的第一個字母問的是誰在痛，這裡也有人在痛，只是那個痛長在等待裡——等一份跑四十分鐘的報表跑完，等一個每次都要重來的匯出。這張圖畫得出哪一段被重算了幾次，畫不出重算的那幾分鐘裡有誰在等。1048576 壓到 5120 是漂亮的算術，可是那家代管商真正拿到手的，是值班的人願意每天按一次那個按鈕。今晚可以做的一件小事：打開你手邊跑最久的那份流程，把每一步的輸入寫在旁邊，看看哪兩步的輸入其實一模一樣。
關於 FFT，常被問到的幾件事
FFT 跟 DFT 是同一件事嗎？
DFT 是那個要算的東西，FFT 是把它算快的一種做法。同一份資料餵進去，兩者的答案完全一樣，差別只在乘法次數：8 個點的時候是 64 對 12，1024 個點的時候是 1048576 對 5120。點數愈多，差距拉得愈開——這也是為什麼幾乎沒有人真的照定義去算 DFT。你在函式庫裡呼叫的那個 fft，回的就是 DFT 的答案。
為什麼輸入要排成 0、4、2、6、1、5、3、7？
那叫位元反轉。把 0 到 7 寫成三位元的二進位，再把位元前後顛倒讀一次：1 是 001，倒過來是 100，也就是 4；3 是 011，倒過來是 110，也就是 6。整組排完就是 0、4、2、6、1、5、3、7。這樣排的好處是，第一層要配對的兩支剛好上下相鄰，第二層隔兩格，第三層隔四格——連線畫得出來，程式也只要一個位移就找得到對象。重排的成本只付一次，付在資料進場那一刻。
旋轉因子 W 到底是什麼？
它是一個複數的乘數，作用是把下面那一支的相位轉一個角度，讓兩支資料在時間上對齊，之後的加減才有意義。每一層的 W 不同，同一層裡不同位置的蝶形用到的也不同——第一層最單純，愈往後轉的角度愈細。寫程式的時候通常先把一整張 W 表算好放著，跑的時候查表就好。要看懂這張圖，把它當成「一個會轉方向的乘數」就夠用了。
資料筆數不是 2 的次方怎麼辦？
兩條路。一是補零補到最近的 2 的次方，代價是頻率解析度被稀釋，圖上會多出一些不存在的小波紋。二是用混合基底的版本，現成的函式庫大多支援任意長度，只是速度比純 2 的次方版本慢一截。實務上最省事的做法是把取樣長度直接設計成 2 的次方：那家代管商取 1024 個點，就是先看好了 1024 是 2 的十次方。
我需要自己寫一張蝶形網嗎？
不需要。NumPy、試算表的分析工具箱、幾乎每一種語言都有現成的實作，而且比手寫的快、也比手寫的穩。讀懂這張圖的價值在別的地方——知道它為什麼快，你才會在取樣的時候就把間隔排整齊、把窗拉夠長。不然函式庫再快，餵進去的還是一份拆不動的資料。
隨便挑一份每次都要重算一遍的流程，圈出被重算的那一段。那一段如果每一輪的輸入都一樣，它就是你的中間結果——留著它，下一輪直接接手。想知道這種省法會在哪裡撞到天花板，可以接著看阿姆達爾定律，那張圖問的是加人加到第幾個開始沒用，這張圖問的是要算的量本身還能砍掉多少。
喜歡這篇文章嗎？
每週幫你拆二本好書，把判斷力、好書金句、好問題，直送你的信箱。
不適合你可隨時退訂 · 每週兩封，陪你把書讀進生活。
送出即表示同意我們依隱私權政策使用你的 email。