從 Pentominoes 程式談起

對於一些年幼時期所玩過的益智遊戲，似乎總有著一股濃濃的情感。

Pentominoes 是一種拼圖益智遊戲，用十二片面積相等的不同拼塊，填滿一個 6x10 的長方形。下圖是一個拼好的例子：


印象中，國小時期曾經玩過這個益智遊戲，並且好像拼出兩百多個不同解。十多年前，在美國讀碩士班時，為了因應無聊的日子，曾用 Power Basic 寫過一個程式來解這個拼圖遊戲。記得當時的主機，還是 Intel 386。66M Hz 的 CPU，跑出所有 2339 組解，需要整整一天的時間。

曾幾何時，電腦硬體的進展飛速；同樣一支程式，在我現在的 1.73G Hz 的 Notebook 上執行，竟然只要 200 秒的時間。（我是有稍微改進了一些冗餘的程式迴圈，但沒有這些改進，依然可以在幾分鐘內跑完所有的解答。）

前些日子，想整理一些曾經感興趣的程式設計問題。很自然地，也想重新檢視一下這個解 Pentominoes 的程式。

溫故也該知新。回頭整理從前的東西，似乎也應檢視一下先進們的成果。用 Google 查了一下 Pentominoes，可以找到許多相關的網頁與程式。其中有一個 Gerard's Polyomino Solution Engine，竟然可以在 18~19 秒內，就跑出所有的解答！

坦白說，我當時是覺得有些氣餒。執行速度，怎麼會差這麼多呢？

前兩個月想開了些（不必要求完美 --- 即使自己的演算法或程式效能比較差，但應該也還是能藉此介紹一些有趣的東西），還是決定用 PHP 重新改寫自己的 Pentominoes 程式，順便改用 bit operations 來改善一些執行效能。很不幸地，執行後發現，竟然需要將近兩個小時的時間，才能跑出所有的解答！這當然也讓自己頗感訝異：雖然早知道 PHP 屬於 interpretive language，但... 似乎也跑得太慢了吧？

後來做了一些簡單的實驗，閱讀相關文件後，漸漸了解其實這是因為 PHP array 並不是像傳統的陣列，被配置在連續的記憶體區塊內。它是使用 hash table + double linked list 來實作的，因此執行 $array[$i]，實際上並不該被解譯為「取出 $array 區塊第 $i 個項目的內容」，而是「用 $i 作為 $array 雜湊表的 hash key，然後取得相對應的值」。如此一來，執行的速度當然就會慢上許多。

幾個星期前，突然想用 Java 來實作看看，了解一下自己的程式究竟比 Gerard 的程式慢上多少。大概是自己寫程式的習慣還不錯，從 PHP 改寫為 Java，含除錯竟然只需要幾個小時的時間。初步執行的結果是，需要 57 秒的時間。

哦，只需要不到一分鐘的時間！這下子精神來了，花上一個星期左右的時間來優化實作的方式，最後終於可以在 17~18 秒內，就把 2339 組解答都找出來。

於是，允許自己得意十七秒鐘，就當作是一個星期辛苦地優化程式的犒賞吧 :p