6

私はF＃コアライブラリソース（v.2.0）を読んでいて、かなり興味深いものを見つけました。それは、非常に単純なものとは
List.foldBack異なり、可変配列を介して実装されています。ここにソースがあります、またはあなたはここList.foldでそれを見つけるかもしれません：

let foldArraySubRight (f:OptimizedClosures.FSharpFunc<'T,_,_>) (arr: 'T[]) start fin acc = 
    let mutable state = acc
    for i = fin downto start do
        state <- f.Invoke(arr.[i], state)
    state

// this version doesn't causes stack overflow - it uses a private stack 
let foldBack<'T,'State> f (list:'T list) (acc:'State) = 
    // skipped optimized implementations for known lists

    // It is faster to allocate and iterate an array than to create all those 
    // highly nested stacks.  It also means we won't get stack overflows here. 
    let arr = toArray list
    let arrn = arr.Length
    foldArraySubRight f arr 0 (arrn - 1) acc

継続を使用しない理由は何ですか？
以下のコードのような素朴なものは、高度に最適化されたライブラリメソッドよりも2〜3倍遅く動作するようです。本当に「配列の割り当てと反復が高速」であるかどうかは疑わしいようです。また、末尾再帰であるため、ここではStackOverflowはありません。
私は何かが足りないのですか？

let foldBack2 predicate acc list =
    let rec loop list cont =
        match list with
        | [] -> cont acc
        | h::t -> loop t (fun racc -> cont (predicate h racc))
    loop list id
4

2 に答える 2

10

CPSを使用しない理由はいくつか考えられます。

  1. メモリをスタックスペースと交換します（これらの継続はすべてヒープ上に存在します）
  2. CPSはほとんどの人にとって不可解です
  3. あなたが発見したように、それは一般的に代替案よりも遅いです（証拠についてはこの質問を参照してください）

リストを簡単に逆方向にトラバースすることはできません。また、配列への/配列からのシーケンシャルアクセス（順方向または逆方向）のコピーは配列に勝るものがないため、実際には非常に効率的です。foldBack課題として、 10,000 / 100,000/100,000,000要素に対してより高速に記述してみてください。

于 2012-10-01T20:25:51.453 に答える
5

一般的なケースを速くします。

実際には、スタックオーバーフローを引き起こさない小さなリストを扱うことがよくあります。List.foldBack例として、 OCamlのF＃の対応物であるList.fold_rightは、末尾再帰でもCPSを使用していません。

ユーザーとして、私たちは内部実装が何であるかを本当に気にしません。高速と末尾再帰の両方があるという驚きを楽しんでいますList.foldBack。たとえば、この美しい分割関数はF＃では末尾再帰です。

let split list = List.foldBack (fun x (l,r) -> x::r, l) list ([],[])
于 2012-10-01T20:27:25.297 に答える