Поиск дубликатов в несортированной последовательности эффективно

Мне нужен очень эффективный способ найти дубликаты в несортированной последовательности. Это то, что я придумал, но у него есть несколько недостатков, а именно:

излишне подсчитывает вхождения вне 2
потребляет всю последовательность перед получением дубликатов
создает несколько промежуточных последовательностей

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

Независимо от недостатков, я не вижу причины заменять это дважды кодом. Можно ли улучшить это с помощью сравнительно сжатого кода?

Ответ 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
    }

Ответ 2

Более элегантное функциональное решение:

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.

Обратите внимание, что член TryGetValue Dictionary позволяет мне избежать выделения во внутреннем цикле путем изменения значения выделенного стека, в то время как член расширения TryGetValue, предложенный F # (и используемый kvb в его/ее ответе) выделяет возвращаемый кортеж.

Ответ 3

Это лучшее "функциональное" решение, которое я мог бы придумать, чтобы он не потреблял всю последовательность вперед.

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)

Ответ 4

Предполагая, что ваша последовательность конечна, для этого решения требуется один запуск последовательности:

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: Чтобы решить вторую проблему, можно создать дубликаты по требованию:

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
   }

Ответ 5

Функциональное решение:

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