Trova duplicati in una sequenza non ordinata in modo efficiente

Question

Ho bisogno di un modo molto efficiente per trovare i duplicati in una sequenza non ordinata. Questo è ciò che mi è venuta, ma ha un paio di difetti, vale a dire che

1. conta inutilmente occorrenze oltre 2
2. consuma l'intera sequenza prima duplicati rendimento
3. crea diverse sequenze intermedie

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

Indipendentemente delle carenze, non vedo una ragione per sostituire questo con il doppio del codice. È possibile migliorare questo con codice relativamente conciso?

Answer 1

Ecco una soluzione imperativa (che è certamente un po 'più lungo):

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

Assumendo la sequenza è finita, questa soluzione richiede una corsa sulla sequenza:

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 

È possibile fornire la lunghezza della sequenza, come la capacità di Dictionary, ma richiede per enumerare l'intera sequenza una volta di più.

EDIT: Per risolvere secondo problema, si potrebbe generare duplicati su richiesta:

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

soluzione funzionale:

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

Questa è la migliore soluzione "funzionale" che potrei immaginare che non consumi l'intera sequenza in anticipo.

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

Una soluzione più elegante funzionale:

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) 

Utilizza scan di accumulare insiemi di tutti gli elementi visti finora. Quindi usa zip per combinare ogni elemento con il set di elementi prima di esso. Infine, utilizza choose per filtrare gli elementi presenti nel set di elementi precedentemente visti, ovvero i duplicati.

EDIT

In realtà la mia risposta originale era completamente sbagliato. In primo luogo, non vuoi duplicati nelle tue uscite. In secondo luogo, vuoi le prestazioni.

Ecco una soluzione puramente funzionale che implementa l'algoritmo che stai dopo:

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) 

Questo utilizza una mappa per monitorare se ogni elemento è stato visto prima una o più volte e poi emette l'elemento se è visto essere visto solo una volta, cioè la prima volta che viene duplicato.

Ecco una versione più veloce imperativo:

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 } 

Si tratta di circa 2 × più veloce di tutti gli altri tuoi risposte (al momento della scrittura).

Utilizzando un'ansa for x in xs do per enumerare gli elementi di una sequenza è sostanzialmente più lento rispetto all'utilizzo GetEnumerator direttamente ma si genera un Enumerator non è significativamente più veloce rispetto all'utilizzo un'espressione calcolo con yield.

noti che la TryGetValue membro di Dictionary mi permette di evitare assegnazione nel ciclo interno mutando un valore pila allocato che l'organo TryGetValue estensione offerta da F # (e utilizzato da KVB nel suo/sua risposta) alloca sua tupla ritorno.