纯函数式语言中的高效堆
-
06-09-2019 - |
题
作为 Haskell 的练习,我正在尝试实现堆排序。在命令式语言中,堆通常被实现为数组,但这在纯函数式语言中效率非常低。因此,我研究了二进制堆,但到目前为止我发现的所有内容都是从命令式的角度描述它们的,并且所提出的算法很难转化为函数设置。如何用Haskell这样的纯函数式语言高效地实现堆?
编辑: 我所说的高效是指它仍然应该是 O(n*log n),但它不必击败 C 程序。另外,我想使用纯函数式编程。在 Haskell 中这样做还有什么意义呢?
其他提示
乔恩费尔贝恩张贴的官能堆排序到Haskell的咖啡馆的邮件列表早在1997年:
http://www.mail-archive.com/haskell@ haskell.org/msg01788.html
我再现它下面,重新格式化,以适应此空间。我还略微简化的merge_heap的代码。
我很惊讶treefold不在标准前奏,因为它是如此有用。从我在思考1992年10月写的版本翻译 - 乔恩·费尔贝恩
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单子势在必行堆排序。
{-# 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:
下面是基于Okasaki的工作的一些其他k元堆PDF文件。
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(日志N)的右下角元素的时间。你也可以看看通常不使用数组实现,如二项堆和斐波那契堆其他类型的堆。
在阵列性能最后需要说明的:在Haskell有使用静态数组,并使用可变阵列之间的折衷。使用静态数组,你有当你改变的元素创建数组的新副本。与可变阵列中,垃圾收集器具有一个很难保持分离的物体的不同世代。尝试推行使用STArray的堆排序,看你怎么喜欢它。
我试图端口标准的二进制堆到功能设置。有与所描述的想法的文章:从功能语法谈标准二叉堆。所有文章中的源代码清单是在Scala中。但它也可能被移植很容易进入其他任何功能性的语言。
下面是包含堆排序的ML版本的页面。这是相当详细,应该提供一个良好的起点。
http://flint.cs.yale.edu /cs428/coq/doc/Reference-Manual021.html