Heap di sinistra con peso specifico: i vantaggi della versione top-down di unione?

Question

Sono autoapprendimento Okasaki's Purely Functional Data Structures, now on exercise 3.4, che chiede di ragionare e implementare un heap di sinistra ponderato. Questa è la mia implementazione di base:

(* 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 

Ora, a 3.4 (c) & (d), si chiede:

Attualmente, merge opera in due passaggi: un passaggio top-down che consiste di chiamate a merge e un passaggio bottom-up costituito da chiamate alla funzione helper , makeT. Modificare merge a operare in un unico passaggio dall'alto verso il basso. Quali vantaggi avrebbe la versione top-downdi merge in un ambiente pigro ? In un ambiente concorrente ?

ho cambiato la funzione merge semplicemente inlining makeT, ma non riesco a vedere alcun vantaggio, quindi penso che non ho afferrato lo spirito di questi parti dell'esercizio. Cosa mi manca?

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 

---

Credo di aver capito un punto per quanto riguarda la valutazione pigra. Se io non uso l'unione ricorsiva per calcolare la dimensione, quindi la chiamata ricorsiva non avrà bisogno di essere valutato fino a che è necessario che il bambino:

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 

È tutto? Non sono sicuro della concorrenza però.

Answer 1

Penso che tu abbia essenzialmente ottenuto fino alla valutazione pigra - non è molto utile usare la valutazione pigra se hai intenzione di finire per attraversare l'intera struttura dati per scoprire qualsiasi cosa ogni volta che unire ...

Per quanto riguarda la concorrenza, mi aspetto che il problema è che se, mentre un thread sta valutando l'unione, un altro arriva e vuole cercare qualcosa, non sarà in grado di ottenere qualcosa di utile fatto almeno fino a quando il primo thread completa l'unione. (E potrebbe anche richiedere più tempo.)

Answer 2

Non ha alcun beneficio per la funzione WMERGE-3-4C in un ambiente pigro. Fa ancora tutto il lavoro svolto dall'unione down down originale. È abbastanza sicuro che non sia più semplice memorizzare il sistema di lingua. Nessun vantaggio per le funzioni WMERGE-3-4C in un ambiente concorrente. Ogni chiamata a WMERGE-3-4C fa tutto il suo lavoro prima di passare il dollaro ad un'altra istanza di WMERGE-3-4C. Infatti, se eliminassimo la ricorsione a mano, WMERGE-3-4C potrebbe essere implementato come un singolo ciclo che fa tutto il lavoro mentre si accumula uno stack, quindi un secondo ciclo che fa il lavoro REDUCE sullo stack. Il primo ciclo non sarebbe naturalmente parallelizzabile, anche se forse il REDUCE potrebbe funzionare chiamando la funzione su coppie, in parallelo, fino a quando un solo elemento rimane nell'elenco.