montones eficientes en lenguajes puramente funcionales
-
06-09-2019 - |
Pregunta
A modo de ejercicio en Haskell, estoy tratando de implementar heapsort. La pila se implementa normalmente como una matriz en lenguajes imperativos, pero esto sería altamente ineficiente en lenguajes puramente funcionales. Así que he mirado montones binarios, pero todo lo encontrado hasta ahora los describe desde un punto de vista imprescindible y los algoritmos presentados son difíciles de traducir en un ambiente funcional. Cómo implementar eficazmente un montón en un lenguaje puramente funcional como Haskell?
Editar: Por eficientes que significa que todavía debe estar en O (n * log n), pero no tiene que vencer a un programa en C. Además, me gustaría utilizar la programación puramente funcional. ¿Qué otra cosa podría ser el punto de hacerlo en Haskell?
Solución
Hay un número de implementaciones de montón Haskell en un apéndice de Okasaki de Estructuras de datos puramente funcional . (El código fuente se puede descargar en el enlace. El libro en sí es bien vale la pena leer.) Ninguno de ellos son montones binarios, per se, pero el " izquierda" montón es muy similar. Tiene O (log n) de inserción, eliminación, y operaciones de combinación. También hay estructuras de datos más complicadas como skew montones , montones binomiales y href="http://en.wikipedia.org/wiki/Splay_heap" que tienen un mejor rendimiento.
Otros consejos
Jon Fairbairn registró una heapsort funcional a la lista de correo Haskell Cafe en 1997:
http://www.mail-archive.com/haskell@ haskell.org/msg01788.html
Lo reproduzco a continuación, reformateado para adaptarse a este espacio. También he simplificado un poco el código de merge_heap.
Estoy sorprendido treefold no está en la antesala estándar ya que es muy útil. Traducido de la versión que escribí en Ponder en octubre de 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 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)
También es posible usar la mónada ST
, lo que le permite escribir código imperativo, sino exponer una interfaz puramente funcional con seguridad.
A modo de ejercicio en Haskell, que puso en marcha un heapsort imperativo con el ST Mónada.
{-# 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
I concurso que por cierto si no es puramente funcional, entonces no hay razón para hacerlo en Haskell. Creo que mi aplicación juguete es mucho mejor que lo que se podría lograr en C ++ con plantillas, que pasa alrededor de las cosas a las funciones internas.
Y aquí hay un montón de Fibonacci en Haskell:
Aquí están los archivos PDF para algunos otros montones k-ario basado en la obra de Okasaki.
https://github.com/downloads/liuxinyu95/AlgoXY/kheap- en.pdf
Al igual que en los algoritmos de ordenación rápida eficientes escrito en Haskell, es necesario utilizar mónadas (transformadores de estado) para hacer cosas en su lugar.
Las matrices en Haskell no son tan altamente ineficiente como se podría pensar, pero la práctica típica en Haskell, probablemente sería implementar esto utilizando tipos de datos comunes, como esto:
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
Si yo fuera la solución de este problema, que podría empezar por el relleno de los elementos de la lista en una matriz, por lo que es más fácil de ponerlos en un índice de creación de la pirámide.
import Data.Array
fromList xs = heapify 0 where
size = length xs
elems = listArray (0, size - 1) xs :: Array Int a
heapify n = ...
Si estás usando un máximo de almacenamiento dinámico binario, es posible que desee realizar un seguimiento del tamaño del montón como de quitar los elementos para que pueda encontrar el elemento inferior derecha en O (log n). También puede tomar un vistazo a otros tipos de pilas que no se implementan normalmente utilizando matrices, como montones binomiales y montones de Fibonacci.
Una nota final sobre las prestaciones del sistema: en Haskell hay un equilibrio entre la utilización de matrices estáticas y utilizando matrices mutables. Con los arreglos estáticos, usted tiene que crear nuevas copias de las matrices cuando cambie los elementos. Con los arreglos mutables, el recolector de basura tiene dificultades para mantener diferentes generaciones de objetos separados. Intenta implementar el uso de un heapsort starray y ver cómo te gusta.
He intentado puerto pila binaria estándar en configuraciones funcionales. Hay un artículo con la idea descrita: un enfoque funcional de estándar binarios Montones . Todos los listados de código fuente en el artículo son en Scala. Pero podría ser portado muy fácil en cualquier otro lenguaje funcional.
Aquí hay una página que contiene una versión de ML HeapSort. Es bastante detallado y debe proporcionar un buen punto de partida.
http://flint.cs.yale.edu /cs428/coq/doc/Reference-Manual021.html