f# - स्टैक ओवरफ्लो में एक बड़ा द्विआधारी पेड़ का परिणाम क्यों चल रहा है, जब भी निरंतरता-गुजर रहा है?




mono binary-tree (2)

किताब एक्सपर्ट एफ # 3.0 के अध्याय 9 में दिखाया गया है कि द्विआधारी पेड़ों का सफर करते समय स्टैक ओवरफ्लो से बचने के लिए निरंतरता-गुजर शैली का उपयोग कैसे करें। मैंने पेड़ के ट्रवर्सल कोड लिखा है जो पुस्तक से कोड के समान है, लेकिन फिर भी मैं स्टैक अतिप्रवाह करता हूं। मेरा कोड निम्नानुसार है:

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 मूल्यांकन कर रहा है sizeContAcc leftLeaningTree6 स्टैक ओवरफ्लो बनाता है। ऐसा क्यों है?


दुर्भाग्य से यह वास्तव में इस मुद्दे को ठीक करने में आपकी मदद नहीं कर सकता है लेकिन शायद यह कुछ संकेत प्रदान करता है जहां देखना है। सबसे पहले, कोड और सेटअप विंडोज़ पर काम करने के लिए मैंने पेड़ के आकार को कम किया है बाकी है। वी। एस .2015 अपडेट 3 में नेट 4.6, 64-बिट, जीत 7 है।

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

[<EntryPoint>]
let main argv =

    ///https://.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

इसे पुल कॉल के साथ संकलित किया गया है, रिलीज मोड में ऑप्टिमाइज़ करें:

C: \ Program Files (x86) \ Microsoft SDKs \ F # \ 4.0 \ Framework \ v4.0 \ fsc.exe -o: obj \ Release \ ConsoleApplication8.exe --debug: pdbonly --noframework - डिफाइन: ट्रेसे - doc: bin \ release \ ConsoleApplication8.XML - ऑप्टिमाइज़ + - प्लेटफार्म: x64 -r: "C: \ Program Files (x86) \ संदर्भ असेंबली \ Microsoft \ FSharp.NETFramework \ v4.0 \ 4.4.0.0 \ FSharp.Core .dll "-r:" C: \ Program Files (x86) \ संदर्भ Assemblies \ Microsoft \ Framework.NETFramework \ v4.6 \ mscorlib.dll "-r:" C: \ Program Files (x86) \ संदर्भ Assemblies \ Microsoft \ Framework.NETFramework \ v4.6 \ System.Core.dll "-r:" C: \ Program Files (x86) \ संदर्भ असेंबली \ Microsoft \ Framework.NETFramework \ v4.6 \ System.dll "-r:" C : \ प्रोग्राम फ़ाइलें (x 86) \ संदर्भ असेंबली \ Microsoft \ Framework.NETFramework \ v4.6 \ System.Numerics.dll "--target: exe --warn: 3 --warnaserror: 76 - वीसरर - एलसीआईडी: 1033 --utf8output --fullpaths --flaterrors --subsystemversion: 6.00 --highentropyva + --sqmsessionguid: 057b 9ccf-c89e-4da6-81ab-5295156e7a19 "सी: \ उपयोगकर्ता \ उपयोगकर्ता नाम \ AppData \ स्थानीय \ Temp.NETFramework, संस्करण = v4 6.Asse mblyAttributes.fs "AssemblyInfo.fs Program.fs 1> ConsoleApplication8 -> सी: \ उपयोगकर्ता \ उपयोगकर्ता नाम \ दस्तावेज़ \ विजुअल स्टूडियो 2015 \ परियोजनाओं \ 6 \ ConsoleApplication8 \ bin \ रिलीज कंसोल अनुप्रयोग API.exe

तो 31 पेड़ों के साथ यह काम करता है:

 .\ConsoleApplication8.exe
450001

अब डीबग मोड में इसे संकलित करते हैं:

सी: \ प्रोग्राम फ़ाइलें (x 86) \ Microsoft SDKs \ F # \ 4.0 \ फ्रेमवर्क \ v4.0 \ fsc.exe -o: obj \ डिबग \ कंसोल Application.exe -g -debug: full --noframework --define: DEBUG - परिभाषित: ट्रेक - डॉक: बिन \ डीबग \ कंसोल अनुप्रयोग 9। एक्सएमएल - ऑप्टिमाइज़- - टेलिकॉल्स- - प्लेटफार्म: anycpu32bitpreferred -r: "सी: \ प्रोग्राम फ़ाइलें (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 : \ प्रोग्राम फ़ाइलें (x 86) \ संदर्भ असेंबली \ 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 - -वार्नासॉररर: 76 - वीसरर - एलसीआईडी: 1033 --यूएफ 8 आउटपुट --फुलपाथ - फ्लाटरर्स - सब्सिस्टिववर्जन: 6.00 --हिगेनट्रापीवा + --sqmsessionguid: 057 बी 9 सीसीएफ-सी 8 9-4 डी 6-81 बी-5295156 ए 7 ए 1 9 "सी: \ यूजर यूजरनेम \ एप्लिकेशन आंकड़ा\ स्थानीय \ Temp.NETFramework, Version = v4.6.AssemblyAttributes.fs "AssemblyInfo.fs Program.fs 1> ConsoleApplication8 -> सी: \ उपयोगकर्ता \ उपयोगकर्ता नाम \ दस्तावेज़ \ विज़ुअल स्टूडियो 2015 \ परियोजनाओं \ 6 \ ConsoleApplication8 \ bin \ Debug \ ConsoleApplication8.exe

और, उफ़:

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

तो अंतर क्या है?

रिलीज़ संस्करण में 9 tail कॉल हैं, यदि आप आईएल को डीकंपिल करते हैं, और मुझे लगता है कि यह किसी प्रकार का लूप है जब इसे दर्शाया जाता है।

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

जांच करने के लिए एक सरल उदाहरण के लिए आप इस प्रश्न की जांच कर सकते हैं क्योंकि इसमें एल्गोरिथम के पुनरावर्ती और पूंछ पुनरावर्ती संस्करण दोनों हैं।


मेरा पहला अनुमान यह था कि आप अपने तर्क में एक-दूसरे के ऊपर कार्य कर रहे हैं, मैं इसे एक स्टैक के रूप में समझा, जो अतिप्रवाह हो सकता है (जबकि वोफ़गैंग ने टिप्पणी में एक ढेर के रूप में समझाया है) लेकिन मैंने कुछ परीक्षण किए तर्क और इसके कारण किसी भी स्टैक ओवरफ्लो का कारण नहीं था इसके बजाय, मुझे एक महत्वपूर्ण मंदी थी और अंत में एक स्मृति अतिप्रवाह पर पहुंच गया।

आपकी विशिष्ट समस्या का एक समाधान उन पेड़ों को स्पष्ट रूप से संग्रहीत करने के लिए होगा जिन्हें आपको एक सूची में तलाशने की आवश्यकता होगी (आप सूची के लिए अधिकतम आकार तक भी सीमित रहेंगे):

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 छोड़ देता है लैनिंगट्री 6





continuation-passing