初始化 graph 的教訓，不熟的語法別亂用

昨晚跑了個程式，今天醒來不久接到york的電話，說連swap 在內資源都被我吃光了。

這個程式有三個步驟：

1. 從資料庫裡取出一些資料轉成 graph G(V, E)
2. 將 G(V, E) 轉成 G’(V, E’)，E’ = { (u, v) | (v, u) in E }
3. 利用 G, G’ 算HITS

原以為是 graph 大小超出我的預料，做了一些縮減後就重跑，吃完午餐回來看，不對，怎麼又停在產生 G’ 的部份。接著在一些錯誤的地方最佳化，最後找到問題的源頭。

在初始graph時, 我以前是這麼寫的：

ur = (1..user_ids.size).map { {} }

產生一個長度為 user_ids.size 的陣列，並在每一個元素內填入一個 hash table (i.e. {})，也就是類似 adjacency list 的存法，擁有 adjacency matrix 和 adjacency list 的好處。這可是過去試了許久找到最滿意的存法，改天再補上遲遲沒寫的 graph 表示法的心得吧。

上面那段程式以前用得好好的，後來我想試試新語法，改成這麼寫：

ur = [{}] * user_ids.size

這個寫法是原自下面這個 idiom code：

array = [0] * n

一般初始陣列時可以這麼寫，會得到一個長度為 n ，初始值為 0 的陣列。

可是 [{}] * n 表示所有元素都指向同一個 hash table (這行程式只產生了一個 hash table)，於是災難發生了，超大的 hash table 導至超糟的效率，更糟的是，我又用這個 graph 產生 G’，使得 G’ 變成幾乎 complete graph，然後 memory 就爆了 ( |V| 很大，但原本是 sparse graph)。

附帶一提， Ruby Cookbook 裡有提過這問題，當時有看懂，但沒完成參透啊！比方說當 hash 內元素不存在時，要自動產生一個陣列的話，標準錯誤寫法如下：

table = Hash.new([])

因為陣列只有被初始化一次，存在 table 內，當 table[key] 不存在時， 不管 key 為何，table 都會傳回那一個陣列。詳見以下的例子：

irb(main):088:0> table = Hash.new([]) irb(main):089:0> p table {} irb(main):090:0> table[0].push 5 irb(main):091:0> table[1].push 10 irb(main):092:0> p table {} irb(main):093:0> p table[2] [5, 10]

正確寫法如下：

table = Hash.new { |h,k| h[k] = [] }

這故事告訴我們，語法要學熟，不然等痛過後就會記熟了。