Obciążone lewe stosy waga: zalety top-down wersji scalania?

Question

Jestem samokształceniem Okasaki's Purely Functional Data Structures, now on exercise 3.4, który prosi o uzasadnienie i wdrożenie obciążonej wagi lewicowej sterty. To jest mój podstawowy realizacja:

(* 3.4 (b) *) 
functor WeightBiasedLeftistHeap (Element : Ordered) : Heap = 
struct 
    structure Elem = Element 

    datatype Heap = E | T of int * Elem.T * Heap * Heap 

    fun size E = 0 
    | size (T (s, _, _, _)) = s 
    fun makeT (x, a, b) = 
    let 
     val sizet = size a + size b + 1 
    in 
     if size a >= size b then T (sizet, x, a, b) 
     else T (sizet, x, b, a) 
    end 

    val empty = E 
    fun isEmpty E = true | isEmpty _ = false 

    fun merge (h, E) = h 
    | merge (E, h) = h 
    | merge (h1 as T (_, x, a1, b1), h2 as T (_, y, a2, b2)) = 
     if Elem.leq (x, y) then makeT (x, a1, merge (b1, h2)) 
     else makeT (y, a2, merge (h1, b2)) 
    fun insert (x, h) = merge (T (1, x, E, E), h) 

    fun findMin E = raise Empty 
    | findMin (T (_, x, a, b)) = x 
    fun deleteMin E = raise Empty 
    | deleteMin (T (_, x, a, b)) = merge (a, b) 
end 

Teraz, 3.4 (c) & (d), to pyta:

Obecnie merge działa w dwóch podań: top-down wprost składający dzwoni do merge, a od dołu do góry składa się z połączeń z pomocą funkcji, makeT. Zmodyfikuj merge na w jednym przejściu z góry do dołu. Jakie zalety miałaby wersja zstępująca wersja merge w leniwym środowisku ? W środowisku współbieżnym ?

zmieniłem funkcję merge po prostu inline makeT, ale nie widzę żadnych korzyści, więc myślę, że nie uchwycił ducha tych części ćwiczenia. czego mi brakuje?

fun merge (h, E) = h 
    | merge (E, h) = h 
    | merge (h1 as T (s1, x, a1, b1), h2 as T (s2, y, a2, b2)) = 
     let 
     val st = s1 + s2 
     val (v, a, b) = 
      if Elem.leq (x, y) then (x, a1, merge (b1, h2)) 
      else (y, a2, merge (h1, b2)) 
     in 
      if size a >= size b then T (st, v, a, b) 
      else T (st, v, b, a) 
     end 

---

myślę, że zorientowali się jeden punkt w odniesieniu do oceny leniwy. Jeśli nie używam rekurencyjnej seryjnej do obliczenia wielkości, wówczas wywołanie rekurencyjne nie będą musiały być oceniane jest potrzebna aż dziecko:

fun merge (h, E) = h 
    | merge (E, h) = h 
    | merge (h1 as T (s1, x, a1, b1), h2 as T (s2, y, a2, b2)) = 
     let 
    val st = s1 + s2 
     val (v, ma, mb1, mb2) = 
     if Elem.leq (x, y) then (x, a1, b1, h2) 
     else (y, a2, h1, b2) 
     in 
     if size ma >= size mb1 + size mb2 
     then T (st, v, ma, merge (mb1, mb2)) 
     else T (st, v, merge (mb1, mb2), ma) 
     end 

Czy to wszystko? Nie jestem jednak pewien co do współbieżności.

Answer 1

Wydaje mi się, że zasadniczo osiągnąłeś to aż do leniwej oceny - nie jest to zbyt pomocne, aby użyć leniwego oszacowania, jeśli będziesz musiał przejść przez całą strukturę danych, aby znaleźć cokolwiek za każdym razem, gdy wykonaj scalenie ...

Co do współbieżności, to spodziewam się, że jeśli jeden wątek ocenia połączenie, pojawia się inny i chce coś sprawdzić, to nie będzie w stanie uzyskać niczego użytecznego co najmniej do ukończenia scalania pierwszego wątku. (Może to potrwać nawet dłużej.)

Answer 2

Nie ma żadnej korzyści dla funkcji WMERGE-3-4C w leniwym otoczeniu. Nadal wykonuje całą pracę, którą wykonał oryginalny scalony zestaw. Jest całkiem pewne, że system językowy nie będzie łatwiejszy do zapamiętania .. Brak korzyści dla funkcji WMERGE-3-4C w środowisku współbieżnym. Każde wezwanie do WMERGE-3-4C wykonuje całą swoją pracę, zanim przejdzie do kolejnego wystąpienia WMERGE-3-4C. W rzeczywistości, jeśli wyeliminujemy rekursję ręcznie, WMERGE-3-4C może zostać zaimplementowany jako pojedyncza pętla, która wykonuje całą pracę podczas gromadzenia stosu, a następnie druga pętla, która wykonuje pracę REDUCE na stosie. Pierwsza pętla nie byłaby naturalnie paralelna, chociaż może REDUCE działałby przez wywołanie funkcji na parach równolegle, dopóki na liście nie pozostałby tylko jeden element.