有效查找未排序序列中的重複項

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容量的長度，但它需要枚舉整個序列一次。

編輯： 要解決第二個問題，我們可以根據需要生成重複：

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成員讓我通過突變堆棧分配的值，而通過F＃提供的（並用在他/她的回答KVB）的TryGetValue擴展成員分配其返回的元組，以避免在內部循環分配。