15

次のプログラムの実行速度について、さまざまな言語を楽しく比較してきました: for i from 1 to 1000000 sum the product i*(sqrt i)

私の実装の 1 つ (唯一のものではありません) は、リスト [1..1000000] を作成してから、特定の関数で折り畳むことです。

このプログラムは、Haskell では (foldl ではなく foldl を使用している場合でも) 正常かつ高速に動作しますが、OCaml と F# ではスタック オーバーフローが発生します。

Haskell コードは次のとおりです。

test = foldl (\ a b -> a + b * (sqrt b)) 0

create 0 = []
create n = n:(create (n-1))

main = print (test (create 1000000))

そして、ここに OCaml のものがあります:

let test = List.fold_left (fun a b -> a +. (float_of_int b) *. (sqrt (float_of_int b))) 0. ;;

let rec create = function
    | 0 -> []
    | n -> n::(create (n-1)) ;;

print_float (test (create 1000000));;

OCaml/F# 実装スタックがオーバーフローするのはなぜですか?

4

5 に答える 5

28

の Haskell コードcreateはリストを遅延評価しfoldlます。リスト全体を一度にすべて必要とするわけではありません。

対照的に、F# と OCaml はcreateリストを厳密に評価します。つまり、コードは に渡す前にリスト全体を一度に生成しようとしfold_leftます。

F# での 1 つの可能性はseq、関数で式を使用するcreateことです。これは、Haskell と同じ方法でリストを遅延生成します。(OCaml に同等の機能があるかどうかはわかりません。)

于 2010-02-20T14:39:29.670 に答える
22

まず、数値に関するパフォーマンスの比較を行う場合、リストは最良の選択ではありません。高速配列用のベクトルパッケージのようなパッケージを試してください。

そして、ループ融合のおかげで、Haskellでさらにうまくやれることに注意してください。create関数を列挙型として記述することにより、コンパイラーはcreateステップとfoldループを組み合わせて、中間データ構造を割り当てない単一のループにすることができます。このような一般的な融合を行う能力は、GHCHaskellに固有のものです。

ベクトルライブラリ（ストリームベースのループ融合）を使用します。

import qualified Data.Vector as V

test = V.foldl (\ a b -> a + b * sqrt b) 0

create n = (V.enumFromTo 1 n)

main = print (test (create 1000000))

さて、以前は、あなたのコードでは、コンパイラはすべてのリストを削除することができず、次のような内部ループになってしまいます。

$wlgo :: Double# -> [Double] -> Double#

$wlgo =
  \ (ww_sww :: Double#) (w_swy :: [Double]) ->
    case w_swy of _ {
      [] -> ww_sww;
      : x_aoY xs_aoZ ->
        case x_aoY of _ { D# x1_aql ->
        $wlgo
          (+##
             ww_sww (*## x1_aql (sqrtDouble# x1_aql)))
          xs_aoZ
        }
    }

$wcreate :: Double# -> [Double]

$wcreate =
  \ (ww_swp :: Double#) ->
    case ==## ww_swp 0.0 of _ {
      False ->
        :
          @ Double
          (D# ww_swp)
          ($wcreate (-## ww_swp 1.0));
      True -> [] @ Double
    }

2つのループがあることに注意してください。（遅延）リストを生成する作成と、それを消費するフォールドです。怠惰のおかげで、そのリストのコストは安いので、それは立派に実行されます：

$ time ./C
4.000004999999896e14
./C  0.06s user 0.00s system 98% cpu 0.058 total

ただし、フュージョンでは、代わりに単一のループのみが取得されます。

main_$s$wfoldlM_loop :: Double# -> Double# -> Double#

main_$s$wfoldlM_loop =
  \ (sc_sYc :: Double#) (sc1_sYd :: Double#) ->
    case <=## sc_sYc 1000000.5 of _ {
      False -> sc1_sYd;
      True ->
        main_$s$wfoldlM_loop
          (+## sc_sYc 1.0)
          (+##
             sc1_sYd (*## sc_sYc (sqrtDouble# sc_sYc)))

GHCは、作成とテストの手順を、リストを使用しない単一のループに減らしました。レジスターで2倍になります。また、ループの数が半分になると、実行速度はほぼ2倍になります。

$ ghc D.hs -Odph -fvia-C -optc-O3 -optc-march=native -fexcess-precision --make
$ time ./D
4.000005000001039e14
./D  0.04s user 0.00s system 95% cpu 0.038 total

これは、純度の保証が提供するパワーの良い例です。コンパイラーは、コードの再調整に非常に積極的になる可能性があります。

于 2010-02-20T18:23:43.463 に答える
9

F# で動作するようにコードを修正する別の方法は、同様に遅延生成されるシーケンス式を使用することですStackOverflow(シーケンス式は F# 固有であるため、OCaml では機能しません)。コードは次のとおりです。

let test nums = Seq.fold (fun a b -> 
  a + (float b) * (sqrt (float b))) 0.0 nums

let rec create count = seq {
  match count with
  | 0 -> do ()
  | n -> yield n
         yield! create (n-1) }

printf "%f" (test (create 1000000));;

パフォーマンスについてはわかりませんが、コンパイラは間違いなくcreate関数で最適化を行っているため、生成されたシーケンスの反復処理はかなり高速になるはずです。ただし、シーケンス式の目的は主に可読性です (F# は純粋ではないため、記述した純粋なコードを最適化する必要がある Haskell とは対照的に、本当に必要な場合に手動で最適化するための多くのスペースが与えられます)。とにかく、いくつかのテストがある場合は、試してみることができます！

于 2010-02-20T15:07:45.307 に答える
7

この形式では、create関数は末尾再帰ではありません。スタック オーバーフローを引き起こさない末尾再帰形式で書き直すことができます。

let rec create n l =
    match n with 
    | 0 -> l
    | n -> create (n-1) (n::l)

print_float (test (create 1000000 []));;
于 2010-02-20T14:43:10.693 に答える
3

このプログラムは、Haskell では (foldl ではなく foldl を使用している場合でも) 正常かつ高速に動作しますが、OCaml と F# ではスタック オーバーフローが発生します。

あなたの Haskell は遅延リストを使用していますが、OCaml/F# は厳密なリストを使用しているため、あなたのプログラムは比類のないものです。

FWIW、F# でオンデマンド シーケンスを使用するソリューションは次のとおりです。

Seq.sumBy (fun i -> let i = float i in i * sqrt i) (seq {1..1000000})
于 2010-05-11T02:31:55.373 に答える