在OCaml中基于列表的快速排序中的stack_overflow

Question

这是我对list-basedquicksort的实现:

let partition pivot l = 
    let rec p left right = function
      | [] -> (left, right)
      | hd::tl ->
    let c = compare pivot hd
    in 
    if c > 0 then
      p (hd::left) right tl
    else 
      p left (hd::right) tl
    in
    p [] [] l;;

let quicksort l =
  let rec qs = function
    | [] -> []
    | pivot::tl ->
      let (left, right) = partition pivot tl
      in 
      (qs left) @ (pivot::(qs right))
  in 
  qs l;;

---

当我尝试列表时100,000,它很好,没有问题.

但是,如果我尝试使用它1,000,000,它会给出错误stack_overflow.

---

我不明白为什么它会给出,stack_overflow因为我认为堆栈大小应该是这样的log1000000 ~ 20,对吧？

Answer 1

该@运营商将使用堆栈的线性量,我会承担.(这只是在列表上进行快速排序的问题之一.)

以下是@Pervasives模块的定义:

let rec ( @ ) l1 l2 =
  match l1 with
    [] -> l2
  | hd :: tl -> hd :: (tl @ l2)

这是一个非常缓慢的排序.如果你真的想要这个,你必须要聪明得多.至少你需要一个尾递归版本@.