एक कार्यात्मक प्रोग्रामिंग संदर्भ में अपरिवर्तनीय सूचियों के साथ निरंतर लंबाई प्राप्त करने के लिए निरंतर लंबाई प्राप्त करना

Question

मुझे वर्तमान में किसी दिए गए सूची की लंबाई के आधार पर मेरी गणना करने की समस्या का सामना करना पड़ रहा है। सूची के सभी तत्वों को फिर से शुरू करने के लिए अपने आकार को जानने के लिए एक बड़ा प्रदर्शन जुर्माना है क्योंकि मैं बड़ी सूचियों का उपयोग कर रहा हूं।

समस्या के लिए सुझाए गए दृष्टिकोण क्या हैं?

मुझे लगता है कि मैं हमेशा सूची के साथ एक आकार मूल्य ले सकता हूं, इसलिए मुझे कॉल साइट पर इसकी गणना किए बिना पहले से ही इसका आकार पता है लेकिन यह एक भंगुर दृष्टिकोण लगता है। मैं अपनी खुद की सूची भी परिभाषित कर सकता हूं जहां प्रत्येक नोड में संपत्ति के रूप में सूचियां होती हैं लेकिन फिर मैं मानक प्रोग्रामिंग के लिए अपनी प्रोग्रामिंग भाषा के पुस्तकालयों द्वारा प्रदान किए गए लाभ को खो देता हूं।

आप इसे अपने दैनिक दिनचर्या पर कैसे संभालेंगे?

मैं वर्तमान में एफ # का उपयोग कर रहा हूं। मुझे पता है कि मैं .NET की म्यूटेबल (सरणी) सूचियों का उपयोग कर सकता हूं, जो समस्या को हल करेंगे। मैं पूरी तरह से अपरिवर्तनीय कार्यात्मक दृष्टिकोण में, हालांकि, अधिक रुचि रखते हैं।

Answer 1

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

इस तरह, आप स्पष्ट रूपांतरण से बच सकते हैं - जब आप सूची लपेट, यह वास्तव में इसे कॉपी नहीं होगा (svick के क्रियान्वयन में), लेकिन आवरण आसानी से Length संपत्ति कैश कर सकते:

open System.Collections 

type LengthList<'T>(list:list<'T>) = 
    let length = lazy list.Length 
    member x.Length = length.Value 
    member x.List = list 
    interface IEnumerable with 
    member x.GetEnumerator() = (list :> IEnumerable).GetEnumerator() 
    interface seq<'T> with //' 
    member x.GetEnumerator() = (list :> seq<_>).GetEnumerator() 

[<CompilationRepresentation(CompilationRepresentationFlags.ModuleSuffix)>] 
module LengthList = 
    let ofList l = LengthList<_>(l) 
    let ofSeq s = LengthList<_>(List.ofSeq s) 
    let toList (l:LengthList<_>) = l.List 
    let length (l:LengthList<_>) = l.Length 

रैपर के साथ काम करने का सबसे अच्छा तरीका LengthList.ofList का उपयोग मानक एफ # सूची से LengthList बनाने के लिए और मानक List मॉड्यूल से किसी भी फ़ंक्शन का उपयोग करने से पहले LengthList.toList (या केवल List) संपत्ति का उपयोग करने के लिए करना है।

हालांकि, यह आपके कोड की जटिलता पर निर्भर करता है - यदि आपको केवल कुछ स्थानों में लंबाई की आवश्यकता है, तो इसे अलग से रखना आसान हो सकता है और एक ट्यूपल list<'T> * int का उपयोग करना आसान हो सकता है।

Answer 2

मुझे नहीं लगता कि चारों ओर लंबाई को कैरिंग करना एक भंगुर दृष्टिकोण है। इस तरह कुछ प्रयास करें (हास्केल):

data NList a = NList Int [a] 

nNil :: NList [a] 
nNil = NList 0 [] 

