Почему обход большого двоичного дерева приводит к переполнению стека даже при использовании стиля прохождения продолжения?

Question

Почему обход большого двоичного дерева приводит к переполнению стека даже при использовании стиля прохождения продолжения?

Глава 9 книги Эксперт F# 3.0 показывает, как использовать стиль прохождения продолжения, чтобы избежать переполнения стека при обходе двоичных деревьев. Я написал код обхода дерева, который почти идентичен коду из книги, но, тем не менее, я получаю переполнение стека. Мой код выглядит следующим образом:

type 'a Tree =
  | Leaf   of 'a
  | Branch of 'a Tree * 'a Tree

let rec mkLeftLeaningTree n tree =
  if n = 0 then
    tree
  else
    Branch (mkLeftLeaningTree (n - 1) tree, Leaf "right")

let leftLeaningTree1 = Leaf "left"
let leftLeaningTree2 = mkLeftLeaningTree 30000 leftLeaningTree1
let leftLeaningTree3 = mkLeftLeaningTree 30000 leftLeaningTree2
let leftLeaningTree4 = mkLeftLeaningTree 30000 leftLeaningTree3
let leftLeaningTree5 = mkLeftLeaningTree 30000 leftLeaningTree4
let leftLeaningTree6 = mkLeftLeaningTree 30000 leftLeaningTree5

let sizeContAcc tree =
  let rec worker acc tree cont =
    match tree with
      | Leaf _               -> cont (acc + 1)
      | Branch (left, right) -> worker acc left  (fun acc ->
                                worker acc right cont)
  worker 0 tree id

Загрузка этого в интерактивную среду F# и оценка выражения sizeContAcc leftLeaningTree6 делает переполнение стека. Почему это?

6

f# mono binary-tree tail-recursion continuation-passing

Источник

user7129045 08 ноя '16 в 00:38

2 ответа

Другие вопросы по тегам f# mono binary-tree tail-recursion continuation-passing

user5627983 09 ноя '16 в 00:17 2016-11-09 00:17 · Answer 1 · 2016-11-09 00:17

К сожалению, это может не помочь вам на самом деле решить проблему, но, возможно, оно дает некоторые указания, где искать. Сначала код и настройка. Я уменьшил размер самого дерева, чтобы оно работало в Windows. Остальное -.NET 4.6, 64-битная, win7, в VS2015 Update3.

type 'a Tree =
    | Leaf   of 'a
    | Branch of 'a Tree * 'a Tree

