एक अनुक्रमित अनुक्रम में डुप्लीकेट को कुशलतापूर्वक

Question

ढूंढें मुझे एक अनुक्रमित अनुक्रम में डुप्लीकेट खोजने के लिए एक बहुत ही कुशल तरीका चाहिए। यह क्या मैं के साथ आया है, लेकिन यह कुछ कमियों, अर्थात् यह

1. अनावश्यक रूप से परे 2
2. उपज डुप्लिकेट से पहले
3. बनाता कई मध्यवर्ती दृश्यों पूरा अनुक्रम की खपत घटनाओं में गिना जाता है है

module Seq = 
    let duplicates items = 
    items 
    |> Seq.countBy id 
    |> Seq.filter (snd >> ((<) 1)) 
    |> Seq.map fst 

कमियों के बावजूद, मुझे कोई कारण नहीं दिख रहा है दो बार कोड के साथ इसे बदलने के लिए। तुलनात्मक रूप से संक्षेप कोड के साथ इसे सुधारना संभव है?

Answer 1

यहाँ एक अनिवार्य समाधान (जो बेशक थोड़ा लंबा है):

let duplicates items = 
    seq { 
     let d = System.Collections.Generic.Dictionary() 
     for i in items do 
      match d.TryGetValue(i) with 
      | false,_ -> d.[i] <- false   // first observance 
      | true,false -> d.[i] <- true; yield i // second observance 
      | true,true ->()      // already seen at least twice 
    } 

Answer 2

मान लिया जाये कि अपने अनुक्रम परिमित है, इस समाधान क्रम पर एक रन की आवश्यकता है:

open System.Collections.Generic 
let duplicates items = 
    let dict = Dictionary() 
    items |> Seq.fold (fun acc item -> 
          match dict.TryGetValue item with 
          | true, 2 -> acc 
          | true, 1 -> dict.[item] <- 2; item::acc 
          | _ -> dict.[item] <- 1; acc) [] 
     |> List.rev 

आप Dictionary की क्षमता के रूप में अनुक्रम की लंबाई प्रदान कर सकते हैं, लेकिन यह पूरे अनुक्रम एक बार फिर की गणना करने की आवश्यकता है।

संपादित करें: 2 समस्या को हल करने से एक मांग पर डुप्लिकेट उत्पन्न कर सकता है:

open System.Collections.Generic 
let duplicates items = 
    seq { 
     let dict = Dictionary() 
     for item in items do 
      match dict.TryGetValue item with 
      | true, 2 ->() 
      | true, 1 -> dict.[item] <- 2; yield item 
      | _ -> dict.[item] <- 1 
    } 

Answer 3

कार्यात्मक समाधान:

let duplicates items = 
    let test (unique, result) v = 
    if not(unique |> Set.contains v) then (unique |> Set.add v ,result) 
    elif not(result |> Set.contains v) then (unique,result |> Set.add v) 
    else (unique, result) 
    items |> Seq.fold test (Set.empty, Set.empty) |> snd |> Set.toSeq 

Answer 4

यह सबसे अच्छा "कार्यात्मक" समाधान है जिसके साथ मैं आ सकता हूं जो पूरे अनुक्रम को सामने नहीं लेता है।

let duplicates = 
    Seq.scan (fun (out, yielded:Set<_>, seen:Set<_>) item -> 
     if yielded.Contains item then 
      (None, yielded, seen) 
     else 
      if seen.Contains item then 
       (Some(item), yielded.Add item, seen.Remove item) 
      else 
       (None, yielded, seen.Add item) 
    ) (None, Set.empty, Set.empty) 
    >> Seq.Choose (fun (x,_,_) -> x) 

Answer 5

एक और अधिक सुरुचिपूर्ण कार्यात्मक समाधान:

let duplicates xs = 
    Seq.scan (fun xs x -> Set.add x xs) Set.empty xs 
    |> Seq.zip xs 
    |> Seq.choose (fun (x, xs) -> if Set.contains x xs then Some x else None) 

का उपयोग करता है scan अब तक देखा सभी तत्वों के सेट जमा करने के लिए। इसके बाद तत्वों के सेट के साथ प्रत्येक तत्व को गठबंधन करने के लिए zip का उपयोग करता है। अंत में, choose का उपयोग पहले से देखे गए तत्वों के सेट में मौजूद तत्वों को फ़िल्टर करने के लिए करता है, यानी डुप्लिकेट।

संपादित

असल में मेरी मूल जवाब पूरी तरह से गलत था। सबसे पहले, आप अपने आउटपुट में डुप्लीकेट नहीं चाहते हैं। दूसरा, आप प्रदर्शन चाहते हैं।

यहाँ एक पूरी तरह कार्यात्मक समाधान है कि एल्गोरिथ्म आप के बाद कर रहे हैं लागू करता है:

let duplicates xs = 
    (Map.empty, xs) 
    ||> Seq.scan (fun xs x -> 
     match Map.tryFind x xs with 
     | None -> Map.add x false xs 
     | Some false -> Map.add x true xs 
     | Some true -> xs) 
    |> Seq.zip xs 
    |> Seq.choose (fun (x, xs) -> 
     match Map.tryFind x xs with 
     | Some false -> Some x 
     | None | Some true -> None) 

यह ट्रैक करने के लिए है कि क्या प्रत्येक तत्व से पहले एक या कई बार देखा गया है किसी मैप का उपयोग करता है और उसके बाद ही वह तत्व का उत्सर्जन करता है देखा जाता है कि केवल एक बार पहले देखा जा रहा था, यानी पहली बार इसे डुप्लिकेट किया गया है।

let duplicates (xs: _ seq) = 
    seq { let d = System.Collections.Generic.Dictionary(HashIdentity.Structural) 
     let e = xs.GetEnumerator() 
     while e.MoveNext() do 
      let x = e.Current 
      let mutable seen = false 
      if d.TryGetValue(x, &seen) then 
      if not seen then 
       d.[x] <- true 
       yield x 
      else 
      d.[x] <- false } 

यह आपके अन्य उत्तर में से किसी की तुलना में तेजी लगभग 2 × (लेखन के समय) है:

यहाँ एक तेजी से जरूरी संस्करण है।

एक क्रम में तत्वों की गणना करने में एक for x in xs do पाश का उपयोग करना GetEnumerator सीधे का उपयोग कर, लेकिन पैदा अपनी खुद की Enumerator काफी yield के साथ एक गणना अभिव्यक्ति का उपयोग कर की तुलना में तेजी नहीं है की तुलना में काफी धीमी है।

ध्यान दें कि Dictionary की TryGetValue सदस्य मुझे एक ढेर आवंटित मूल्य परिवर्तनशील जबकि TryGetValue विस्तार सदस्य (उसकी/उसके जवाब में KVB द्वारा और प्रयोग किया जाता) एफ # द्वारा की पेशकश की अपनी वापसी टपल आवंटित द्वारा भीतरी पाश में आवंटन से बचने के लिए अनुमति देता है।