Skutecznie odnajduj duplikaty w niesortowanej sekwencji

Question

Potrzebuję bardzo skutecznego sposobu na znalezienie duplikatów w niesortowanej sekwencji. To jest to, co wymyśliłem, ale ma kilka wad, a mianowicie to

1. niepotrzebnie zlicza wystąpienia poza 2
2. zużywa całą sekwencję przed plonach duplikatów
3. tworzy kilka sekwencji pośrednich

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

Niezależnie od wad, nie widzę powodu, aby zastąpić to dwukrotnym kodem. Czy można to poprawić za pomocą porównywalnie zwięzłego kodu?

Answer 1

Oto imperatywem rozwiązanie (które jest wprawdzie nieco dłużej):

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

Zakładając, że sekwencja jest skończony, to rozwiązanie wymaga jednego biegu na sekwencji:

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 

można podać długość sekwencji jako zdolność Dictionary, ale wymaga, aby wyliczyć całą sekwencję jeszcze raz.

EDIT: Aby rozwiązać 2nd problemu, można wygenerować duplikaty na żądanie:

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

rozwiązanie funkcjonalne:

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

To najlepsze "funkcjonalne" rozwiązanie, które wymyśliłem, nie pochłania całej sekwencji z góry.

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

Bardziej eleganckie rozwiązanie funkcjonalne:

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) 

Używa scan gromadzić zbiory wszystkich elementów widział do tej pory. Następnie używa zip do łączenia każdego elementu z zestawem elementów przed nim. Wreszcie, używa choose do odfiltrowania elementów, które są w zestawie wcześniej widzianych elementów, tj. Duplikatów.

EDIT

Właściwie mój oryginalny odpowiedź była całkowicie błędne. Po pierwsze, nie chcesz duplikatów na wyjściach. Po drugie, chcesz wydajności.

Oto czysto funkcjonalne rozwiązanie, które implementuje algorytm jesteś po:

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) 

ta wykorzystuje mapy, aby śledzić, czy każdy element został widział raz lub wiele razy, a następnie emituje element, jeśli to widać, że był widziany tylko raz, tj. po raz pierwszy jest duplikowany.

Oto szybciej imperatyw wersja:

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 } 

Jest to około 2 × szybciej niż którykolwiek z pozostałych odpowiedzi (w chwili pisania tego tekstu).

Stosując for x in xs do pętli wyliczyć elementy sekwencji jest znacznie wolniejsza niż przy GetEnumerator bezpośrednio, lecz generuje własny Enumerator jest znacznie szybciej niż przy użyciu wyrażenia obliczeń z yield.

Należy zauważyć, że członkiem DictionaryTryGetValue pozwala mi uniknąć przydziały w wewnętrznej pętli przez mutację wartość stosu przeznaczono natomiast członek TryGetValue rozszerzenie oferowanych przez F # (i wykorzystywane przez KVB w jego/jej odpowiedzi) przydziela jej krotka powrotną.