Heaps gauchistes avec biais de poids: avantages de la version descendante de la fusion?

Question

Je suis auto-étudiant Okasaki's Purely Functional Data Structures, now on exercise 3.4, qui demande de raisonner et de mettre en œuvre un tas gauchiste biaisé par le poids. Ceci est ma mise en œuvre de 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 

Maintenant, 3.4 (c) & (d), il demande:

Actuellement, merge fonctionne en deux passe: une passe descendante consistant appels à merge, et une passe ascendante consistant en des appels à la fonction auxiliaire, makeT. Modifier merge à fonctionner dans une seule passe, top-down. Quels avantages aurait la version descendante de merge dans un environnement paresseux? Dans un environnement simultané ?

j'ai changé la fonction merge simplement inline makeT, mais je ne vois pas les avantages, donc je pense que je ne l'ai pas compris l'esprit de ces parties de l'exercice. Qu'est-ce que je rate?

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 

---

Je pense que j'ai compris un point en ce qui concerne l'évaluation paresseuse. Si je ne pas utiliser la fusion récursive pour calculer la taille, l'appel récursif doit pas être évalué jusqu'à ce que l'enfant est nécessaire:

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 

Est-ce tout? Cependant, je ne suis pas sûr de la concurrence.

Answer 1

Je pense que vous l'avez essentiellement eu pour l'évaluation paresseuse - il n'est pas très utile d'utiliser l'évaluation paresseuse si vous devez parcourir toute la structure de données pour trouver quelque chose à chaque fois que vous faire une fusion ...

En ce qui concerne la concurrence, je pense que le problème est que si un thread évalue la fusion, un autre arrive et veut chercher quelque chose, il ne sera pas en mesure d'obtenir quelque chose d'utile fait au moins jusqu'à ce que le premier thread termine la fusion. (Et il pourrait même prendre plus de temps que cela.)

Answer 2

Il ne bénéficie pas de la fonction WMERGE-3-4C dans un environnement paresseux. Il fait toujours tout le travail que la fusion descendante originale a fait. Il est quasiment certain qu'il ne sera pas plus facile de mémoriser le système de langue. Aucun avantage pour les fonctions WMERGE-3-4C dans un environnement simultané. Chaque appel à WMERGE-3-4C fait tout son travail avant de passer le test à une autre instance de WMERGE-3-4C. En fait, si nous éliminions la récursivité à la main, WMERGE-3-4C pourrait être implémenté comme une seule boucle qui fait tout le travail en accumulant une pile, puis une seconde boucle qui fait fonctionner REDUCE sur la pile. La première boucle ne serait pas naturellement parallèle, bien que le REDUCE pourrait peut-être fonctionner en appelant la fonction sur des paires, en parallèle, jusqu'à ce qu'un seul élément reste dans la liste.