Левые кучи, ориентированные на вес: преимущества нисходящей версии слияния? - PullRequest
Новая
       38

Левые кучи, ориентированные на вес: преимущества нисходящей версии слияния?

6 голосов
/ 20 августа 2010

Я занимаюсь самообучением Чисто функциональные структуры данных Окасаки, теперь в упражнении 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 есть у ленивых среда? В одновременной окружающая среда

Я изменил функцию merge, просто вставив makeT, но я не вижу никаких преимуществ, поэтому думаю, что не понял дух этих частей упражнения. Чего мне не хватает? 

  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

Это все? Я не уверен насчет параллелизма.

Ответы [ 2 ]

1 голос
/ 07 декабря 2010

Это не приносит никакой пользы функции WMERGE-3-4C в ленивой среде.Он по-прежнему выполняет всю работу, которую выполняло первоначальное слияние вверх-вниз.Он уверен, что языковой системе будет легче запомнить. Никаких преимуществ для функций WMERGE-3-4C в параллельной среде.Каждый вызов WMERGE-3-4C выполняет всю свою работу, прежде чем переложить доллар на другой экземпляр WMERGE-3-4C.Фактически, если мы исключим рекурсию вручную, WMERGE-3-4C может быть реализован в виде одного цикла, который выполняет всю работу при накоплении стека, а затем второго цикла, который выполняет REDUCE для работы со стеком.Первый цикл не может быть парализован естественным образом, хотя, возможно, функция REDUCE могла бы работать, вызывая функцию параллельно, пока в списке не останется только один элемент.

1 голос
/ 03 декабря 2010

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

Что касается параллелизма, я ожидаю, что проблема заключается в том, что если, хотя один поток оценивает слияние, другой приходит и хочет что-то найти, он не сможет ничего получитьполезно сделать по крайней мере, пока первый поток не завершит слияние.(И это может даже занять больше времени.)

...