0

我正在尝试实现一个tail-recursive MergeSortin 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);;

当我编译它并使用 a 运行它时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 网站，因此具有略微不同的优化和运行时特性。

我可以可靠地重现这样一个事实，即在TryOCaml 网站上，您显示的 CPS 样式函数mergeSort_cps在长度列表上失败，1_000_000并出现以下错误：

Exception: InternalError: too much recursion.

我的分析是，这不是由于缺乏 tail-rec-ness，而是由于 Javascript 后端缺乏对 CPS 转换调用为 tailrec 的非明显方式的支持：递归通过lambda 抽象边界（但仍处于尾部位置）。

在direct、 non-tail-rec 版本中打开代码会使问题消失：

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（仍然使用您的定义merge）来显着加快速度，从而避免双重遍历List.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_listmerge

问题是：通过进行 CPS 转换和大量使用累加器，与递归相关的最差堆栈深度是多少？在调用上保存堆栈深度sort实际上并不是很有趣：因为每个都将列表分成两部分，最差的堆栈深度将是O(log n)输入n列表的大小。

相反，如果它们不是以累加器传递样式编写的，split并且merge会线性O(n)使用堆栈，因此它们对于进行尾记录很重要。由于您对这些例程的实现是 tail-rec，因此无需担心堆栈使用，也无需将排序例程本身转换为 CPS 形式，这会使代码更难阅读。

（请注意，这个对数递减参数是特定于合并排序的。在最坏的情况下，快速排序可以使用线性堆栈，因此使其成为尾记录可能很重要。）

于 2013-02-26T06:00:25.087 回答