nCons :: a -> NList a -> NList a 
nCons x (NList n xs) = NList (n+1) (x:xs) 

nHead :: NList a -> a 
nHead (NList _ (x:_)) = x 

nTail :: NList a -> NList a 
nTail (NList n (_:xs)) = NList (n-1) xs 

convert :: [a] -> NList a 
convert xs = NList (length xs) xs 

और इसी तरह। यदि यह लाइब्रेरी या मॉड्यूल में है, तो आप कन्स्ट्रक्टर NList निर्यात नहीं करके इसे सुरक्षित (मुझे लगता है) बना सकते हैं।

जीएचसी को length को याद रखने में भी संभव हो सकता है, लेकिन मुझे यकीन नहीं है कि कैसे या कब।

Answer 3

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

type MyList<'T>(item : Option<'T * MyList<'T>>) = 

    let length = 
     match item with 
     | None -> 0 
     | Some (_, tail) -> tail.Length + 1 

    member this.Length = length 

    member private this.sequence = 
     match item with 
     | None -> Seq.empty 
     | Some (x, tail) -> 
      seq { 
       yield x 
       yield! tail.sequence 
      } 

    interface seq<'T> with 
     member this.GetEnumerator() = 
      (this.sequence).GetEnumerator() 
     member this.GetEnumerator() = 
      (this.sequence :> System.Collections.IEnumerable).GetEnumerator() 

module MyList = 
    let rec ofList list = 
     match list with 
     | [] -> MyList None 
     | head::tail -> MyList(Some (head, ofList tail)) 

Answer 4

आप इसे अपने दैनिक दिनचर्या पर कैसे संभालेंगे?

हम नहीं करते हैं, क्योंकि यह दैनिक दिनचर्या में कोई समस्या नहीं है। यह शायद सीमित डोमेन में एक समस्या की तरह लगता है।

यदि आप सूचियों हाल ही में, तो आप शायद पहले से ही हे (एन) काम किया है, तो सूची चलने इसकी लंबाई प्राप्त करने के लिए बनाई गई शायद एक बड़ी बात नहीं है।

आप कुछ बहुत बड़ी सूचियों कि तब नहीं की बदलती 'कर रहे हैं ज्यादा बना रहे हैं (जाहिर है कभी नहीं बदल रहा है, लेकिन मैं सूचियों के प्रमुखों कि आपके डोमेन/एल्गोरिथ्म में उपयोग किया जाता है के लिए संदर्भ के सेट को बदलने मतलब), तो यह अर्थपूर्ण हो सकता है सिर्फ संदर्भ करने वाली सूची सिर * लंबाई tuples के पक्ष के लिए रवाना एक शब्दकोश है, और शब्दकोश से परामर्श जब लंबाई के लिए पूछ (वास्तविक काम कर रही जब जरूरत उन्हें चलने के लिए है, लेकिन भविष्य के लिए कैशिंग परिणामों के बारे में पूछता है एक ही सूची)।

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

(बहुत आम तौर पर, मुझे लगता है कि यह अंतर्निहित डेटा संरचनाओं समय की 99.99% का उपयोग करने के लिए आम तौर पर सबसे अच्छा है। समय जहां एक एल्गोरिथ्म या कोड का सा है कि बहुत होने की जरूरत है विकसित कर रहे हैं 0.01% में अत्यधिक अनुकूलित किया है, तो लगभग हमेशा आप का परित्याग में निर्मित करने के लिए डेटा संरचनाओं (जो काफी ज्यादातर मामलों के लिए अच्छे हैं) और सटीक समस्या आप पर काम कर रहे हल करने के लिए डिज़ाइन किया गया कस्टम डेटा संरचना का उपयोग करें। विकिपीडिया को देखो या Okasaki की '' पूरी तरह कार्यात्मक की जरूरत है विचारों और उस मामले में Inspriation के लिए डेटा सरंचनाएं "। लेकिन शायद ही कभी उस मामले पर जाएं।)