以有效的方式查找未排序的重复项

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.

注意,TryGetValue成员Dictionary允许我通过改变堆栈分配值来避免在内部循环中进行分配,而TryGetValueF#提供的扩展成员(并且在他/她的回答中由kvb使用)分配其返回元组.

Answer 2

这是一个必要的解决方案(可以肯定的是稍长一点):

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
    }