並べ替えられていないシーケンス内の重複を効率的に見つける

Question

並べ替えられていないシーケンスで重複を見つけるには非常に効率的な方法が必要です。これは私が思い付いたものですが、それはいくつかの欠点、すなわちそれ

1. が不必要に
2. が
3. 作成し、いくつかの中間シーケンス得重複する前に、シーケンス全体を消費2を超えて発生をカウントしてい

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

理由にかかわらず、私は理由を見ませんこれを2倍のコードに置き換えます。これを比較的簡潔なコードで改善することは可能でしょうか？あなたの順序を想定し

Answer 1

をここで（少し長い確かである）が不可欠ソリューションです：

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 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の容量として、シーケンスの長さを提供することができますが、それはもう一度全体のシーケンスを列挙することが必要です。

EDIT： 第二の問題を解決するには、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 3

機能ソリューション：

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 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を使用して、前に見た要素のセット、つまり重複している要素に含まれる要素を除外します。

EDIT

実は私のオリジナルの答えは完全に間違っていました。まず、出力に重複を必要としません。第二に、パフォーマンスが必要です。ここで

はあなたが後にしているアルゴリズムを実装して、純粋に機能的なソリューションです：

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) 

これは、各要素が一回または多数回の前に見て、それならば要素を発してきたかどうかを追跡するためにマップを使用しています以前に一度だけ見られた、すなわちそれが初めて複製されたことが見られる。これはあなたの他の回答（執筆時）のいずれよりも約2 ×高速である

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 } 

：ここ

は速い不可欠バージョンです。シーケンス内の要素を列挙するfor x in xs doループを使用し

は直接GetEnumeratorを使用するよりも実質的に遅いですが、あなた自身のEnumeratorを生成することyieldで計算式を使用するよりもはるかに高速ではありません。 DictionaryのTryGetValueメンバーは、私は（彼/彼女の答えでKVBにより、使用）のF＃が提供するTryGetValue延長部材は、その戻りタプルを割り振るのに対し、スタックに割り当てられた値を変異させることにより、内側のループで割り当てが行われないようにする

注意。