[<EntryPoint>]
let main argv =

    ///https://stackru.com/questions/40477122/why-does-traversing-a-large-binary-tree-result-in-a-stack-overflow-even-when-usi



    let rec mkLeftLeaningTree n tree =
      if n = 0 then
        tree
      else
        Branch (mkLeftLeaningTree (n - 1) tree, Leaf "right")



    let leftLeaningTree1 = Leaf "left"
    let leftLeaningTree2 = mkLeftLeaningTree 15000 leftLeaningTree1
    let leftLeaningTree3 = mkLeftLeaningTree 15000 leftLeaningTree2
    let leftLeaningTree4 = mkLeftLeaningTree 15000 leftLeaningTree3
    let leftLeaningTree5 = mkLeftLeaningTree 15000 leftLeaningTree4
    let leftLeaningTree6 = mkLeftLeaningTree 15000 leftLeaningTree5
    let leftLeaningTree7 = mkLeftLeaningTree 15000 leftLeaningTree6
    let leftLeaningTree8 = mkLeftLeaningTree 15000 leftLeaningTree7
    let leftLeaningTree9 = mkLeftLeaningTree 15000 leftLeaningTree8
    let leftLeaningTree10 = mkLeftLeaningTree 15000 leftLeaningTree9
    let leftLeaningTree11 = mkLeftLeaningTree 15000 leftLeaningTree10
    let leftLeaningTree12 = mkLeftLeaningTree 15000 leftLeaningTree11
    let leftLeaningTree13 = mkLeftLeaningTree 15000 leftLeaningTree12
    let leftLeaningTree14 = mkLeftLeaningTree 15000 leftLeaningTree13
    let leftLeaningTree15 = mkLeftLeaningTree 15000 leftLeaningTree14
    let leftLeaningTree16 = mkLeftLeaningTree 15000 leftLeaningTree15
    let leftLeaningTree17 = mkLeftLeaningTree 15000 leftLeaningTree16
    let leftLeaningTree18 = mkLeftLeaningTree 15000 leftLeaningTree17
    let leftLeaningTree19 = mkLeftLeaningTree 15000 leftLeaningTree18
    let leftLeaningTree20 = mkLeftLeaningTree 15000 leftLeaningTree19
    let leftLeaningTree21 = mkLeftLeaningTree 15000 leftLeaningTree20
    let leftLeaningTree22 = mkLeftLeaningTree 15000 leftLeaningTree21
    let leftLeaningTree23 = mkLeftLeaningTree 15000 leftLeaningTree22
    let leftLeaningTree24 = mkLeftLeaningTree 15000 leftLeaningTree23
    let leftLeaningTree25 = mkLeftLeaningTree 15000 leftLeaningTree24
    let leftLeaningTree26 = mkLeftLeaningTree 15000 leftLeaningTree25
    let leftLeaningTree27 = mkLeftLeaningTree 15000 leftLeaningTree26
    let leftLeaningTree28 = mkLeftLeaningTree 15000 leftLeaningTree27
    let leftLeaningTree29 = mkLeftLeaningTree 15000 leftLeaningTree28
    let leftLeaningTree30 = mkLeftLeaningTree 15000 leftLeaningTree29
    let leftLeaningTree31 = mkLeftLeaningTree 15000 leftLeaningTree30

    let sizeContAcc tree =
      let rec worker acc tree cont =
        match tree with
          | Leaf _               -> cont (acc + 1)
          | Branch (left, right) -> worker acc left  (fun acc ->
                                    worker acc right cont)
      worker 0 tree id



    sizeContAcc leftLeaningTree31  |> printfn "%A"

    printfn "%A" argv
    0 // return an integer exit code

Это скомпилировано с хвостовыми вызовами, оптимизировать в режиме Release:

C: \ Program Files (x86) \ Microsoft SDKs \ F# \ 4.0 \ Framework \ v4.0 \ fsc.exe -o: obj \ Release \ ConsoleApplication8.exe --debug: pdbonly --noframework --define: TRACE - doc:bin\Release\ConsoleApplication8.XML --optimize+ --platform:x64 -r:"C:\Program Files (x86)\ Справочные сборки \Microsoft\FSharp.NETFramework\v4.0\4.4.0.0\FSharp.Core.dll" -r:"C:\Program Files (x86)\ Справочные сборки \Microsoft\Framework.NETFramework\v4.6\mscorlib.dll" -r:"C:\Program Files (x86)\ Справочные сборки \Microsoft\Framework.NETFramework\v4.6\System.Core.dll" -r:"C:\Program Files (x86)\ Справочные сборки \Microsoft\Framework.NETFramework\v4.6\System.dll" -r:"C:\Program Files (x86)\ Справочные сборки \Microsoft\Framework.NETFramework\v4.6\System.Numerics.dll" --target:exe --warn:3 --warnaserror:76 --vserrors --LCID:1033 --utf8output --fullpaths --flaterrors --subsystemversion:6.00 --highentropyva+ --sqmsessionguid:057b9ccf-c89e-4da6-81ab-5295156e7a19 "C:\Users\userName\AppData\Local\Temp.NETFramework,Version=v.6.AssemblyAttributes.fs" AssemblyInfo.fs Program.fs 1> ConsoleApplication8 -> C:\Users\ имя пользователя \Documents\Visual Studio 2015\Projects\Stackru6\ConsoleApplication8\bin\Release\ConsoleApplication8.exe

Так с 31 деревьями это работает:

 .\ConsoleApplication8.exe
