Оптимизация хвостовых вызовов F # с 2 рекурсивными вызовами? - PullRequest
Новая
       51

Оптимизация хвостовых вызовов F # с 2 рекурсивными вызовами?

11 голосов
/ 11 июня 2011

Когда я писал эту функцию, я знал, что не получу оптимизацию хвостового вызова. Я до сих пор не нашел хорошего способа справиться с этим и надеялся, что кто-то еще может предложить предложения.

У меня есть дерево: 

type Heap<'a> =
| E
| T of int * 'a * Heap<'a> * Heap<'a>

И я хочу посчитать, сколько узлов в нем: 

let count h =
    let rec count' h acc =
        match h with 
        | E -> 0 + acc
        | T(_, value, leftChild, rightChild) ->
            let acc = 1 + acc
            (count' leftChild acc) + (count' rightChild acc)

    count' h 0

Это не оптимизировано из-за добавления подсчетов для дочерних узлов. Любая идея, как сделать что-то подобное, если дерево имеет 1 миллион узлов?

Спасибо, Дерек

Вот реализация count с использованием CPS. Это все еще взорвало стек. 

let count h =
    let rec count' h acc cont =
        match h with
        | E -> cont (1 + acc)
        | T(_,_,left,right) ->
            let f = (fun lc -> count' right lc cont)
            count' left acc f

    count' h 0 (fun (x: int) -> x)

Может, мне удастся придумать какой-нибудь способ разбить дерево на достаточное количество частей, чтобы я мог сосчитать их, не взорвав стек?

Кто-то спросил о коде, который генерирует дерево. Это ниже. 

member this.ParallelHeaps threads =
    let rand = new Random()
    let maxVal = 1000000

    let rec heaper i h =
        if i < 1 then
            h
        else
            let heap = LeftistHeap.insert (rand.Next(100,2 * maxVal)) h
            heaper (i - 1) heap

    let heaps = Array.create threads E
    printfn "Creating heap of %d elements, with %d threads" maxVal threads
    let startTime = DateTime.Now
    seq { for i in 0 .. (threads - 1) ->
          async { Array.set heaps i (heaper (maxVal / threads) E) }}
    |> Async.Parallel
    |> Async.RunSynchronously 
    |> ignore

    printfn "Creating %d sub-heaps took %f milliseconds" threads (DateTime.Now - startTime).TotalMilliseconds
    let startTime = DateTime.Now

    Array.length heaps |> should_ equal threads <| "The size of the heaps array should match the number of threads to process the heaps"

    let rec reMerge i h =
        match i with 
        | -1 -> h
        | _  -> 
            printfn "heap[%d].count = %d" i (LeftistHeap.count heaps.[i])
            LeftistHeap.merge heaps.[i] (reMerge (i-1) h)

    let heap = reMerge (threads-1) E
    printfn "Merging %d heaps took %f milliseconds" threads (DateTime.Now - startTime).TotalMilliseconds
    printfn "heap min: %d" (LeftistHeap.findMin heap)

    LeftistHeap.count heap |> should_ equal maxVal <| "The count of the reMerged heap should equal maxVal"

Ответы [ 2 ]

10 голосов
/ 11 июня 2011

Для решения этой проблемы вы можете использовать стиль продолжения (CPS).См. Рекурсирование при рекурсии - продолжение прохождения . Автор Matthew Podwysocki. 

let tree_size_cont tree = 
  let rec size_acc tree acc cont = 
    match tree with 
    | Leaf _ -> cont (1 + acc) 
    | Node(_, left, right) -> 
         size_acc left acc (fun left_size -> 
         size_acc right left_size cont) 

  size_acc tree 0 (fun x -> x)

Обратите также внимание, что в сборках отладки оптимизация хвостового вызова отключена.Если вы не хотите работать в режиме выпуска, вы можете включить оптимизацию в свойствах проекта в Visual Studio.

5 голосов
/ 18 июня 2011

CPS - хорошее общее решение, но вы также можете рассмотреть возможность явного использования стека, поскольку он будет быстрее и, возможно, проще: 

let count heap =
  let stack = System.Collections.Generic.Stack[heap]
  let mutable n = 0
  while stack.Count > 0 do
    match stack.Pop() with
    | E -> ()
    | T(_, _, heap1, heap2) ->
        n <- n + 1
        stack.Push heap1
        stack.Push heap2
  n
...