0

でを実装しようとしてtail-recursive MergeSortいOCamlます。

Mergesort当然、末尾再帰ではないので、それを実装するために使用しCPSています。

また、私の実装は、OCamlの末尾再帰マージソートに触発されています

以下は私のコードです

let merge compare_fun l1 l2 = 
  let rec mg l1 l2 acc =
    match l1, l2 with
      | ([], []) -> List.rev acc
      | ([], hd2::tl2) -> mg [] tl2 (hd2::acc)
      | (hd1::tl1, []) -> mg tl1 [] (hd1::acc)
      | (hd1::tl1, hd2::tl2) ->
         let c = compare_fun hd1 hd2
         in 
         if c = 1 then mg l1 tl2 (hd2::acc)
         else if c = 0 then mg tl1 tl2 (hd2::hd1::acc)
         else mg tl1 l2 (hd1::acc)
  in 
  mg l1 l2 [];;

let split_list p l = 
  let rec split_list p (acc1, acc2) = function
    | [] -> (List.rev acc1, List.rev acc2)
    | hd::tl ->
      if p > 0 then split_list (p-1) (hd::acc1, acc2) tl
      else split_list (p-2) (acc1, hd::acc2) tl
  in 
  split_list p ([], []) l;;

let mergeSort_cps compare_fun l =
  let rec sort_cps l cf =  (*cf = continuation func*)
    match l with 
      | [] -> cf []
      | hd::[] -> cf [hd]
      | _ ->
        let (left, right) = split_list ((List.length l)/2) l
        in 
        sort_cps left (fun leftR -> sort_cps right (fun rightR -> cf (merge compare_fun leftR rightR)))
  in 
  sort_cps l (fun x -> x);;

コンパイルして、で実行すると、1,000,000 integersのエラーが発生しますstackoverflow。なんで？

編集

テストに使用したコードは次のとおりです。

let compare_int x y =
  if x > y then 1
  else if x = y then 0
  else -1;;

let create_list n = 
  Random.self_init ();
  let rec create n' acc =
    if n' = 0 then acc
    else 
      create (n'-1) ((Random.int (n/2))::acc)
  in 
  create n [];;

let l = create_list 1000000;;

let sl = mergeSort_cps compare_int l;;

でhttp://try.ocamlpro.com/、このエラーが発生しました：Exception: RangeError: Maximum call stack size exceeded.

でlocal ocaml top level、問題ありませんでした

4

2 に答える 2

2

別のポイントを作るために別の答えを追加する：回答者間の混乱の多くは、標準のOCamlコンパイラを使用していないという事実によって引き起こされているようですが、javascriptの上に別個のOCamlバックエンドを実行するTryOCaml Webサイト、したがって、最適化と実行時の特性がわずかに異なります。

TryOCaml Webサイトで、表示されているCPSスタイルの関数mergeSort_cpsが長さのリストで失敗し1_000_000、次のエラーが発生するという事実を確実に再現できます。

Exception: InternalError: too much recursion.

私の分析によると、これはテールレックネスの欠如によるものではなく、JavascriptバックエンドでのCPS変換された呼び出しがテールレックであるという非自明な方法のサポートの欠如によるものです。ラムダ抽象境界（ただし、テール位置のまま）。

直接の非テールレックバージョンでコードを回すと、問題は解決します。

let rec merge_sort compare = function
  | [] -> []
  | [hd] -> [hd]
  | l ->
    let (left, right) = split_list (List.length l / 2) l in
    merge compare (merge_sort compare left) (merge_sort compare right);;

他の回答で述べたように、このコードには対数のスタック深度があるため、StackOverflowを使用しても発生しません（tail-recがすべてではありません）。Javascriptバックエンドがより適切に処理するのはより単純なコードです。

分割の二重走査を回避するより良い実装split（まだ定義を使用）を使用することで、大幅に高速化できることに注意してください。mergeList.length

let split li =
  let rec split ls rs = function
    | [] -> (ls, rs)
    | x::xs -> split rs (x::ls) xs in
  split [] [] li;;

let rec merge_sort compare = function
  | [] -> []
  | [hd] -> [hd]
  | l ->
    let (left, right) = split l in
    merge compare (merge_sort compare left) (merge_sort compare right);;
于 2013-02-26T12:32:26.580 に答える
0

コメントを読むと、Stack_overflowエラーを再現するのは難しいようです。

それでも、コードは完全にCPSまたは末尾再帰ではありません。merge_sortでは、呼び出しとsplit_list末尾merge呼び出し以外の位置での呼び出しが行われます。

問題は、CPS変換を行い、アキュムレータを多用することで、再帰に関連する最悪のスタック深度はどれくらいになるかということです。呼び出しでスタックの深さを保存sortすることは、実際にはあまり興味深いことではありません。それぞれがリストを2つに分割するため、最悪のスタックの深O(log n)さnは入力リストのサイズになります。

それどころか、アキュムレータ通過スタイルで記述されsplitていなければ、スタックをmerge線形に使用することになります。したがって、テールレックを作成することが重要です。O(n)これらのルーチンの実装はtail-recであるため、スタックの使用について心配する必要はなく、ソートルーチン自体をCPS形式に変換してコードを読みにくくする必要もありません。

（このlogarithmic-decrease引数は、mergesortに固有であることに注意してください。クイックソートは、最悪の場合、線形スタックを使用する可能性があるため、テールレックにすることが重要になる可能性があります。）

于 2013-02-26T06:00:25.087 に答える