450001

Теперь давайте скомпилируем это в режиме отладки:

C: \ Program Files (x86) \ Microsoft SDKs \ F# \ 4.0 \ Framework \ v4.0 \ fsc.exe -o: obj \ Debug \ ConsoleApplication8.exe -g --debug: полная --noframework --define:DEBUG --define:TRACE --doc:bin\Debug\ConsoleApplication8.XML --optimize- --tailcalls- --platform:anycpu32bitpreferred -r:"C:\Program Files (x86)\ Справочные сборки \Microsoft\FSharp.NETFramework\v4.0\4.4.0.0\FSharp.Core.dll" -r:"C:\Program Files (x86)\ Справочные сборки \Microsoft\Framework.NETFramework\v4.6\mscorlib.dll" -r:"C:\Program Files (x86)\ Справочные сборки \Microsoft\Framework.NETFramework\v4.6\System.Core.dll" -r:"C:\Program Files (x86)\ Справочные сборки \Microsoft\Framework.NETFramework\v4.6\System.dll" -r:"C:\Program Files (x86)\ Справочные сборки \ Microsoft \ Framework.NETFramework \ v4.6 \ System.Numerics.dll "--target: exe --warn: 3 - -warnaserror: 76 --vserrors --LCID: 1033 --utf8output --fullpaths --flaterrors --subsystemversion: 6.00 --highentropyva + --sqmsessionguid: 057b9ccf-c89e-4da6-81ab-5295156e7a19 "C: \ Users \ userName Данные приложения\Local\Temp.NETFramework,Version=v4.6.AssemblyAttributes.fs" AssemblyInfo.fs Program.fs 1> ConsoleApplication8 -> C:\Users\ имя_пользователя \ Documents \ Visual Studio 2015 \ Проекты \Stackru6\ConsoleApplication8\bin\Debug\ConsoleApplication8.exe

И, ой:

> .\ConsoleApplication8.exe
Process is terminated due to StackruException.

Так в чем же разница?

В версии Release 9 tail вызовов, если вы декомпилируете IL, и я предполагаю, что это представлено каким-то циклом while.

IL_0073: ldloc.s 6
IL_0075: tail.
IL_0077: call int32 [FSharp.Core]Microsoft.FSharp.Core.LanguagePrimitives/HashCompare::GenericComparisonWithComparerIntrinsic<!a>(class [mscorlib]System.Collections.IComparer, !!0, !!0)

В версии отладки это будет отсутствовать:

L_007d: ldloc.s 6
IL_007f: call int32 [FSharp.Core]Microsoft.FSharp.Core.LanguagePrimitives/HashCompare::GenericComparisonWithComparerIntrinsic<!a>(class [mscorlib]System.Collections.IComparer, !!0, !!0)
IL_0084: ret

Для более простого примера тестирования вы можете проверить этот Вопрос, поскольку он имеет как рекурсивную, так и хвостовую рекурсивную версию алгоритма.

user6422174 08 ноя '16 в 10:04 2016-11-08 10:04 · Answer 2 · 2016-11-08 10:04

Мое первое предположение состояло в том, что вы размещаете функции друг над другом в своем аргументе cont, я понимал его как стек, который может переполниться (тогда как это было кучей, как объяснил Вольфганг в комментарии), но я провел несколько тестов, используя продолжение аргумент, и это не вызвало никакого переполнения стека. Вместо этого у меня было значительное замедление и, наконец, переполнение памяти.

Решением вашей конкретной проблемы было бы явное сохранение деревьев, которые вам нужно исследовать, в списке (вы все равно будете ограничены максимальным размером списка):

let sizeContAcc tree =
  let rec worker acc tree contList =
    match tree with
      | Leaf _ -> 
        match contList with
        | [] -> acc+1
        | t::cl -> worker (acc+1) t cl
      | Branch (left, right) -> worker acc left (right::contList)
  worker 0 tree []

Это работает и мгновенно дает мне 150001 для leftLeaningTree6.