小記

• Ref.: 劉未鵬 | Mind Hacks – 知其所以然（續）
  

  最後再舉一個例子：算法書上幾乎必講的霍夫曼樹。你所看的算法書在講霍夫曼樹的時候給了證明嗎？講過霍夫曼樹的歷史八卦嗎？也許你看了霍夫曼樹的構造方法之後覺得：「哦，這樣啊，顯然」。但是你可曾想到，在最優編碼這個問題上，連香農本人之前給出的解法都只是suboptimal的，而且霍夫曼本人在得到這個算法之前也是絞盡腦汁幾近放棄。如果你10分鐘就「理解」了，那麼百分之百隻是背了課文而已。

  科科, 我倒是不知道這個小故事XD
  
• 友人的blog上看到一個有趣的小問題

  給定一個長度為n的陣列，我們希望可以把陣列向右旋轉p位，如何在線性時間常數的空間做到。

  友人提到有三種解法, Reverse法, Block Swap法, Juggling 法.(參考 Programming Pearls的一個章節) Juggling 法主要是藉由n和p找出 cycle decomposition，就可以直接交換了。
  
  慚愧的是, 雖然我看過 Programming Pearls, 但是我完全不記得有這個部分 Orz 而且很奇怪的是, 我只有想到 Juggling 法, 完全沒想到 Reverse法和 Block Swap法....
• Ref.: Fawcett, T. Data mining with cellular automata SIGKDD Explor. Newsl., ACM, 2008, 10, 32-39
  
  看到一篇有趣的論文, 是用 cellular automata 做 data mining. 他的概念是, 把 training set 轉換投射到 n-D grid 上面, 然後用特殊的 update rule 去跑 cellular automata, 看看收斂之後的 pattern 長什麼樣, 用這個方式來做 data mining.
  
  我之前是知道 cellular automata 可以用來解偏微分方程之類的東西. 不過用來做 data mining 是否真的適合? 畢竟這篇論文的做法, 其實沒有很特別, 而且要真的達到好的效能, 應該 update rule 和轉換投射的函式都需要特別設計吧. 這實在是沒有比較吸引人.