Finde Duplikate in einer unsortierten Sequenz effizient

Question

Ich brauche eine sehr effiziente Möglichkeit, Duplikate in einer unsortierten Sequenz zu finden. Das ist, was ich herausgefunden habe, aber es hat einige Mängel, nämlich

1. zählt unnötigerweise Vorkommen über 2 hinaus
2. verbraucht die gesamte Sequenz, bevor Duplikate ausgegeben werden

3. erstellt mehrere Zwischensequenzen

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

Trotz der Mängel sehe ich keinen Grund, dies durch doppelt so viel Code zu ersetzen. Ist es möglich, dies mit vergleichsweise knappem Code zu verbessern?

Answer 1

Eine elegantere funktionale Lösung:

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)

Verwendet scan, um Sets aller bisher gesehenen Elemente zu akkumulieren. Verwendet dann zip, um jedes Element mit dem Satz von Elementen vor ihm zu kombinieren. Schließlich verwendet choose, um die Elemente herauszufiltern, die im Satz der zuvor gesehenen Elemente enthalten sind, d.h. die Duplikate.

BEARBEITEN

Eigentlich war meine ursprüngliche Antwort völlig falsch. Erstens möchten Sie keine Duplikate in Ihren Ausgaben haben. Zweitens möchten Sie Leistung.

Hier ist eine rein funktionale Lösung, die den von Ihnen gewünschten Algorithmus implementiert:

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)

Das verwendet eine Map, um zu verfolgen, ob jedes Element schon einmal gesehen wurde, einmal oder mehrmals, und gibt dann das Element aus, wenn es gesehen wird und vorher nur einmal gesehen wurde, d.h. das erste Mal, dass es dupliziert wird.

Hier ist eine schnellere imperativ Lösung:

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 }

Dies ist etwa 2× schneller als alle anderen Antworten (zum Zeitpunkt des Schreibens).

Die Verwendung einer for x in xs do-Schleife zur Aufzählung der Elemente in einer Sequenz ist wesentlich langsamer als die Verwendung von GetEnumerator direkt, aber die Erstellung des eigenen Enumerator ist nicht signifikant schneller als die Verwendung eines Ausdrucks mit yield.

Beachten Sie, dass das TryGetValue-Element der Dictionary mir ermöglicht, in der Innen Schleife eine Zuweisung an einen stapelallokierten Wert zu vermeiden, während das von F# angebotene TryGetValue-Erweiterungselement (von kvb in seiner Antwort verwendet) sein Rückgabetupel alloziert.

Answer 2

Hier ist eine imperative Lösung (die zugegebenermaßen etwas länger ist):

let duplicates items =
    seq {
        let d = System.Collections.Generic.Dictionary()
        for i in items do
            match d.TryGetValue(i) with
            | false,_    -> d.[i] <- false         // erste Beobachtung
            | true,false -> d.[i] <- true; yield i // zweite Beobachtung
            | true,true  -> ()                     // bereits mindestens zweimal gesehen
    }

Answer 3

Dies ist die beste "funktionale" Lösung, die ich finden konnte, die nicht die gesamte Sequenz im Voraus verbraucht.

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 4

Vorausgesetzt, Ihre Sequenz endlich ist, erfordert diese Lösung einen Durchlauf der Sequenz:

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

Sie können die Länge der Sequenz als Kapazität des Dictionary angeben, aber es erfordert eine weitere vollständige Aufzählung der Sequenz.

EDIT: Um das 2. Problem zu lösen, könnte man Duplikate bei Bedarf generieren:

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 5

Funktionale Lösung:

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