Haskell의 Priority Queue 구현 비교

Haskell의 Priority Queue 구현 비교

---

Haskell에 대해 기성품으로 사용할 수있는 몇 가지 우선 순위 큐 구현이있는 것 같습니다. 예를 들어 다음이 있습니다.

• Data.PriorityQueue.FingerTree (해 키지의 fingertree- 0.0.1.0)
• Data.PurePriorityQueue (해 키지의 pure-priority-queue-0.14 )

둘 다 순수한 우선 순위 큐 데이터 구조 인 것처럼 보입니다. 전자는 제가 익숙하지 않은 데이터 구조 인 핑거 트리를 기반으로합니다. 후자는 Data.Map을 둘러싼 래퍼입니다. 또한

• Data.Heap (해 키지의 힙 -1.0.0)

순전히 기능적인 힙 데이터 구조를 정의하여 사소하게 우선 순위 큐를 만들 수 있습니다. . 또한

• Data.Heap (해 키지의 힙 -0.2)
• Data.MeldableHeap (해 키지의 meldable-heap-2.0.3 )

둘 다 Brodal / Okasaki 데이터 구조를 사용하여 순전히 기능적인 혼합 가능한 힙을 구현합니다. 이것은 비 순수 기능 영역의 이항 힙 데이터 구조와 유사하다고 생각합니다.

(오, 그리고

• Data.PriorityQueue (해 키지의 priority-queue-0.2.2)

그 기능은 나에게 명확하지 않지만 모나드에 연결된 우선 순위 대기열을 구축하는 것과 관련된 것으로 보이며 어쨌든 Data.Map 위에 구축 된 것처럼 보입니다. 이 질문에서는 순전히 기능적인 우선 순위 대기열에 관심이 있으므로 priority-queue-0.2.2 패키지는 관련이 없다고 생각합니다. 그러나 내가 틀렸다면 나를 고쳐주세요!)

내가 구축중인 프로젝트에 대한 순수한 기능 우선 순위 대기열 데이터 구조가 필요합니다. 해킹이 제공하는 부의 부끄러움 사이에서 내가 결정할 때 지혜의 말을 해줄 수있는 사람이 있는지 궁금 했다. 구체적으로 특별히:

1. 순전히 기능적이고 변경 불가능한 프레젠테이션에서 기존의 우선 순위 대기열 삽입 및 추출 분 작업과는 별도로 기능을 수행한다고 가정합니다. 위에서 언급 한 패키지의 장단점은 무엇입니까? 누구든지 '분노'를 사용한 경험이 있습니까? 성능의 장단점은 무엇입니까? 신뢰할 수 있음? 다른 사람들이 더 널리 사용하는 것은 무엇입니까? (이것을 사용하면 다른 사람들이 내 코드를 더 쉽게 읽을 수 있습니다. 라이브러리에 더 익숙해지기 때문입니다.) 결정을 내리기 전에 알아야 할 다른 사항이 있습니까?
2. 우선 순위 대기열을 효율적으로 병합하려면 어떻게해야합니까? (나는이 프로젝트를위한 것이 아니지만 이것을 추가 할 것이라고 생각했지만 미래의 독자들에게 SO 질문을 더 유용하게 만들 것입니다.)
3. 내가 놓친 다른 우선 순위 대기열 패키지가 있습니까?

---

목록을 완성하기 위해 해킹에서 찾을 수있는 우선 순위 대기열 구현이 풍부합니다.

• http://hackage.haskell.org/package/PSQueue
• http://hackage.haskell.org/package/pqueue
• http://hackage.haskell.org/package/queuelike
• http://hackage.haskell.org/package/priority-queue
• http://hackage.haskell.org/package/pure-priority-queue
• http://hackage.haskell.org/package/fingertree-psqueue

그중 PSQueue에는 특히 멋진 인터페이스가 있다는 것을 알았습니다. 나는 이것이 첫 번째 구현 중 하나였으며 Ralf Hinze 가이 문서 에서 잘 다루었다고 생각합니다 . 가장 효율적이고 완전한 구현은 아니지만 지금까지 모든 요구 사항을 충족했습니다.

MonadReader ( 16 호 )에는 Louis Wassermann ( pqueue 패키지 도 작성했습니다) 의 매우 좋은 기사가 있습니다. 그의 기사에서 Louis는 다양한 우선 순위 대기열 구현을 제공하고 각각에 대한 알고리즘 복잡성도 포함합니다.
일부 우선 순위 대기열 내부의 단순성에 대한 놀라운 예로서 그는 약간의 멋진 구현을 포함합니다. 내가 가장 좋아하는 것 (그의 기사에서 발췌) :

data SkewHeap a = Empty | SkewNode a (SkewHeap a) (SkewHeap a) deriving (Show)

(+++) :: Ord a => SkewHeap a -> SkewHeap a -> SkewHeap a
heap1@(SkewNode x1 l1 r1) +++ heap2@(SkewNode x2 l2 r2) 
  | x1 <= x2    = SkewNode x1 (heap2 +++ r1) l1 
  | otherwise = SkewNode x2 (heap1 +++ r2) l2
Empty +++ heap = heap
heap +++ Empty = heap

extractMin Empty = Nothing
extractMin (SkewNode x l r ) = Just (x , l +++ r )

멋진 작은 구현 ... 짧은 사용 예 :

test = foldl (\acc x->acc +++ x) Empty nodes
  where nodes = map (\x-> SkewNode x Empty Empty) [3,5,1,9,7,2]

우선 순위 대기열 구현의 일부 벤치 마크는 여기 와 haskell.org의 흥미로운 스레드 에서 찾을 수 있습니다 .

참조 URL : https://stackoverflow.com/questions/6976559/comparison-of-priority-queue-implementations-in-haskell