10進法でも2進法でも回文となる数のうち、1,000,000以下のものの和を求める。
今回は自信作である。解説する力量が自分にはないかも知れないが、最初のコードが20秒近い計算時間を要したものが、Data.Mapを使うことで0.2秒まで劇的に早くなった。
まず10進法を2進法に書き直すところで考える。2で割る計算を繰り返すのが常道だが、計算速度を上げたいので、以下の漸化式を利用する。この方法は有名なのかも知れないが、自分の中ではオリジナルである。
nの二進法表記を b(n) とすると
b(n) = b(n-1) + 1 （nが奇数）
_____b(n/2) (nが偶数）
（ただし演算は10進法の世界で行う）
さらに、漸化式が出てきたなら、連想リストを使って高速化が図れるのではないかと疑うのが、最近のトレンド(?)なので、Data.Mapに再登場願う。これまで連想リストは f(n-1)までの値を覚えておいて f(n) の計算の高速化を図るという使い方しかしてこなかったが、今回は1から100万までを順次評価しなければならないので、Table を携えてリストを走査するという、まさに「地図(MAP)を持って旅をしよう」という使い方を試みた。効果は絶大である。
mainが長ったらしくて分かりにくいが、まず回分素数だけを抽出して、その全てを2進数表示して、後で2進数→10進数の計算をしないで済むように、予め（10進数表記，2進数表記）のタプルとして連想リストで覚えておく。あとは2進数から回分だけを取り出して、fstでその10進数表記を拾い集めて和を取る…という、若干回りくどいことをしている。filterを2回使うところがロスしているような気もするが、多分Haskellが遅延評価を上手に使って効率的に処理してくれているのだろう…ということで納得しておくことにした。
早くなったどー☆
