2010-08-19 43 views
6

我自學Okasaki's Purely Functional Data Structures, now on exercise 3.4,要求推理和實施重量偏左的堆。這是我的基本實現:現在重量偏左的堆:自上而下版本的優勢?

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

,在3.4(C)&(d),它要求:

目前,merge工作於兩種 遍:自上而下的傳遞由 調用merge,以及由幫助者 函數makeT的調用組成的自底向上傳遞 。修改merge至 在一個自上而下的傳遞中操作。 自頂向下 版本merge在惰性 環境中有什麼優勢?在併發 環境中?

我通過簡單的內聯makeT改變merge功能,但我看不到任何優勢,所以我覺得我還沒有掌握鍛鍊這些部位的精神。我錯過了什麼?

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 

我想我已經想通了一個點與問候懶惰的評價。如果我不使用遞歸合併計算尺寸,然後遞歸調用將不再需要,直到孩子是需要進行評估:

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 

是這樣嗎?雖然我不確定併發。

回答

1

我認爲你已經基本上得到它,只要懶惰的評估 - 如果你不得不最終遍歷整個數據結構來找出你每次遇到任何事時使用懶惰評估是沒有什麼幫助的做一個合併...

至於併發性,我期望的問題是,如果,而當一個線程正在評估合併,另一個來,並希望看到的東西了,它將無法得到任何有用的至少在第一個線程完成合並之前完成。 (甚至可能需要更長的時間。)

1

這對於懶惰環境中的WMERGE-3-4C函數沒有任何好處。它仍然完成原始下合併過程中所做的所有工作。它確信語言系統不會更容易記憶。 在並行環境中對WMERGE-3-4C功能沒有益處。每次打電話給WMERGE-3-4C之前都要做好所有工作,然後再將其轉交給另一個WMERGE-3-4C實例。事實上,如果我們手工消除遞歸,WMERGE-3-4C可以作爲一個單獨的循環來實現,它可以在堆疊堆棧時完成所有工作,然後執行REDUCE在堆棧上工作的第二個循環。第一個循環不會自然平行,儘管也許REDUCE可以通過並行地調用成對函數來操作,直到列表中只剩下一個元素。