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

StackOverflow https://stackoverflow.com/questions/932721

Вопрос

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

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

Это было полезно?

Решение

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

Другие советы

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

http://www.mail-archive.com/haskell@haskell.org/msg01788.html

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

Я удивлен, что древовидная складка не входит в стандартную прелюдию, ведь она настолько полезна.Перевод версии, которую я написал в Ponder в октябре 1992 года — Джон Фэйрберн

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 node_a@(Node a heaps_a) node_b@(Node b heaps_b)
            | a < b = Node a (node_b: heaps_a)
            | otherwise = Node b (node_a: heaps_b)

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

В качестве упражнения на 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

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

А вот куча Фибоначчи в Haskell:

https://github.com/liuxinyu95/AlgoXY/blob/algoxy/datastruct/heap/other-heaps/src/FibonacciHeap.hs

Вот pdf-файл некоторых других k-арных куч, основанных на работе Окасаки.

https://github.com/downloads/liuxinyu95/AlgoXY/kheap-en.pdf

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

Массивы в 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 существует компромисс между использованием статических и изменяемых массивов.При использовании статических массивов вам придется создавать новые копии массивов при изменении элементов.При использовании изменяемых массивов сборщику мусора трудно разделить объекты разных поколений.Попробуйте реализовать пирамидальную сортировку с помощью STArray и посмотрите, понравится ли она вам.

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

Вот страница, содержащая версию HeapSort для машинного обучения.Он довольно подробный и должен послужить хорошей отправной точкой.

http://flint.cs.yale.edu/cs428/coq/doc/Reference-Manual021.html

Лицензировано под: CC-BY-SA с атрибуция
Не связан с StackOverflow
scroll top