순전히 기능적인 언어로 효율적인 힙

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

문제

Haskell에서 운동으로 Heapsort를 구현하려고합니다. 힙은 일반적으로 명령적인 언어로 배열로 구현되지만 순전히 기능적인 언어에서는 매우 비효율적입니다. 그래서 나는 이진 힙을 살펴 보았지만 지금까지 찾은 모든 것은 명령적인 관점에서 그것들을 설명하고 제시된 알고리즘은 기능적 설정으로 번역하기가 어렵습니다. Haskell과 같은 순전히 기능적인 언어로 힙을 효율적으로 구현하는 방법은 무엇입니까?

편집하다: 효율적으로 나는 여전히 O (n*log n)에 있어야하지만 C 프로그램을 이길 필요는 없습니다. 또한 순전히 기능적인 프로그래밍을 사용하고 싶습니다. Haskell에서 그것을하는 요점은 무엇입니까?

도움이 되었습니까?

해결책

Okasaki의 부록에는 많은 Haskell 힙 구현이 있습니다. 순전히 기능적인 데이터 구조. (소스 코드는 링크에서 다운로드 할 수 있습니다. 책 자체는 읽을 가치가 있습니다.) 그 중 어느 것도 이진 힙, 그 자체는 없습니다. "좌파"힙 매우 유사합니다. O (log n) 삽입, 제거 및 병합 작업이 있습니다. 더 복잡한 데이터 구조도 있습니다 꼬치 힙, 이항 힙, 그리고 쌓인 힙 더 나은 성능을 가진.

다른 팁

Jon Fairbairn은 1997 년에 Haskell Cafe 메일 링리스트에 기능용 힙소를 게시했습니다.

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

나는이 공간에 맞게 개혁 된 아래에서 그것을 재생산한다. 또한 merge_heap 코드를 약간 단순화했습니다.

나는 Treefold가 표준 전주곡에 있지 않다는 것에 놀랐습니다. 1992 년 10 월 Ponder에서 쓴 버전에서 번역 -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)

당신은 또한 사용할 수 있습니다 ST Monad는 명령 코드를 작성할 수 있지만 순전히 기능적인 인터페이스를 안전하게 노출시킬 수 있습니다.

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

BTW 나는 순전히 기능적이지 않다면 Haskell에서는 그렇게 할 필요가 없다고 경쟁합니다. 내 장난감 구현은 템플릿으로 C ++에서 달성하여 내부 기능으로 물건을 전달하는 것보다 훨씬 좋다고 생각합니다.

그리고 여기 Haskell의 Fibonacci 힙이 있습니다.

https://github.com/liuxinyu95/algoxy/blob/algoxy/datrastruct/heap/other-heaps/src/fibonacciheap.hs

다음은 오카사키의 작업을 기반으로 한 다른 K-Ary 힙에 대한 PDF 파일입니다.

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

Haskell에 작성된 효율적인 QuickSort 알고리즘과 마찬가지로 Monads (State Transformers)를 사용하여 작업을 수행해야합니다.

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에는 정적 어레이 사용과 Mutable Array를 사용하는 것 사이에 트레이드 오프가 있습니다. 정적 배열을 사용하면 요소를 변경할 때 배열의 새 사본을 만들어야합니다. 변수 어레이를 사용하면 쓰레기 수집기는 다른 세대의 물체를 분리하는 데 어려움을 겪고 있습니다. Starray를 사용하여 Heapsort를 구현하고 좋아하는 방법을 확인하십시오.

표준 바이너리 힙을 기능 설정으로 포트하려고했습니다. 설명 된 아이디어가있는 기사가 있습니다. 표준 이진 힙에 대한 기능적 접근. 기사의 모든 소스 코드 목록은 Scala입니다. 그러나 다른 기능적 언어로 매우 쉽게 포팅 될 수 있습니다.

다음은 ML 버전의 Heapsort가 포함 된 페이지입니다. 매우 상세하고 좋은 출발점을 제공해야합니다.

http://flint.cs.yale.edu/cs428/coq/doc/reference-manual021.html

라이센스 : CC-BY-SA ~와 함께 속성
제휴하지 않습니다 StackOverflow
scroll top