performance - 有效地在未排序的序列中查找重复项

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 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 成员允许我通过改变堆栈分配的值来避免内部循环中的分配，而 TryGetValue 扩展F# 提供的成员(kvb 在他/她的回答中使用)分配其返回元组。