Euler 4 を Haskell で高速化してみたが、、、

下記のような記事があって、

HaskellとOCamlの速度を比較してみた - let start programming = fun life -> life * 100;;

キャミバ様とガリグ先生がOCamlでコードを戦わせていたようだったので、こりゃ勝てないと思ってHaskellで高速化をしてみた。
結果、ぼくのコードは10倍に膨れ上がってしまった。

改善の趣旨としては、この問題は最大値を求める問題なので、探索空間をおおよそ大きい方からのリストにして、最初に見つかった解に対して、明らかに小さくなってしまう部分を切り捨てる。という方針。

is_circle n =
    let is_circle_sub m n r = if m == 0
        then r == n
        else is_circle_sub (m `div` 10) n (r * 10 + m `mod` 10)
    in
    is_circle_sub n n 0

declist a b limit tail =
    if b <= a
    then (a,b):(declist (a-1) (b+1) limit tail )
    else tail

-- decendant list of pair (a,b) on value a + b
declist_rec a b limit  = declist a b limit $
    if(a + b > 2)
    then
        if (a+b-1) > limit
        then declist_rec limit (a + b -1 -limit) limit
        else declist_rec (a+b-2) 1 limit
    else []

mult_list        = map (\ (x,y) -> x * y) $ declist_rec 999 999 999
index_mult_list  = zip [1..] mult_list

main =
    let (index,first_sol) = head $ filter (is_circle.snd) index_mult_list
        root              = floor $ sqrt $ fromInteger first_sol
        search_limit      = (\x->x * x) $ (\x -> (999 - x +1)) $ root
    in
    do
        print $ maximum $ filter is_circle $ drop (index-1) $ take search_limit mult_list

これがhideshi_oさんのオリジナルのコード

--Haskell
import Data.List
main = do
  print $ last $ filter (\x -> (reverse $ show x) == show x) $ sort ([x * y | x <- [100..999], y <- [100..999]])

さて、実行結果は

オリジナルコード：

[seg@seg-PC ~/haskell-sample]$ time ./Euler0
906609
0.000u 0.046s 0:04.09 0.9%      0+0k 0+0io 1355pf+0w

今回アルゴリズム改善したコード：

[seg@seg-PC ~/haskell-sample]$ time ./Euler
906609
0.000u 0.031s 0:00.04 75.0%     0+0k 0+0io 1356pf+0w

爆速になった。100万要素リストのトラバースをしないのだから当然と言っては当然。実際に探索した空間は2300くらい。500倍の差がつかないのは他に余計な計算をたくさんしているせいか。あ、takeを使わないでリストをたぐるだけの関数書けば速くなりそうな気がしますね。

ただ、元のコードにあった簡潔さはもうみじんもないし、コード行数も実質15倍。トレードオフといえばそれまでだけどなんだかなぁ、という気分にもなる。

元の趣旨であったと思われる「簡潔で見やすいコードの速度を比べてみる」というところからは明らかに外れたコード修正でした。