純粋関数型言語での効率的なヒープ

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

質問

Haskell の演習として、ヒープソートを実装しようとしています。ヒープは通常、命令型言語では配列として実装されますが、これは純粋な関数型言語では非常に非効率的です。そこで私はバイナリ ヒープについて調べてきましたが、これまでに見つけたものはすべて命令型の観点からバイナリ ヒープを説明しており、提示されたアルゴリズムを機能的な設定に変換するのは困難です。Haskell などの純粋関数型言語でヒープを効率的に実装するにはどうすればよいでしょうか?

編集： 効率的とは、依然として O(n*log n) 内にある必要があることを意味しますが、C プログラムを上回る必要はありません。また、純粋に関数型プログラミングを使用したいと考えています。Haskell でそれを行うことに他に何の意味があるでしょうか?

役に立ちましたか？

解決

オカサキの付録には、多数の Haskell ヒープ実装があります。 純粋に機能的なデータ構造. 。(ソースコードはリンクからダウンロードできます。この本自体は読む価値があります。) それらはいずれもそれ自体バイナリ ヒープではありませんが、 「左翼」の山 とても似ています。O(log n) 回の挿入、削除、およびマージ操作があります。次のようなより複雑なデータ構造もあります。 スキューヒープ, 二項ヒープ, 、 そして 広がる山 パフォーマンスが優れているもの。

他のヒント

ジョン・フェアバーンは、1997年に戻ってHaskellのカフェメーリングリストへの機能ヒープソートを掲示ます：

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モナドを、使用することができます。

ハスケルの練習として、私は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でそうするにはポイントがないことを争います。私は私のおもちゃの実装では、1は内部関数に渡すものを中心に、テンプレートを使用してC ++に達成するであろうものよりもはるかに良くあると思います。

そして、ここではHaskellでフィボナッチヒープあります：

ます。https：// githubの。 COM / liuxinyu95 / algoXY /ブロブ/ algoxy / datastruct /ヒープ/その他-ヒープ/ SRC / FibonacciHeap.hsする

ここでOkasakiの仕事に基づいていくつかの他のk-aryのヒープのための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する

ライセンス： CC-BY-SA と 帰属
所属していません StackOverflow
scroll top