परिचय

हास्केल पर सूची के बारे में हाल ही में एक लेख पढ़ने के बाद, मैंने एफएनपी (एफ #) में बुनियादी संरचनाओं के कार्यान्वयन के बारे में थोड़ी बात करने का भी फैसला किया। लेख व्यावहारिक मूल्य नहीं रखता है, क्योंकि इंटरनेट पर बहुत सारे तैयार किए गए कार्यान्वयन हैं। लेख का उद्देश्य इस बारे में बात करना है कि आप एफ # पर एक अपरिवर्तनीय कतार को कैसे लागू कर सकते हैं और यह कैसे काम करता है।
पहला, कुछ शब्दावली।
F # .NET परिवार की एक प्रोग्रामिंग भाषा है, जो ऑब्जेक्ट-ओरिएंटेड और एप्रोच दृष्टिकोण के अलावा, प्रोग्रामिंग के लिए एक कार्यात्मक दृष्टिकोण को लागू करता है।
अपरिवर्तनीय वस्तुएँ वे वस्तुएँ हैं जिन्हें एक बार बनाने पर, भविष्य में नहीं बदला जा सकता है। उदाहरण के लिए, C # में स्ट्रिंग जैसा डेटा प्रकार होता है, जिसके उदाहरण अपरिवर्तनीय होते हैं। एक स्ट्रिंग में एक चरित्र जोड़ने से, आपको एक नया स्ट्रिंग मिलता है और पुराना एक अपरिवर्तित रहता है। अधिक जानकारी यहाँ ।

एकल रूप से जुड़ी हुई सूची

कतार को लागू करने के लिए, हमें एक एकल लिंक की गई सूची चाहिए। मैं आपको याद दिलाता हूं कि एक एकल लिंक की गई सूची एक ऐसी डेटा संरचना है, जिसके प्रत्येक तत्व में एक संग्रहीत मूल्य और पिछले तत्व का लिंक होता है।
F # पर समान बात:

type public 'a List = //  List  generic- 'a,     | Empty //  | Node of 'a * 'a List //:  -   ("") 

इस प्रविष्टि का मतलब है कि सूची या तो खाली हो सकती है, या "सिर" की एक जोड़ी हो सकती है - "पूंछ", जहां "पूंछ" भी एक सूची है।
सूची के मूल संचालन पर विचार करें और उनकी जटिलता का मूल्यांकन करें।

सूची में आइटम जोड़ें

एक तत्व जोड़ने के लिए और एक ही समय में पुरानी सूची को अपरिवर्तित छोड़ दें, आपको एक नई सूची बनाने की आवश्यकता है, जहां सिर जोड़ा जाने वाला तत्व है, पूंछ पुरानी सूची है। F # पर यह एक पंक्ति में लिखा गया है:

 member this.Cons x = Node(x, this) 

उसके बाद, हमारे पास पहले से ही दो सूचियाँ हैं: मूल और नई। एक ही समय में, दोनों सूचियाँ एक ही मात्रा में मेमोरी पर कब्जा कर लेती हैं क्योंकि एक अंतिम सूची पर कब्जा होगा (नीचे आंकड़ा देखें)।

आइटम में, सूची 1 आइटम जोड़ने से पहले की सूची है, सूची 2 आइटम जोड़ने के बाद की सूची है। इसके अलावा, List1 भी List2 की पूंछ है।
जाहिर है, किसी आइटम को जोड़ने की जटिलता सूची की लंबाई पर निर्भर नहीं करती है और ओ (1) के बराबर है।

किसी सूची से कोई आइटम निकालें

किसी आइटम को फिर से जोड़ना उतना ही आसान है जितना कि जोड़ना। अंतिम जोड़ा तत्व बस "सिर" से लिया गया है; इस तत्व के बिना एक सूची प्राप्त करने के लिए, "पूंछ" लें।

 member this.Head = match this with | Empty -> failwith "Empty stack" | Node(head, tail) -> head member this.Tail = match this with | Empty -> failwith "Empty stack" | Node(head, tail) -> tail 

जाहिर है, इन ऑपरेशनों की जटिलता ओ (1) है।

सूची का प्रसार

एक सूची पर एक और उपयोगी ऑपरेशन एक प्रसार है, अर्थात। आइटम को फिर से व्यवस्थित करना। एक उत्क्रमण के लिए, मूल सूची से तत्वों को क्रमिक रूप से निकालना और उन्हें एक नए स्थान पर रखना आवश्यक है। नई और पुरानी सूचियों में आम डेटा नहीं होगा। जटिलता हमेशा ओ (एन) होगी। नीचे कोड और चित्रण:

 let rec reverse destList sourceList = match sourceList with | Empty -> destList | Node(sourceHead, sourceTail) -> reverse (Node(sourceHead, destList)) sourceTail 

चित्र में, सूची 1 को उलटने से पहले की सूची है, सूची 2 के बाद है।

बारी

स्टैक कार्यान्वयन के लिए ऐड और पुनर्प्राप्त संचालन के साथ एक एकल लिंक की गई सूची आदर्श है। हालाँकि, यदि आप कुछ ऐसी सूचियाँ लेते हैं, तो आप कतार को लागू कर सकते हैं।
तत्वों की पहुंच के सिद्धांत के साथ एक कतार एक डेटा संरचना है "पहले आओ - पहले बाहर आओ" (फीफो)।
कतार को लागू करने के लिए, आपको एक रियर सूची की आवश्यकता होगी जिसमें नए तत्व जोड़े जाते हैं, और एक सामने की सूची जिसमें से तत्व निकाले जाते हैं।

 type 'a Queue (front:'a List, rear: 'a List) = //   Queue    static member Empty = Queue(List.Empty, List.Empty) //   -    

किसी आइटम को कतार में जोड़ना

एक आइटम को कतार में जोड़ना बैक सूची में एक आइटम जोड़ रहा है, या बल्कि, एक नई कतार बना रहा है, जहां सामने की सूची समान है और एक नई आइटम जोड़कर पीछे की सूची प्राप्त की जाती है:

  member this.Snoc value = Queue(front, rear.Cons value) 

जाहिर है, कतार में एक तत्व जोड़ने की कठिनाई का आकलन एक एकल लिंक की गई सूची में एक तत्व को जोड़ने की जटिलता के मूल्यांकन के साथ मेल खाता है - ओ (1)।

किसी पंक्ति से कोई आइटम पुनर्प्राप्त करना

ललाट सूची से एक आइटम निकालने से पहले, हम यह देखने के लिए जांचते हैं कि क्या यह खाली है। यदि यह खाली है, तो पीछे ले जाएं और इसे विस्तारित करें - अब यह ललाट है, और पीछे एक खाली सूची असाइन करें। सबसे खराब स्थिति जटिलता ओ (एन) सूची रोल की जटिलता के बराबर है।

  let frontToBack = match front, rear with |Empty, rear -> (rear.Reverse, Empty) |x -> (x) member this.Head = match frontToBack with | Empty, _ -> failwith "Empty or not reversed" | List.Node(a, __), _ -> a member this.Tail = match frontToBack with |Empty, _ -> failwith "Empty" |List.Node(a, tail), r -> Queue(tail, r) 

निम्नलिखित कतारों के "जीवन" का एक चित्रण है, जो जोड़ और निष्कर्षण के संचालन के क्रमिक निष्पादन को दर्शाता है।

चार पंक्तियों को योजनाबद्ध रूप से चित्र में दिखाया गया है: A एक खाली कतार है, B एक पंक्ति है क्रमिक रूप से संख्या 1, 2, 3 और 4 को जोड़ने के बाद, C एक तत्व (नंबर 1) निकालने के बाद एक कतार है, संख्या 5 को जोड़ने के बाद G एक कतार है।

निष्कर्ष

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

साहित्य का इस्तेमाल किया

क्रिस ओकासाकी की पुस्तक "विशुद्ध रूप से कार्यात्मक डेटा संरचनाएं" का उपयोग सूचना के मुख्य स्रोत के रूप में किया गया था।