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

Question

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

編集:効率的とは、まだ O(n*log n) である必要があることを意味しますが、C プログラムに勝る必要はありません。また、純粋に関数型プログラミングを使用したいと思います。Haskellでそれを行うことのポイントは何ですか?

score 34 · Accepted Answer

Okasaki のPurely Functional Data Structuresの付録に、多数の Haskell ヒープ実装があります。(ソースコードはリンクからダウンロードできます。本自体は読む価値があります。) それ自体はバイナリヒープではありませんが、「左翼」ヒープは非常に似ています。O(log n) の挿入、削除、およびマージ操作があります。また、スキューヒープ、二項ヒープ、スプレイヒープなど、よりパフォーマンスの高い複雑なデータ構造もあります。

score 12 · Accepted Answer

Jon Fairbairn は、1997 年に Haskell Cafe メーリングリストに機能的なヒープソートを投稿しました。

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

このスペースに収まるように再フォーマットして、以下に再掲します。また、merge_heap のコードを少し単純化しました。

ツリーフォールドが非常に便利なため、標準のプレリュードに含まれていないことに驚いています。1992 年 10 月に私が Ponder に書いたバージョンからの翻訳 -- ジョンフェアバーン

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)

score 11 · Accepted Answer

モナドを使用することもSTできます。これにより、命令型コードを記述できますが、純粋に機能的なインターフェイスを安全に公開できます。

score 8 · Accepted Answer

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++ で達成するものよりもはるかに優れていると思います。内部関数に物を渡します。

score 3 · Accepted Answer

Haskell のフィボナッチヒープは次のとおりです。

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

岡崎氏の研究に基づく他の k-ary ヒープの pdf ファイルを次に示します。

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

score 2 · Accepted Answer

標準バイナリヒープを機能設定に移植しようとしました。説明されたアイデアの記事があります: A Functional Approach to Standard Binary Heaps。この記事のソースコードリストはすべて Scala です。しかし、他の関数型言語には非常に簡単に移植できます。

score 2 · Accepted Answer

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 を使用してヒープソートを実装してみて、気に入ったかどうかを確認してください。

score 2 · Accepted Answer

Haskell で書かれた効率的な Quicksort アルゴリズムと同じように、モナド (状態トランスフォーマー) を使用してインプレースで処理する必要があります。

score 1 · Accepted Answer

HeapSort の ML バージョンを含むページを次に示します。それは非常に詳細であり、良い出発点を提供するはずです.

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

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

9 に答える 9

Related

Reference