合并排序为f sharp

Question

这是我的代码,当我输入一个非常大的数字我得到堆栈溢出错误有谁知道为什么？当我输入一个非常大的数字我得到了这个错误,我不确定是什么导致它,它只有大数小的工作正常.....

//
// merge two sorted lists into one:
//
let rec merge L1 L2 = 
  if L1 = [] && L2 = [] then
    []
  else if L1 = [] then
    L2
  else if L2 = [] then
    L1
  else if L1.Head <= L2.Head then
    L1.Head :: merge L1.Tail L2
  else
    L2.Head :: merge L1 L2.Tail

//
// mergesort:
//
let rec mergesort L = 
  match L with
 | []    -> []
 | E::[] -> L
 | _     -> 
   let mid = List.length L / 2
   let (L1, L2) = List.splitAt mid L
   merge (mergesort L1) (mergesort L2)

Answer 1

在你的两个函数中你都遇到了问题,你所采取的最后一步不是递归调用,而是其他一些事情:

• 在merge它是::操作
• 在mergesort它是merge

所以你必须达到最后一个是递归调用的地步!

在你有多个递归调用的情况下,一种可能性是使用continuation - 想法是传递一个函数,应该用当前步骤的结果调用,然后从那里继续计算.

这是使用此技术的尾递归版本mergesort:

let mergesort xs = 
    let rec msort xs cont = 
        match xs with
        | []    -> cont []
        | [x]   -> cont xs
        | _     -> 
            let mid = List.length xs / 2
            let (xs', xs'') = List.splitAt mid xs
            msort xs' (fun ys' -> msort xs'' (fun ys'' -> cont (merge ys' ys'')))
    msort xs id

正如你所看到的那样,这个想法并不难 - 而不是先调用两个递归路径,而是从一半开始,但增加了一个基本上表示的延续:

一旦我有结果mergesort xs'我拍摄效果ys',并通过不断mergesort荷兰国际集团xs'',然后合并这些

当然第二步是以同样的方式完成(推进merge到延续)

第一个延续通常是你在最后一行看到的身份;)

这里有类似的东西merge:

let merge xs ys = 
    let rec mrg xs ys cont =
        match (xs, ys) with
        | ([], ys) -> cont ys
        | (xs, []) -> cont xs
        | (x::xs', y::ys') ->
            if x < y 
            then mrg xs' ys (fun rs -> cont (x::rs))
            else mrg xs ys' (fun rs -> cont (y::rs))
    mrg xs ys id

那些当然会在堆上占用尽可能多的空间(可能更多) - 但这通常没问题 - 你的堆栈应该没问题;)