मैं OCaml में दो सूचियों कैसे एक दूसरे को काटना करते हैं?

Question

मैं OCaml में दो सूचियों, उदाहरण के लिए जब

e1 = [3; 4; 5; 6; 7] 

और

e2 = [1; 3; 5; 7; 9] 

वहाँ एक कारगर तरीका उन दो सूचियों के चौराहे प्राप्त करने के लिए है? यानी .:

[3; 5; 7] 

क्योंकि मैं सूची E1 में प्रत्येक तत्व के लिए सूची e2 में हर तत्व को स्कैन, इस प्रकार क्रम का एक बड़ा ओह n^2 बनाने पसंद नहीं है।

Answer 1

फ़्रैंक और Rémi के रूप में कहा, (stdlib मॉड्यूल सेट से) सेट करने के लिए अपनी सूची को परिवर्तित करने के लिए लॉग इन n लागत (एन), और फिर सेट करता है चौराहे के एक रेखीय कार्यान्वयन प्रदान करता है। फ्रैंक ने सूचियों को क्रमबद्ध करने के बराबर विकल्प का भी उल्लेख किया, और फिर उन्हें एक सिंक्रनाइज़ तरीके से पार किया। ये लगभग एक ही कर रहे हैं (और वैसे, दोनों ही मामलों में आप अपनी सूची में तत्वों पर कुल आदेश प्रदान करने में सक्षम होने की जरूरत है)।

चौराहों अपने एल्गोरिथ्म के एक महत्वपूर्ण हिस्सा हैं और आप उन्हें तेजी से तत्व हैं जो केवल थोड़े अलग हैं के दो सेट के मामले में होना चाहते हैं, तो आप इस तरह के पेट्रीसिया पेड़ के रूप में एक एकत्रित करने लायक संरचना करने के लिए स्विच करना होगा। फ़ाइलों http://www.lri.fr/~filliatr/ftp/ocaml/ds/ में pt* देखें।

यदि आपको सभी मामलों में तेजी से छेड़छाड़ की आवश्यकता है, तो आपके पास हैश-युक्त पेट्रीसिया पेड़ का उपयोग करने की संभावना है। हैश-consing संरचना की दृष्टि से समान उप पेड़ समझते हैं, और तुलना सस्ता बनाकर पिछले कार्यों के लिए कुशल कैश निर्माण करने के लिए मदद करने के लिए मदद करता है।

पेट्रीसिया पेड़ एक मनमाने ढंग से कुंजी के रूप में उपयोग नहीं कर सकते हैं (आमतौर पर उन्हें चाबियों के रूप में इन्स के साथ प्रस्तुत किया जाता है)। लेकिन आप कभी कभी निर्माण में प्रत्येक मान आप एक कुंजी के रूप में उपयोग करने का इरादा नंबर से इस सीमा के आसपास काम कर सकते हैं।

Answer 2

मैं OCaml (सिंटेक्स वार) पता नहीं है, लेकिन आम तौर पर आप दो तरह से कर सकते हैं:

1. अपनी भाषा एक सेट आंकड़ा संरचना के लिए समर्थन है, तो दोनों सूचियों सेट में तब्दील और सेट-चौराहे ऑपरेशन का उपयोग करें।

2. अधिक आम तौर पर: दोनों सूचियों पर क्रमबद्ध, तो क्रमबद्ध सूचियों स्कैन करते हैं, जो अधिक कुशल डुप्लिकेट खोजने में आता है। आप सॉर्टिंग के लिए एन लॉग (एन) लेते हैं और फिर रैखिक समय में डुप्लिकेट पा सकते हैं।

Answer 3

मेरे OCaml सबसे अच्छा नहीं है, लेकिन मैं इस समारोह एक साथ जो हल कर सूचियों काटना होगा काट दिया:

let rec intersect l1 l2 = 
    match l1 with [] -> [] 
     | h1::t1 -> (
      match l2 with [] -> [] 
       | h2::t2 when h1 < h2 -> intersect t1 l2 
       | h2::t2 when h1 > h2 -> intersect l1 t2 
       | h2::t2 -> (
       match intersect t1 t2 with [] -> [h1] 
        | h3::t3 as l when h3 = h1 -> l 
        | h3::t3 as l -> h1::l 
      ) 
     );; 

जो (n + m) समय हे में चलाने चाहिए। असल में यह प्रत्येक सूची का पहला तत्व जांचता है। यदि वे बराबर हैं, तो यह रिकर्सिव कॉल का परिणाम उनकी पूंछ में संग्रहीत करता है, और फिर यह देखने के लिए जांच करता है कि संग्रहित परिणाम का सिर सूचियों के प्रमुखों के बराबर है या नहीं। यदि ऐसा नहीं है, तो यह इसे सम्मिलित करता है, अन्यथा यह एक डुप्लिकेट है और यह इसे अनदेखा करता है।

यदि वे बराबर नहीं हैं, तो यह केवल आगे बढ़ता है जो भी छोटा होता है।

Answer 4

रूप @Frank सुझाव दिया है, तो आप इस समस्या को हल करने के लिए सेट का उपयोग कर सकते हैं, हालांकि यह सबसे अच्छा जवाब कभी नहीं है, लेकिन यहां एक शॉर्ट कोड लिस्टिंग का प्रदर्शन यह कैसे OCaml में प्राप्त किया जा सकता है:

module Int_set = Set.Make (struct 
          type t = int 
          let compare = compare 
          end);; 

(* iters through a list to construct a set*) 
let set_of_list = List.fold_left (fun acc x -> Int_set.add x acc) Int_set.empty;; 

let e1 = [3; 4; 5; 6; 7];; 
let e2 = [1; 3; 5; 7; 9];; 

let s1 = set_of_list e1;; 
let s2 = set_of_list e2;; 

(*result*) 
let s3 = Int_set.inter s1 s2;; 


(*testing output*) 
Int_set.iter (fun elt -> print_int elt;print_string "\n") s3;; 

उत्पादन होता है:

1.) y के आकार के बूलियन्स की एक सरणी बनाएँ:

3 
5 
7 
- : unit =() 

Answer 5

अपनी सूची केवल एक सीमित आकार के पूर्णांक है, तो उसके भी हे में एक समाधान (एन) है आपकी मूल सूचियों में कहां सबसे बड़ा पूर्णांक मान प्लस 1 (उदा। आपके उदाहरण में '9 + 1'); सभी क्षेत्रों को झूठ में सेट करें;

let m = Array.create 10 false

->[|false; false; false; false; false; false; false; false; false; false|]

2.) दोहराएं पहली सूची से अधिक: हर तत्व आपके सामने आने वाली के लिए, बूलियन संबंधित 'सही' के लिए ऑफसेट के साथ सेट; अपने उदाहरण में यह लाभ होगा

List.iter (fun x -> m.(x) <- true) e1

->[|false; false; false; true; true; true; true; true; false; false|]

3.) दूसरी सूची से अधिक फिल्टर, केवल उन तत्वों रखते हुए जिनमें से सरणी में संगत फ़ील्ड सच है

List.filter (fun x -> m.(x) = true) e2

->[3; 5; 7]