F＃中的尾递归：堆栈溢出
作为任务的一部分，我试图在大图上实现Kosaraju算法[MOOC Algo I Stanford on Coursera]
https://en.wikipedia.org/wiki/Kosaraju%27s_algorithm
当前的代码工作在一个小图上，但是我在运行时执行时遇到了Stack Overflow。
尽管已经阅读了F＃专家的相关章节，或者其他网站和SO上的例子，但我仍然不知道如何使用continuation来解决这个问题
下面是一般用途的完整代码，但它在执行DFSLoop1和递归函数DFSsub时已经失败。 我认为我没有让函数尾递归[因为指令
t<-t+1
G.[n].finishingtime <- t
？]
但我不明白我可以如何正确实施延续。
当仅考虑失败的部分时，DFSLoop1将作为我们将应用深度优先搜索的图形作为参数。 我们需要将完成时间记录为算法的一部分，以便在第二个DFS循环（DFSLoop2）中进入算法的第二部分[当然，我们在此之前是失败的]。
open System
open System.Collections.Generic
open System.IO
let x = File.ReadAllLines "C:UsersFaguiDocumentsGitHubLearning FsharpAlgo Stanford IPA 4 - SCC.txt";;
// let x = File.ReadAllLines "C:UsersFaguiDocumentsGitHubLearning FsharpAlgo Stanford IPA 4 - test1.txt";;
// val x : string [] =
let splitAtTab (text:string)=
text.Split [|'t';' '|]
let splitIntoKeyValue (A: int[]) =
(A.[0], A.[1])
let parseLine (line:string)=
line
|> splitAtTab
|> Array.filter (fun s -> not(s=""))
|> Array.map (fun s-> (int s))
|> splitIntoKeyValue
let y =
x |> Array.map parseLine
//val it : (int * int) []
type Children = int[]
type Node1 =
{children : Children ;
mutable finishingtime : int ;
mutable explored1 : bool ;
}
type Node2 =
{children : Children ;
mutable leader : int ;
mutable explored2 : bool ;
}
type DFSgraphcore = Dictionary<int,Children>
let directgraphcore = new DFSgraphcore()
let reversegraphcore = new DFSgraphcore()
type DFSgraph1 = Dictionary<int,Node1>
let reversegraph1 = new DFSgraph1()
type DFSgraph2 = Dictionary<int,Node2>
let directgraph2 = new DFSgraph2()
let AddtoGraph (G:DFSgraphcore) (n,c) =
if not(G.ContainsKey n) then
let node = [|c|]
G.Add(n,node)
else
let c'= G.[n]
G.Remove(n) |> ignore
G.Add (n, Array.append c' [|c|])
let inline swaptuple (a,b) = (b,a)
y|> Array.iter (AddtoGraph directgraphcore)
y|> Array.map swaptuple |> Array.iter (AddtoGraph reversegraphcore)
for i in directgraphcore.Keys do
if reversegraphcore.ContainsKey(i) then do
let node = {children = reversegraphcore.[i] ;
finishingtime = -1 ;
explored1 = false ;
}
reversegraph1.Add (i,node)
else
let node = {children = [||] ;
finishingtime = -1 ;
explored1 = false ;
}
reversegraph1.Add (i,node)
directgraphcore.Clear |> ignore
reversegraphcore.Clear |> ignore
// for i in reversegraph1.Keys do printfn "%d %A" i reversegraph1.[i].children
printfn "pause"
Console.ReadKey() |> ignore
let num_nodes =
directgraphcore |> Seq.length
let DFSLoop1 (G:DFSgraph1) =
let mutable t = 0
let mutable s = -1
let mutable k = num_nodes
let rec DFSsub (G:DFSgraph1)(n:int) (cont:int->int) =
//how to make it tail recursive ???
G.[n].explored1 <- true
// G.[n].leader <- s
for j in G.[n].children do
if not(G.[j].explored1) then DFSsub G j cont
t<-t+1
G.[n].finishingtime <- t
// end of DFSsub
for i in num_nodes .. -1 .. 1 do
printfn "%d" i
if not(G.[i].explored1) then do
s <- i
( DFSsub G i (fun s -> s) ) |> ignore
// printfn "%d %d" i G.[i].finishingtime
DFSLoop1 reversegraph1
printfn "pause"
Console.ReadKey() |> ignore
for i in directgraphcore.Keys do
let node = {children =
directgraphcore.[i]
|> Array.map (fun k -> reversegraph1.[k].finishingtime) ;
leader = -1 ;
explored2= false ;
}
directgraph2.Add (reversegraph1.[i].finishingtime,node)
let z = 0
let DFSLoop2 (G:DFSgraph2) =
let mutable t = 0
let mutable s = -1
let mutable k = num_nodes
let rec DFSsub (G:DFSgraph2)(n:int) (cont:int->int) =
G.[n].explored2 <- true
G.[n].leader <- s
for j in G.[n].children do
if not(G.[j].explored2) then DFSsub G j cont
t<-t+1
// G.[n].finishingtime <- t
// end of DFSsub
for i in num_nodes .. -1 .. 1 do
if not(G.[i].explored2) then do
s <- i
( DFSsub G i (fun s -> s) ) |> ignore
// printfn "%d %d" i G.[i].leader
DFSLoop2 directgraph2
printfn "pause"
Console.ReadKey() |> ignore
let table = [for i in directgraph2.Keys do yield directgraph2.[i].leader]
let results = table |> Seq.countBy id |> Seq.map snd |> Seq.toList |> List.sort |> List.rev
printfn "%A" results
printfn "pause"
Console.ReadKey() |> ignore
这是一个带有简单图形例子的文本文件
1 4
2 8
3 6
4 7
5 2
6 9
7 1
8 5
8 6
9 7
9 3
（引起溢出的那个是70Mo，大约有900,000个节点）
编辑
先澄清几件事这里是“伪代码”
输入：邻接表表示中的有向图G =（V，E）。 假设顶点V被标记为1,2,3，...， 。 。 ，n。 1.在所有弧的方向已经颠倒之后，让Grev表示图G。 2.在Grev上运行DFS-Loop子例程，按照给定顺序处理顶点，以获得每个顶点v∈V的结束时间f（v）。 3.在G上运行DFS-Loop子例程，按f（v）的降序处理顶点，为每个顶点v∈V分配一个领导。 4. G的强连通分量对应于共享一个共同领导的G的顶点。 图2 ：我们的SCC算法的顶层。 在第一次和第二次调用DFS-Loop时分别计算f值和领导者（见下文）。
输入：邻接表表示中的有向图G =（V，E）。 1.将全局变量t初始化为0. [这将跟踪已完全探索的顶点数量。] 2.将全局变量s初始化为NULL。 [这跟踪了最后一次调用DFS调用的顶点。] 3.对于i = n downto 1：[在第一次调用中，顶点被标记为1,2，...。 。 。 ，n任意。 在第二次调用中，顶点由第一次调用的f（v）值标记。]（a）如果我尚未探索：i。 设置s：= i ii。 DFS（G，i） 图3 ：DFS-Loop子程序。
输入：邻接表表示中的有向图G =（V，E），源顶点i∈V。 1.将我标为探索。 [在DFS-Loop调用的整个持续时间内仍然被探索。] 2.设置领导者（i）：= s 3.对于每个弧（i，j）∈G：（a）如果j尚未探索：i。 DFS（G，j）4. t + + 5.设置f（i）：= t 图4 ：DFS子程序。 只需在第一次调用DFS循环期间计算f值，并且只需在第二次调用DFS循环期间计算领导者值。
编辑我修改了代码，在一位经验丰富的程序员（一名Lisp但对F＃没有经验）的帮助下简化了第一部分，以便更快速地实现一个示例，而不会为此讨论中的非相关代码烦恼。
该代码只关注算法的一半，运行DFS一次以获得反转树的结束时间。
这是代码的第一部分，只是为了创建一个小例子，y是原始树。 元组的第一个元素是父元素，第二个元素是子元素。 但是我们将使用反向树
open System
open System.Collections.Generic
open System.IO
let x = File.ReadAllLines "C:UsersFaguiDocumentsGitHubLearning FsharpAlgo Stanford IPA 4 - SCC.txt";;
// let x = File.ReadAllLines "C:UsersFaguiDocumentsGitHubLearning FsharpAlgo Stanford IPA 4 - test1.txt";;
// val x : string [] =
let splitAtTab (text:string)=
text.Split [|'t';' '|]
let splitIntoKeyValue (A: int[]) =
(A.[0], A.[1])
let parseLine (line:string)=
line
|> splitAtTab
|> Array.filter (fun s -> not(s=""))
|> Array.map (fun s-> (int s))
|> splitIntoKeyValue
// let y =
// x |> Array.map parseLine
//let y =
// [|(1, 4); (2, 8); (3, 6); (4, 7); (5, 2); (6, 9); (7, 1); (8, 5); (8, 6);
// (9, 7); (9, 3)|]
// let y = Array.append [|(1,1);(1,2);(2,3);(3,1)|] [|for i in 4 .. 10000 do yield (i,4)|]
let y = Array.append [|(1,1);(1,2);(2,3);(3,1)|] [|for i in 4 .. 99999 do yield (i,i+1)|]
//val it : (int * int) []
type Children = int list
type Node1 =
{children : Children ;
mutable finishingtime : int ;
mutable explored1 : bool ;
}
type Node2 =
{children : Children ;
mutable leader : int ;
mutable explored2 : bool ;
}
type DFSgraphcore = Dictionary<int,Children>
let directgraphcore = new DFSgraphcore()
let reversegraphcore = new DFSgraphcore()
type DFSgraph1 = Dictionary<int,Node1>
let reversegraph1 = new DFSgraph1()
let AddtoGraph (G:DFSgraphcore) (n,c) =
if not(G.ContainsKey n) then
let node = [c]
G.Add(n,node)
else
let c'= G.[n]
G.Remove(n) |> ignore
G.Add (n, List.append c' [c])
let inline swaptuple (a,b) = (b,a)
y|> Array.iter (AddtoGraph directgraphcore)
y|> Array.map swaptuple |> Array.iter (AddtoGraph reversegraphcore)
// définir reversegraph1 = ... with....
for i in reversegraphcore.Keys do
let node = {children = reversegraphcore.[i] ;
finishingtime = -1 ;
explored1 = false ;
}
reversegraph1.Add (i,node)
for i in directgraphcore.Keys do
if not(reversegraphcore.ContainsKey(i)) then do
let node = {children = [] ;
finishingtime = -1 ;
explored1 = false ;
}
reversegraph1.Add (i,node)
directgraphcore.Clear |> ignore
reversegraphcore.Clear |> ignore
// for i in reversegraph1.Keys do printfn "%d %A" i reversegraph1.[i].children
printfn "pause"
Console.ReadKey() |> ignore
let num_nodes =
directgraphcore |> Seq.length
所以基本上图是（1-> 2-> 3-> 1）：:( 4-> 5-> 6-> 7-> 8 - > ....-> 99999-> 10000）和反向图（1→3→2→1）：:( 10000→9999→......→4）
这里是直接编写的主要代码
//////////////////// main code is below ///////////////////
let DFSLoop1 (G:DFSgraph1) =
let mutable t = 0
let mutable s = -1
let rec iter (n:int) (f:'a->unit) (list:'a list) : unit =
match list with
| [] -> (t <- t+1) ; (G.[n].finishingtime <- t)
| x::xs -> f x ; iter n f xs
let rec DFSsub (G:DFSgraph1) (n:int) : unit =
let my_f (j:int) : unit = if not(G.[j].explored1) then (DFSsub G j)
G.[n].explored1 <- true
iter n my_f G.[n].children
for i in num_nodes .. -1 .. 1 do
// printfn "%d" i
if not(G.[i].explored1) then do
s <- i
DFSsub G i
printfn "%d %d" i G.[i].finishingtime
// End of DFSLoop1
DFSLoop1 reversegraph1
printfn "pause"
Console.ReadKey() |> ignore
它没有尾递归，所以我们使用continuation，这里是相同的代码适应CPS风格：
//////////////////// main code is below ///////////////////
let DFSLoop1 (G:DFSgraph1) =
let mutable t = 0
let mutable s = -1
let rec iter_c (n:int) (f_c:'a->(unit->'r)->'r) (list:'a list) (cont: unit->'r) : 'r =
match list with
| [] -> (t <- t+1) ; (G.[n].finishingtime <- t) ; cont()
| x::xs -> f_c x (fun ()-> iter_c n f_c xs cont)
let rec DFSsub (G:DFSgraph1) (n:int) (cont: unit->'r) : 'r=
let my_f_c (j:int)(cont:unit->'r):'r = if not(G.[j].explored1) then (DFSsub G j cont) else cont()
G.[n].explored1 <- true
iter_c n my_f_c G.[n].children cont
for i in maxnum_nodes .. -1 .. 1 do
// printfn "%d" i
if not(G.[i].explored1) then do
s <- i
DFSsub G i id
printfn "%d %d" i G.[i].finishingtime
DFSLoop1 reversegraph1
printfn "faré"
printfn "pause"
Console.ReadKey() |> ignore
这两个代码都会编译并为小示例（评论中的一个）或我们正在使用的同一个树提供相同的结果，而较小的大小（1000而不是100000）
所以我不认为它是在这里的算法中的一个bug，我们有相同的树结构，只是一棵更大的树正在造成问题。 它看起来对我们的延续写得很好。 我们已经明确输入了代码。 所有的电话在所有情况下都会延续......
我们正在寻找专家的意见！ 谢谢 ！！！
我没有尝试去理解整个代码片断，因为它相当长，但是您肯定需要用一个使用continuation传递样式实现的迭代替换for循环。 就像是：
let rec iterc f cont list =
match list with
| [] -> cont ()
| x::xs -> f x (fun () -> iterc f cont xs)
我不明白DFSub函数中的cont的目的（它从来没有被调用过，是吗？），但是基于延续的版本看起来大致如下：
let rec DFSsub (G:DFSgraph2)(n:int) cont =
G.[n].explored2 <- true
G.[n].leader <- s
G.[n].children
|> iterc
(fun j cont -> if not(G.[j].explored2) then DFSsub G j cont else cont ())
(fun () -> t <- t + 1)
当你通过成千上万的条目递归时溢出堆栈实际上并不糟糕。 很多编程语言实现会比这个短得多的递归窒息。 你有严重的程序员问题 - 没有什么可羞愧的！
现在，如果你想做更深的递归而不是你的实现将要处理的事情，你需要改变你的算法，使其成为迭代和/或尾递归（两者是同构的 - 除了尾递归允许分散和模块化，而迭代是集中和非模块化）。
为了将算法从递归转换为尾递归（这是一种重要技能），您需要了解隐式存储在堆栈框架中的状态，即函数体中通过递归变化的自由变量，以及显式地将它们存储在一个FIFO队列中（一个复制堆栈的数据结构，并可以作为链表简单实现）。 然后，您可以将该已链接的帧变量链表作为参数传递给您的尾递归函数。
在更高级的情况下，你有许多尾递归函数，每个函数都有不同类型的框架，而不是简单的自递归，你可能需要为实现的栈帧定义一些相互递归的数据类型，而不是使用列表。 但我相信Kosaraju的算法只涉及自递归函数。
好的，所以上面给出的代码是正确的代码！ 问题在于编译器的F＃
这里有一些来自微软的话http://blogs.msdn.com/b/fsharpteam/archive/2011/07/08/tail-calls-in-fsharp.aspx
基本上，要小心设置，在默认模式下，编译器可能不会自动调用尾部调用。 为此，在VS2015中，进入解决方案资源管理器，用鼠标右键单击并单击“属性”（滚动列表的最后一个元素）。然后在新窗口中，单击“Build”并勾选“Generate尾巴呼叫“
它也是检查编译器是否使用ILDASM.exe查看反汇编的工作
你可以在我的github仓库中找到整个算法的源代码
https://github.com/FaguiCurtain/Learning-Fsharp/blob/master/Algo%20Stanford/Algo%20Stanford/Kosaraju_cont.fs
从表现的角度来看，我并不是很满意。 代码在我的笔记本电脑上运行36秒。 从论坛上与其他同行的MOOCers一起，C / C ++ / C＃通常在5秒内执行，Java在10-15左右，Python在20-30s左右执行。 所以我的实现显然没有优化。 我现在很高兴听到关于使技巧更快的技巧！ 谢谢 ！！！！
链接地址: http://www.djcxy.com/p/80577.html上一篇: Tail Recursion in F# : Stack Overflow
下一篇: System.OutOfMemoryException for a tail recursive function