Haskell：コードの2つのバージョンの速度の差

Question

私はいくつかの小さな問題を解決しようとすることによってHaskellに潜入し始めました。

私は「標準Haskellのフレンドリー」液と私の「非常に-醜いとハスケル・無愛想」バージョンの間には大きなパフォーマンスの差（〜100-200x）につまずいてきました。

私は仲間のハスケラーにとって、このパフォーマンスの違いが正当な理由があると確信しています。私はこれが欠けており、このトピックについて私に教育することができます。

問題：

の両方が解決で同じ概念使用し、数値、文字列内の最大5桁の数字を検索：すべての5桁の番号を生成し、最大値を見つけることを。

エレガントかつ迅速なコード

digit5 :: String -> Int 
digit5 = maximum . map (read . take 5) . init . tails 

大きな入力のための醜いと非常に遅いコード（文字列のサイズが大きいたら）私はほぼ同じ実行時間を取得し、小さな入力の場合

digit5' :: String -> String -> String 
-- xs - input string 
-- maxim - current maximal value 
digit5' xs maxim 
    | (length xs) < 5 = maxim 
    | y > maxim = digit5' (drop 1 xs) y -- use new detected maximum value 
    | otherwise = digit5' (drop 1 xs) maxim 
    where y = take 5 xs 

digit5 :: String -> Int 
digit5 xs 
-- return the original string if the input size is smaller than 6 
    | length (xs) < 6 = read xs 
    | otherwise = read $ digit5' xs "00000" 

、I非常に大きな違いが見られるようになります（44550要素の入力の場合）：

Computation time for ugly version: 2.047 sec 
Computation time for nice version: 0.062 sec 

私の表面的これを理解するには、高速コードがの事前利用可能な高次関数を使用していることです。より遅いバージョンでは再帰が使用されますが、私はテールの咬合が可能でなければならないと思います。しかし、naiveレベルでは、私にとってはどちらも同じことをしているようです。

代わりに数字に変換するのに遅い機能は、私はまた、int型に文字列を変換する文字列の比較を試みたんが、いずれかの大きな改善

せずに、私は任意のフラグなしとでGHCを使用してコンパイルしてみたものの次のコマンド：

ghc 
ghc -O2 
ghc -O2 -fexcess-precision -optc-O3 -optc-ffast-math -no- 
recomp 
stack runhaskell 
ghc -O3 

再現性のために、私はまた、コードcontaningにテストベクトルをリンクを追加している：https://pastebin.com/kuS5iKgd

Answer 1

あなたの「スロー」バージョンに問題があるTHI Sライン：

| length xs < 5 = maxim 

これは、xsの長さを計算し、Haskellのリストは単独で、リンクされたリストであるため、この操作はO（N）であるリスト全体の完全な横断を必要とします。それはすべての反復で発生します。 N回の反復があります。これはプロセス全体をO（n^2）にする。

一方、「高速」コードは線形であり、大きな入力では鮮やかに表示されます。

あなただけこれで問題のある行交換する場合：

| null xs = maxim 

をそれが全体のことは、単に線形になります、そしてそれは「エレガント」ソリューションと同じくらい速くなります。確かに、これは余分な5回の反復をもたらすが、その損失は全体的な複雑さを減らすことによって補う以上のものである。

あるいは、あなたが5つの文字または短い尾をフィルタリングすることにより、同じように遅い「エレガント」解決することができます：

digit5 = maximum . map (read . take 5) . filter ((>= 5) . length) . tails