हास्केल

Question

में प्राथमिकता कतार कार्यान्वयन की तुलना हास्केल के लिए ऑफ-द-शेल्फ उपलब्ध कई प्राथमिकता कतार कार्यान्वयन प्रतीत होती है। उदाहरण के लिए, वहाँ है:

(hackage पर pure-priority-queue-0.14 में) Data.PriorityQueue.FingerTree

Data.PurePriorityQueue (hackage पर fingertree-0.0.1.0 में) जो दोनों के शुद्ध प्राथमिकता कतार डेटा प्रतीत संरचनाओं। पूर्व उंगली के पेड़ों पर आधारित है, एक डेटा संरचना जिसके साथ मैं अपरिचित हूं; उत्तरार्द्ध Data.Map के चारों ओर एक रैपर है।

• (hackage पर heap-1.0.0 में) Data.Heap

जो जहाँ से एक तुच्छता प्राथमिकता कतारों कर सकते हैं पूरी तरह कार्यात्मक ढेर डाटा संरचनाओं को परिभाषित करता है भी नहीं है। । वहाँ भी

• Data.Heap
• Data.MeldableHeap (hackage पर heaps-0.2 में) (hackage पर meldable-heap-2.0.3 में) कर रहे हैं

जो दोनों Brodal/Okasaki डेटा का उपयोग कर पूरी तरह कार्यात्मक meldable ढेर लागू संरचना, जो मुझे विश्वास है कि गैर-शुद्ध कार्यात्मक भूमि में द्विपदीय ढेर डेटा संरचना के समान है।

(ओह, और वहाँ भी है

• Data.PriorityQueue (hackage पर प्राथमिकता-पंक्ति-0.2.2) में

समारोह जिसका मेरे लिए स्पष्ट नहीं है, लेकिन जो संबंधित प्रतीत हो रहा है एक मोनैड से जुड़ी प्राथमिकता कतारों का निर्माण, और जो किसी भी तरह से डेटा.मैप के शीर्ष पर बनाया गया प्रतीत होता है। इस सवाल में, मैं पूरी तरह कार्यात्मक प्राथमिकता कतारों से चिंतित हूं, इसलिए मुझे लगता है कि प्राथमिकता-कतार-0.2.2 पैकेज अप्रासंगिक है लेकिन अगर मैं गलत हूं तो मुझे सही करें!)

मुझे एक परियोजना के लिए एक शुद्ध कार्यात्मक प्राथमिकता कतार डेटा संरचना की आवश्यकता है जिसे मैं बना रहा हूं। मैं सोच रहा था कि कोई भी ज्ञान के किसी भी शब्द प्रदान कर सकता है क्योंकि मैं हैकेज द्वारा प्रदत्त embarrassment of riches के बीच निर्णय लेता हूं। विशेष रूप से:

1. मान लीजिए कि मैं परंपरागत प्राथमिकता कतार सम्मिलन और निकालने-न्यूनतम संचालन के अलावा पूरी तरह से कार्यात्मक/अपरिवर्तनीय प्रस्तुति के अलावा सुविधाओं को अलग करना चाहता हूं। ऊपर वर्णित संकुल के पेशेवरों और विपक्ष क्या हैं? क्या किसी को भी 'क्रोध में' उनमें से किसी का उपयोग करने का अनुभव है? प्रदर्शन में ट्रेडऑफ क्या हैं? विश्वसनीयता? दूसरों द्वारा अधिक व्यापक रूप से उपयोग किया जाता है? (उन लोगों का उपयोग करना मेरे कोड को दूसरों के पढ़ने के लिए आसान बना सकता है, क्योंकि वे लाइब्रेरी से परिचित होने की अधिक संभावना रखते हैं।) क्या उनके बीच कोई निर्णय लेने से पहले मुझे कोई और चीज जाननी चाहिए?
2. यदि मैं भी प्राथमिकता कतारों के कुशल विलय करना चाहता हूं, तो फिर क्या? (मैं इस परियोजना के लिए नहीं हूं, लेकिन मैंने इसे जोड़ने का विचार किया लेकिन एसओ प्रश्न भविष्य के पाठकों के लिए अधिक उपयोगी बना देगा।)
3. क्या वहां कोई अन्य प्राथमिकता कतार पैकेज है जो मुझे याद आया?

Answer 1

वहाँ प्राथमिकता कतार कार्यान्वयन की बहुतायत hackage पर पाया जा सकता है, बस अपनी सूची को पूरा करने के:

• 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 में विशेष रूप से अच्छा इंटरफ़ेस है। मुझे लगता है कि यह पहले कार्यान्वयन में से एक था और राल्फ हिनज द्वारा this paper में अच्छी तरह से कवर किया गया है। यह सबसे कुशल और पूर्ण कार्यान्वयन नहीं हो सकता है लेकिन अब तक यह मेरी सभी आवश्यकताओं को पूरा करता है।

लुइस वासरमेन द्वारा मोनैड रीडर (issue 16) में एक बहुत अच्छा लेख है (जिसने pqueue पैकेज भी लिखा था)। अपने लेख में लुई विभिन्न प्राथमिकता कतार कार्यान्वयन प्रदान करता है और प्रत्येक के लिए एल्गोरिदमिक जटिलताओं को भी शामिल करता है।
कुछ प्राथमिकता कतार आंतरिक की सादगी के एक आकर्षक उदाहरण के रूप में उनमें कुछ शांत छोटे कार्यान्वयन शामिल हैं। मेरा पसंदीदा एक (अपने लेख से लिया गया):

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] 

प्राथमिकता कतार कार्यान्वयन के कुछ मानक here पाया जा सकता है और एक नहीं बल्कि दिलचस्प में thread haskell.org here पर।