ハミング数の算法 3種 - infinite list, imperative queue, cyclical iteration
この手の問題は、やはり Haskell で書くとスッキリする。
Hamming numbers - Rosetta Code から Haskell のコードを引用する。
hamming = 1 : map (2*) hamming `merge` map (3*) hamming `merge` map (5*) hamming where merge (x:xs) (y:ys) | x < y = x : xs `merge` (y:ys) | x > y = y : (x:xs) `merge` ys | otherwise = x : xs `merge` ys main = do print $ take 20 hamming print $ hamming !! 1690 print $ hamming !! 999999
ただし、この方法で第1000000項を求めようとすると、メモリを圧迫する。初項から第1000000項の全てを保持するためである。
実際、私の環境で実行するためには、JVMが最大で使用できるヒープメモリの制限を増やす必要があった。具体的には、-Xmx512m オプションを指定した。
このメモリ圧迫問題の解決法には、①明示的にキューに積んでポップするという imperative な方法と；② cyclical iteration を使う方法がある。
①の方法に関しては、scala 実装コードが、そのまんまの例。
②の方法に関しては、python 実装コードが、そのまんまの例。
cyclical iteration と言うと、難しく聞こえるが、本質は簡単。Stream(scala の無限リスト)の代わりに Iterator を用いることで、"忘れていく"無限リストを作ればよい。
python の cyclical iteration を scala に翻訳すると、下記のようになる。
cyclical iteration の implementation issues は、下記の2点：
- 前方参照をどう解決するか
- 後続項目の遅延評価をどうするか
以下、簡単な補足説明。
前方参照をどう解決したか。python は単に def すれば前方参照であることをごまかせるのに対して、scala は一工夫が必要。具体的には、class 定義のコンテキストにしてあげると、うまくごまかせる。object ForwardReferenceabl という ローカルな singleton を定義したのは、ひとえに前方参照をごまかすためのトリック。
では、後続項目の遅延評価をどうするか。scala において iterator を chain するのは Iterator#++() というメソッド。これは、引数を遅延評価してくれるので、一見すると、問題がないように思える。しかし、コードを書いてから分かったことだが、どうも scala の Iterator インタフェースのいろいろな実装の中には、.next を呼び出した際に、さらに一個先読みする実装が混ざっている*2ようだ。
そのため、本来は初項の1だけを初期値にすればよいところを、1,2 および 3,4,5 を指定している。(先読み問題を解決するために 1,2 を指定するとともに、循環参照部は 2の倍数系列と3の倍数系列と5の倍数系列を揃えるために 3, 4, 5 と指定した)
なお、私が Hamming 数に関心を抱いたきっかけは id:dev68 さんのエントリhttp://d.hatena.ne.jp/deve68/20110423/1303521318を拝見したためです。いつも参考にさせていただいております。ありがとうございます。
