为f锐利合并排序 [英] Merge sort for f sharp

问题描述

这是我的代码，当我输入一个非常大的数字时，我会得到堆栈溢出错误，有人知道为什么吗?当我输入一个非常大的数字时，我会收到该错误，而我不确定是什么原因造成的，这仅是在出现大量数字的情况下，小数字才可以正常工作.....

This is my code, when I enter a very large number I get stack overflow error does anyone know why? When i enter a very large number i get that error and im not really sure what is causing it, it is only with large numbers small ones work fine.....

//
// 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)

推荐答案

在两个函数中都存在问题，即您采取的最后一步不是递归调用，而是其他一些事情:

In both your functions you had the problem, that the last step you take is not the recursive call but some other thing:

• 在merge中是::操作
在mergesort中的
• 是merge

• in merge it is the :: operation
• in mergesort it is the merge

因此，您必须了解到最后一件事是递归调用！

So you have to get to a point where the very last thing is the recursive call!

在您进行多个递归调用的情况下，一种可能性是使用 continuations -想法是传递一个函数，该函数应与当前步骤的结果一起调用，然后从那里继续计算.

One possibility in situations where you have more than one recursive call to make is to use continuations - the idea is to pass a function around that should be called with the result of the current step and then continue the computation from there.

这是使用此技术的>的 tail-recursive 版本:

this is a tail-recursive version of mergesort using this technique:

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

如您所见，这个想法并不难-与其先调用两个递归路径，不如先调用它的一半，然后添加一个基本上表示如下的延续:

as you can see the idea is not to hard - instead of first calling both recursive paths it starts with just one half but adds a continuation that basically says:

一旦得到mergesort xs'的结果，就得到ys'的结果，然后继续mergesort ing xs''，然后将其合并

once I have the result of mergesort xs' I take the result ys' and continue by mergesorting xs'' and then merge those

当然，第二步以相同的方式完成(将merge推入接续)

of course the second step is done in just the same way (push the merge into the continuation)

最开始的 continuation 通常是您在最后一行看到的身份;)

the very first continuation is usually the identity as you can see in the very last line ;)

，这与您的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

---

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

---

those will of course take as much space on the heap (probably more) - but that is usually no problem - your stack should be fine ;)

这篇关于为f锐利合并排序的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！