跟我寫jpeg解碼器（附錄二）優化技巧.md

優化技巧

如果用配套程式碼來解碼 1920 * 1080 的圖片，大約會需要將近一秒（我用的 CPU 是 AMD Ryzen 2700X），但是使用一般的開圖軟體（例如 eog, eye of gnome），幾乎是瞬間解開，這代表目前的解碼器還有很多的優化空間。

經過簡單的性能分析之後，大約可以發現效能瓶頸的前兩名是

• 反離散餘弦變換
• 霍夫曼解碼

其中反離散餘弦變換的計算量是霍夫曼解碼的好幾倍，建議優先優化。

題外話：IO

解碼器使用到的系統呼叫就只有讀檔寫檔，只會佔總體運行時間的幾 % 而已，如果用 time 指令觀察到的系統時間佔比不太尋常，那應該先嘗試優化 IO ，或許加上一些緩衝區，避免一直系統呼叫，就會有很好的提升。

反離散餘弦變換優化

先將反離散餘弦變換的公式再列出一次，以方便讀者查閱：

$ result[i][j] = \frac{1}{4}\sum{{x=0} ^7}\sum{{y=0} ^7}C_x C_y cos(\frac{(2i + 1)x\pi}{16}) cos (\frac{(2j + 1)y\pi}{16}) block[x][y] ​$

其中的 $C_i​$ 定義如下

$C_0 = \frac{1}{\sqrt{2}}​$

$C_i = 1, \forall i > 0 ​$

來計算以下直接照定義展開展開的時間複雜度，我們有 $O(n^2)$ 的 result 要計算，每個 result 又要兩層迴圈才算得出來，總時間複雜度爲 $O(n^4)$ 。

快取 cos

觀察式中的 $cos(\frac{(2i + 1)x\pi}{16})$, $cos (\frac{(2j + 1)y\pi}{16})$ ，$i, j, x, y$ 的值都是 0 到 7 之間的整數，也就是說 $cos$ 函數要運算的組合只有 64 種而已，將這些原本要重複計算的值快取到一個陣列裡，就能很容易地提升速度。

二階變換 -> 兩次一階變換

反離散餘弦變換的公式在兩層 $\sum{\sum}​$ 內有一堆函數，我們可以根據參數來對它們分門別類，例如 $C_x​$, $cos(\frac{(2i+1)x \pi}{16})​$ ，只跟 $i​$, $x​$ 有關；而 $C_y​$, $cos(\frac{(2j+1)y \pi}{16})​$ ，只跟 $j​$, $y​$ 有關，於是，可以進行以下代換：

$r_1(i, x) = C_x cos(\frac{(2i+1)x \pi}{16})$

$r_2(j, y) = C_y cos(\frac{(2j+1)y \pi}{16})​$

而其實 $r_1​$, 跟 $r_2​$ 做爲函數，是完全等價的，因此我們設 $r = r_1 = r_2​$。

原式就可以寫爲：

$ result[i][j] = \frac{1}{4}\sum{{x=0} ^7}\sum{{y=0} ^7} r(i,x) r(j,y) block[x][y] = \frac{1}{4}\sum{{x=0} ^7} r(i,x) \sum{{y=0} ^7}r(j,y) block[x][y] ​$

注意到等式最右側的第二個 $\sum​$ ，也就是中的$\sum{_{y=0} ^7}r(j,y) block[x][y]​$，它只是 $x​$ 跟 $j​$ 的函數（y 被遍歷，因此不是參數），也就是說我們可以再用一個 $s(x, j)​$ 來把它取代，進一步把原式寫爲：

$result[i][j] = \sum{_{x=0} ^7} r(x, i)s(x, j)$

計算一個 s(x, j) 的複雜度爲 $O(n)$ ，計算全部的 s(x, j) 複雜度爲 $O(n^3)$ ，result 同理也是 $O(n^3)$ 。這兩個運算其實是一樣的，都是在做一階反離散餘弦變換。

藉由兩步驟一維變換來得到二維變換，我們將複雜度由$O(n^4)$降至$O(n^3)$。

在 JPEG 解碼過程中，$n = 8$，但一維的要做兩次，故大略可提昇$8 / 2 = 4$倍效能。

轉換爲矩陣乘法

有另一個更清晰的方式來理解上述的變換，觀察

$\sum{{x=0} ^7}\sum{{y=0} ^7} r(i,x) r(j,y) block[x][y]​$

欸？是不是有點像矩陣乘法？若令矩陣 $X$ 表示 block ，矩陣 $R$ 表示函數 $r$ 在參數爲 0 到 7 之間的取值，那我們可以將上式寫成 $R^TXR$ 。（請與矩陣乘法的 $\sum$ 式子做比較，就能夠很容易得到）

其中包含了兩次矩陣乘法，分別對應前述的兩次一維的反離散餘弦變換（記得照定義展開的矩陣乘法時間複雜度也是$O(n^3)$），但將它表示成矩陣乘法之後，就能夠利用計算矩陣乘法的算法，進一步降低時間複雜度。

利用快速傅里葉變換

TODO

範式霍夫曼表優化

配套程式碼裡，儲存霍夫曼表的資料結構爲求實作簡單，直接使用了 rust 標準庫裡的 HashMap 。雖然查詢的複雜度是 O(1) ，但常數項一定相當大，畢竟要執行過一個 hash 函數。

一個很自然的優化方式是把它寫成二元樹，但是利用範式霍夫曼表的特性，我們能寫出一種更簡單，效能也許也更好的實作。

回顧一下範式霍夫曼表中碼字的公式：

• 若高度相等：$leaf[n] = leaf[n - 1] + 1$
• 若高度差 1 ：$leaf[n] = (leaf[n - 1] + 1) * 2$
• 若高度差 k ：$leaf[n] = (leaf[n - 1] + 1) * 2^k$

可以得到一個重要的觀察，當碼字長度（高度）相等時，它們的值是連續的（這裏的連續是指整數上的連續），因爲每次都恰好增加 1。

有了這個特性，我們就不再需要 hash 函數，爲不同長度的碼字各建立一個陣列（也就是 16 個陣列），直接將碼字的二進位值當做索引所得到的位置，就能夠拿來儲存該碼字所對應的信源編碼。

當然，爲了節省空間，可以將索引減去該長度最小碼字的值，使得最小碼字的索引從 0 開始。