Хвостовая рекурсия в F#: переполнение стека
Я пытаюсь реализовать алгоритм Косараджу на большом графике как часть задания [MOOC Algo I Stanford on Coursera]
https://en.wikipedia.org/wiki/Kosaraju%27s_algorithm
Текущий код работает на небольшом графике, но я нажимаю на переполнение стека во время выполнения.
Несмотря на то, что я прочитал соответствующую главу в Expert в F# или другие доступные примеры на веб-сайтах и SO, я все еще не понимаю, как использовать продолжение для решения этой проблемы.
Ниже приведен полный код общего назначения, но он уже завершится ошибкой при выполнении 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:\Users\Fagui\Documents\GitHub\Learning Fsharp\Algo Stanford I\PA 4 - SCC.txt";;
// let x = File.ReadAllLines "C:\Users\Fagui\Documents\GitHub\Learning Fsharp\Algo Stanford I\PA 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 и около 900000 узлов)
РЕДАКТИРОВАТЬ
сначала прояснить несколько вещей Вот "псевдокод"
Вход: ориентированный граф G = (V,E), в представлении списка смежности. Предположим, что вершины V помечены 1, 2, 3, .,, н. 1. Пусть Грев обозначает граф G после изменения ориентации всех дуг. 2. Запустите подпрограмму DFS-Loop в Grev, обрабатывая вершины в соответствии с заданным порядком, чтобы получить время окончания f(v) для каждой вершины v ∈ V . 3. Запустите подпрограмму DFS-Loop на G, обрабатывая вершины в порядке убывания f(v), чтобы назначить лидер каждой вершине v ∈ V . 4. Сильно связные компоненты группы G соответствуют вершинам группы G, которые имеют общий лидер.Рисунок 2: Верхний уровень нашего алгоритма SCC. Значения f и лидеры вычисляются в первом и втором вызовах DFS-Loop соответственно (см. Ниже).
Вход: ориентированный граф G = (V,E), в представлении списка смежности. 1. Инициализируйте глобальную переменную t равной 0. [Это отслеживает количество вершин, которые были полностью исследованы.] 2. Инициализируйте глобальную переменную s в NULL. [Это отслеживает вершину, из которой был вызван последний вызов DFS.] 3. Для i = n вплоть до 1: [В первом вызове вершины помечены 1, 2, .,, произвольно. Во втором вызове вершины помечаются своими f(v)-значениями из первого вызова.] (A), если я еще не исследовал: i. set 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. Значения f необходимо вычислять только во время первого вызова DFS-Loop, а значения лидера нужно вычислять только во время второго вызова DFS-Loop.
РЕДАКТИРОВАТЬ Я исправил код, с помощью опытного программиста (шучу, но не имевшего опыта в F#), упростив несколько первой части, чтобы иметь более быстрый пример, не заботясь о нерелевантном коде для этого обсуждения.
Код фокусируется только на половине алгоритма, запуская DFS один раз, чтобы получить время окончания обращенного дерева.
Это первая часть кода, просто для создания небольшого примера у исходного дерева. первый элемент кортежа является родительским, второй - дочерним. Но мы будем работать с обратным деревом
open System
open System.Collections.Generic
open System.IO
let x = File.ReadAllLines "C:\Users\Fagui\Documents\GitHub\Learning Fsharp\Algo Stanford I\PA 4 - SCC.txt";;
// let x = File.ReadAllLines "C:\Users\Fagui\Documents\GitHub\Learning Fsharp\Algo Stanford I\PA 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
это не хвостовая рекурсия, поэтому мы используем продолжения, вот тот же код, адаптированный к стилю 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)
так что я не думаю, что это ошибка в алгоритме здесь, у нас та же древовидная структура, просто большее дерево вызывает проблемы. нам кажется, что продолжения хорошо написаны. мы ввели код явно. и все звонки заканчиваются продолжением во всех случаях...
Мы ищем консультации экспертов!!! Спасибо!!!
3 ответа
ОК, поэтому приведенный выше код был ПРАВИЛЬНЫМ! проблема заключается в компиляторе F#
Вот несколько слов об этом от Microsoft http://blogs.msdn.com/b/fsharpteam/archive/2011/07/08/tail-calls-in-fsharp.aspx
В основном, будьте осторожны с настройками, в режиме по умолчанию компилятор НЕ может автоматически делать хвостовые вызовы. Для этого в VS2015 перейдите в Solution Explorer, щелкните правой кнопкой мыши и выберите "Свойства" (последний элемент списка прокрутки). Затем в новом окне нажмите "Построить" и установите флажок "Создать". хвостовые звонки
Также необходимо проверить, выполнил ли компилятор свою работу, глядя на разборку с помощью ILDASM.exe.
Вы можете найти исходный код для всего алгоритма в моем репозитории GitHub
с точки зрения производительности, я не очень доволен. Код работает на моем ноутбуке 36 секунд. На форуме с другими коллегами по MOOCers C/C++/C# обычно выполняется за доли секунды до 5 с, Java около 10-15, Python около 20-30 с. Так что моя реализация явно не оптимизирована. Теперь я рад услышать о трюках, чтобы сделать это быстрее! Спасибо!!!!
Я не пытался понять весь фрагмент кода, потому что он довольно длинный, но вам непременно нужно заменить for цикл с итерацией, реализованной с использованием стиля передачи продолжения. Что-то вроде:
let rec iterc f cont list =
match list with
| [] -> cont ()
| x::xs -> f x (fun () -> iterc f cont xs)
Я не поняла цель cont в вашем DFSub функция (она никогда не вызывается, не так ли?), но основанная на продолжении версия будет выглядеть примерно так:
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 (структура данных, которая копирует ваш стек и может быть тривиально реализована в виде связанного списка). Затем вы можете передать этот связанный список переменных кадра в качестве аргумента своим хвостовым рекурсивным функциям.
В более сложных случаях, когда у вас есть много хвостовых рекурсивных функций, каждая из которых имеет свой тип фрейма, вместо простой саморекурсии, вам может потребоваться определить некоторые взаимно рекурсивные типы данных для реформированных стековых фреймов вместо использования списка. Но я считаю, что алгоритм Косараджу включает только саморекурсивные функции.