Подтвердить что ты не робот

Эффективные кучи в чисто функциональных языках

Как упражнение в Haskell, я пытаюсь реализовать heapsort. Куча обычно реализуется как массив на императивных языках, но это было бы крайне неэффективно на чисто функциональных языках. Поэтому я просмотрел двоичные кучи, но все, что я нашел до сих пор, описывает их с императивной точки зрения, и представленные алгоритмы трудно перевести на функциональные настройки. Как эффективно реализовать кучу в чисто функциональном языке, таком как Haskell?

Изменить: по эффективности я имею в виду, что он все равно должен быть в O (n * log n), но ему не нужно бить программу C. Кроме того, я хотел бы использовать чисто функциональное программирование. Что еще могло бы сделать это в Haskell?

4b9b3361

ОТВЕТЫ

Ответ 1

Существует ряд реализаций кучи Haskell в приложении к Okasaki чисто функциональные структуры данных. (Исходный код можно скачать по ссылке. Сама книга стоит прочитать.) Ни одна из них не является двоичной кучей, сама по себе, но "leftist" куча очень похожа. Он имеет операции ввода, удаления и слияния O (log n). Существуют также более сложные структуры данных, такие как перекос кучи, биномиальные кучи, и splay heaps, которые имеют лучшую производительность.

Ответ 2

Джон Фэйрбэрн опубликовал функциональный хаппорт для списка рассылки Haskell Cafe еще в 1997 году:

http://www.mail-archive.com/[email protected]/msg01788.html

Я воспроизведу его ниже, переформатированный, чтобы соответствовать этому пространству. Я также немного упростил код merge_heap.

Я удивлен, что treefold не входит в стандартную прелюдию, так как это так полезно. Перевод с версии, которую я написал в Ponder в октябре 1992 года - Jon Fairbairn

module Treefold where

-- treefold (*) z [a,b,c,d,e,f] = (((a*b)*(c*d))*(e*f))
treefold f zero [] = zero
treefold f zero [x] = x
treefold f zero (a:b:l) = treefold f zero (f a b : pairfold l)
    where 
        pairfold (x:y:rest) = f x y : pairfold rest
        pairfold l = l -- here l will have fewer than 2 elements


module Heapsort where
import Treefold

data Heap a = Nil | Node a [Heap a]
heapify x = Node x []

heapsort :: Ord a => [a] -> [a]    
heapsort = flatten_heap . merge_heaps . map heapify    
    where 
        merge_heaps :: Ord a => [Heap a] -> Heap a
        merge_heaps = treefold merge_heap Nil

        flatten_heap Nil = []
        flatten_heap (Node x heaps) = x:flatten_heap (merge_heaps heaps)

        merge_heap heap Nil = heap
        merge_heap [email protected](Node a heaps_a) [email protected](Node b heaps_b)
            | a < b = Node a (node_b: heaps_a)
            | otherwise = Node b (node_a: heaps_b)

Ответ 3

Вы также можете использовать монаду ST, которая позволяет вам писать императивный код, но безопасно демонстрировать чисто функциональный интерфейс.

Ответ 4

Как упражнение в Haskell, я применил императивный хаппорт с ST Monad.

{-# LANGUAGE ScopedTypeVariables #-}

import Control.Monad (forM, forM_)
import Control.Monad.ST (ST, runST)
import Data.Array.MArray (newListArray, readArray, writeArray)
import Data.Array.ST (STArray)
import Data.STRef (newSTRef, readSTRef, writeSTRef)

heapSort :: forall a. Ord a => [a] -> [a]
heapSort list = runST $ do
  let n = length list
  heap <- newListArray (1, n) list :: ST s (STArray s Int a)
  heapSizeRef <- newSTRef n
  let
    heapifyDown pos = do
      val <- readArray heap pos
      heapSize <- readSTRef heapSizeRef
      let children = filter (<= heapSize) [pos*2, pos*2+1]      
      childrenVals <- forM children $ \i -> do
        childVal <- readArray heap i
        return (childVal, i)
      let (minChildVal, minChildIdx) = minimum childrenVals
      if null children || val < minChildVal
        then return ()
        else do
          writeArray heap pos minChildVal
          writeArray heap minChildIdx val
          heapifyDown minChildIdx
    lastParent = n `div` 2
  forM_ [lastParent,lastParent-1..1] heapifyDown
  forM [n,n-1..1] $ \i -> do
    top <- readArray heap 1
    val <- readArray heap i
    writeArray heap 1 val
    writeSTRef heapSizeRef (i-1)
    heapifyDown 1
    return top

btw Я оспариваю, что если это не чисто функционально, тогда в Haskell нет смысла делать это. Я думаю, что моя реализация игру намного приятнее, чем то, что можно было бы сделать на С++ с шаблонами, передавая вещи во внутренние функции.

Ответ 6

Как и в эффективных алгоритмах Quicksort, написанных в Haskell, вам нужно использовать монады (трансформаторы состояния), чтобы делать что-то на месте.

Ответ 7

Я попытался перенести стандартную двоичную кучу в функциональные настройки. Существует статья с описанной идеей: Функциональный подход к стандартным двоичным кучам. Все исходные коды в статье указаны в Scala. Но это может быть легко перенесено на любой другой функциональный язык.

Ответ 8

Массивы в Haskell не так сильно неэффективны, как вы могли бы подумать, но типичная практика в Haskell, вероятно, будет реализована с использованием обычных типов данных, например:

data Heap a = Empty | Heap a (Heap a) (Heap a)
fromList :: Ord a => [a] -> Heap a
toSortedList :: Ord a => Heap a -> [a]
heapSort = toSortedList . fromList

Если бы я решал эту проблему, я мог бы начать с добавления элементов списка в массив, что упростит их индексирование для создания кучи.

import Data.Array
fromList xs = heapify 0 where
  size = length xs
  elems = listArray (0, size - 1) xs :: Array Int a
  heapify n = ...

Если вы используете двоичную максимальную кучу, вы можете отслеживать размер кучи при удалении элементов, чтобы вы могли найти нижний правый элемент в O (log N). Вы также можете взглянуть на другие типы куч, которые обычно не реализуются с использованием массивов, таких как биномиальные кучи и кучи фибоначчи.

Последняя заметка о производительности массива: в Haskell существует компромисс между использованием статических массивов и использованием изменяемых массивов. При использовании статических массивов вы должны создавать новые копии массивов при изменении элементов. С изменяемыми массивами сборщик мусора с трудом удерживает разные поколения разделенных объектов. Попробуйте реализовать heapsort с помощью STArray и посмотреть, как вам это нравится.