F#中的尾递归:使用Quicksort进行反演

Question

嗨我在理解尾递归方面有些困难.我知道避免无限循环以及内存使用非常重要.我在"F#中的专家"中看到了一些关于像Fibonacci这样的简单函数的例子,但是当我的结果不仅仅是一个数字时,我认为我没有看过代码.

那么累加器会是什么？我不确定...

这是我写的一个递归函数.它使用快速排序算法计算数组中的反转次数.[它取自斯坦福大学的Coursera MOOC Algo I的练习]

如果有人能解释如何使尾部递归,我将不胜感激.[另外,我已经从命令式代码翻译了那段代码,因为我之前在R中写过,所以风格根本不起作用......]

另一个问题:语法是否正确,A是一个(可变)数组,我let A = ....到处都写过？为A <- ....更好地/一样的吗？

open System.IO
open System


let X = [|57; 97; 17; 31; 54; 98; 87; 27; 89; 81; 18; 70; 3; 34; 63; 100; 46; 30; 99;
    10; 33; 65; 96; 38; 48; 80; 95; 6; 16; 19; 56; 61; 1; 47; 12; 73; 49; 41;
    37; 40; 59; 67; 93; 26; 75; 44; 58; 66; 8; 55; 94; 74; 83; 7; 15; 86; 42;
    50; 5; 22; 90; 13; 69; 53; 43; 24; 92; 51; 23; 39; 78; 85; 4; 25; 52; 36;
    60; 68; 9; 64; 79; 14; 45; 2; 77; 84; 11; 71; 35; 72; 28; 76; 82; 88; 32;
    21; 20; 91; 62; 29|]

// not tail recursive. answer = 488

let N = X.Length

let mutable count = 0

let swap (A:int[]) a b =
    let tmp = A.[a]
    A.[a] <- A.[b]
    A.[b] <- tmp
    A

let rec quicksortNT (A:int[]) = 
    let L = A.Length


    match L with 
         | 1 -> A
         | 2 -> count <- count + 1
                if (A.[0]<A.[1]) then A 
                   else [|A.[1];A.[0]|]

         | x -> let p = x
                let pval = A.[p-1]
                let A = swap A 0 (p-1)
                let mutable i = 1
                for j in 1 .. (x-1) do 
                     if (A.[j]<pval) then let A = swap A i j
                                          i <- i+1
                // end of for loop

                // putting back pivot at its right place
                let A = swap A 0 (i-1)
                let l1 = i-1
                let l2 = x-i

                if (l1=0) then
                            let A =  Array.append [|A.[0]|] (quicksortNT A.[1..p-1])               
                            count <- count + (l2-1)
                            A
                     elif (l2=0) then 
                            let A = Array.append (quicksortNT A.[0..p-2]) [|A.[p-1]|]
                            count <- count + (l2-1)
                            A
                else
                            let A = Array.append ( Array.append (quicksortNT A.[0..(i-2)]) [|A.[i-1]|] ) (quicksortNT A.[i..p-1])
                            count <- count + (l1-1)+(l2-1)
                            A


let Y = quicksortNT X
for i in 1..N do printfn "%d" Y.[i-1]
printfn "count = %d" count

Console.ReadKey() |> ignore

非常感谢您的帮助

Answer 1

正如我在评论中所说:你进行inplace-swapping,因此重新创建和返回数组是没有意义的.

但是当您询问尾递归解决方案时,请使用list和continuation-passing-style来查看此版本,以使算法具有尾递归性:

let quicksort values =
    let rec qsort xs cont =
        match xs with
        | [] -> cont xs
        | (x::xs) ->
            let lower = List.filter (fun y -> y <= x) xs
            let upper = List.filter (fun y -> y > x) xs
            qsort lower (fun lowerSorted ->
                qsort upper (fun upperSorted -> cont (lowerSorted @ x :: upperSorted)))
    qsort values id

备注:

• 你可以这样想:
  • 首先将输入分区为upper和lower部分
  • 然后开始排序(递归)lower部分,当你完成这个继续...
  • ... lowerSorted对upper零件进行分类并继续...
  • ...获取两个已排序的部分,将它们连接起来并将它们传递到外部延续部分
  • 最外层的延续当然应该是id功能
• 有人会争辩说,这不是快速排序,因为它没有排序到位!
• 也许它很难看,但它是最后一次调用的尾递归qsort,它的结果将是当前调用的结果
• 我使用List是因为模式匹配非常好 - 但是你也可以将这个用于带有数组的版本
• 在那些情况下(如此处)你有多个递归调用我总是发现 - cont通过解决方案更容易编写和更自然 - 但也可以使用累加器(但它会变得混乱因为你需要通过你也)
• 这不会占用比没有cont-passing 的版本更少的内存 - 它只会放在堆而不是堆栈上(你通常有更多的堆可用;)) - 所以这有点像作弊
• 这就是为什么命令式算法在性能方面仍然更好的原因 - 所以通常的妥协是(例如)复制数组,在副本上使用inplace-algorithm然后返回副本 - 这样算法的行为就好像它是纯粹的在外面