本章探討計算機科學中「狀態」的概念及其應用。利用計算機解決問題的本質，就是把問題分解成獨立的狀態或過程，然後在狀態之間找到相互獨立或前後依賴的關係。掌握狀態的抽象、等價變換與因果關係鏈，是從業者系統性提升能力的關鍵。

9.1 從問題到狀態#

透過「捕鼠策略問題」來說明如何從具體問題中提煉出抽象的狀態。

  • 捕鼠問題：五個相連的格子中有一隻老鼠，每天移動到相鄰格子，每天可以打開一個格子的蓋子，問用什麼策略能抓住老鼠
  • 關鍵在於將老鼠所有可能的位置等價為幾種狀態：老鼠第一天在 1、3、5 位置，第二天一定在 2、4 位置，交替切換
  • 理解了狀態切換關係後，只需 6 天即可確保抓住老鼠（先處理 (2,4) 狀態，再處理 (1,3,5) 狀態）
  • 這個問題考查的是能否把具體問題變成抽象的狀態，並弄清狀態之間的切換關係

狀態的概念也應用在 N 元文法模型（N-gram Model）中：

  • 將大量不同的詞組合併為少數狀態，可以極大程度地縮小問題的規模
  • 例如在中英文機器翻譯中，用有限狀態機（FSM）將幾十萬個節點合併為幾千個狀態，時間可節省三到四個數量級
  • 在面向對象程序設計（OOD/OOP）中，把相似的操作合併、抽象成一個新的概念，也是同樣的思想

幾種情況只要組合在一起，組合數就會非常大，計算機速度再快、容量再大，可能也不夠用。解決問題的技巧就在於把類似的情況合併到同一個狀態中。

9.2 等價性：抽象出狀態的工具#

很多狀態能夠合併為一個狀態的原因，在於那些狀態在某種情況下是等價的。

整數置換問題#

  • 如何不使用額外的存儲單元完成兩個整數 x 和 y 的互換
  • 利用等價信息的概念：<x,y> 和 <x+y, y> 包含等價的信息
  • 三步完成：x <- x+y，y <- x-y，x <- x-y
  • 每一步中兩個存儲單元的數值雖然在不斷變化，但一直保持著和最初數值完全等價的信息

矢量量化（Vector Quantization）#

  • 將不同圖形投射到多維空間中的點，然後量化為少數有代表性的組合
  • 廣泛應用於語音壓縮編碼和識別、圖像壓縮、信號檢測、通信標準制定
  • 矢量字庫就是利用這個原理：用曲線函數模擬漢字或字母外形，不僅佔用空間小，而且無限放大也能保持圓滑

傅里葉變換#

  • 時域信號和頻域信號是等價的，可以互相轉換
  • 語音和圖片都可以透過等價變換（時域轉頻域）來濾除噪聲或壓縮數據
  • JPEG 格式就是把空間信號變成等價的頻率信號，大大壓縮圖像大小

等價性在硬體設計中的應用#

  • 數字電路的基礎就是將各種運算等價為最基本的與或、與非運算
  • 處理器內部沒有除法器，除法是通過乘法、加減法和查表來完成的
  • 了解除法實現的細節，寫代碼時要盡可能多用乘法、少用除法

等價性通常被用於歸類和間接地解決難題。三級以上的工程師必須能夠使用等價變換的工具，否則一些難題解決不了。

9.3 因果關係：建立狀態之間的聯繫#

將很多等價的情況合併為少數狀態之後，很多時候狀態之間是有因果關係的——從一個狀態經過某些操作可以變成另一個狀態。狀態之間的這些聯繫就構成了一張圖，此時可以使用圖論工具來解決問題。

三對老虎過河問題#

  • 三隻大老虎（A、B、C）和各自的小老虎（a、b、c）要過河
  • 船一次載兩隻老虎，小老虎身邊只能有自己的媽媽（否則會被其他大老虎吃掉）
  • 解題關鍵：先列出所有合法的狀態，濾除不合法的狀態，然後在合法狀態之間找到因果聯繫，畫成一張圖
  • 圖中從起點到終點的一條路徑就是答案，共需 7 步完成

因果關係鏈在實際中的應用#

  • 在計算機的算法或應用中，任意給出一個狀態，都要搞清楚原因，有時甚至要搞清楚原因的原因
  • Testing：尋找非法的狀態；Debugging：尋找造成非法狀態的因果關係鏈
  • Debug 的本質是根據異常現象倒推原因，沿著因果關係鏈逆向推理
  • 1994 年英特爾奔騰處理器的除法 bug 造成 5 億美元損失，說明即使設計和測試非常嚴格，也難免有考慮不周的情況

時間機器（Time Machine）#

  • 蘋果操作系統的備份功能利用了狀態和因果關係鏈的概念
  • 操作系統記錄文件系統的初始狀態，之後每小時記錄增量信息（當前狀態和之前狀態的差異）
  • 可以倒推出前一個狀態，找回被刪除或修改錯誤的文件
  • 軟體工程中的版本管理（如 Git）也是同樣的概念

在計算機軟硬體中，狀態之間通常是有因果關係的，從一個狀態經過一些中間過程到達另一個狀態，它們之間就有一個因果關係鏈。test 是要找到非法的狀態，而 debug 是要找到造成非法狀態的因果關係鏈。

結束語#

  • 計算機所能自動完成的實際上是計算：計算什麼、如何計算、如何將具體問題變成計算問題，這是計算機從業者需要解決的問題
  • 將問題中的各種情況抽象成狀態，用少數狀態覆蓋大量看似無關的情況，再釐清狀態之間的邏輯關係，是計算機從業者所應具備的能力
  • 在遇到問題時，特別是發現機器工作出錯時，能追蹤機器運行的狀態，通過因果關係快速找到問題所在，是資深從業者水平的體現