如何在不使用引用的情况下删除F#序列中的重复项

Question

我有一个排序的序列,想要通过它并返回序列中的唯一条目.我可以使用以下函数来完成它,但它使用引用变量,我不认为这是解决问题的正确方法.

    let takeFirstCell sectors = 
        let currentRNCId = ref -1
        let currentCellId = ref -1
        seq {
            for sector in sectors do
                if sector.RNCId <> !currentRNCId || sector.CellId <> !currentCellId then
                    currentRNCId := sector.RNCId
                    currentCellId := sector.CellId
                    yield sector
        }

我怎么能以功能的方式做到这一点？

Answer 1

[1;1;1;2;2;2;3;3;3]
|> Seq.distinctBy id
|> printfn "%A"

Answer 2

Seq.distinct (1::[1..5])回报seq [1; 2; 3; 4; 5].这是你的意思吗？

Answer 3

distinct并且distinctBy都使用Dictionary并因此需要散列和一些内存来存储唯一的项目.如果您的序列已经排序,您可以使用以下方法(与您的类似).它几乎快两倍,并且具有恒定的内存使用,使其可用于任何大小的序列.

let distinctWithoutHash (items:seq<_>) =
  seq {
    use e = items.GetEnumerator()
    if e.MoveNext() then
      let prev = ref e.Current
      yield !prev
      while e.MoveNext() do
        if e.Current <> !prev then 
          yield e.Current
          prev := e.Current
  }

let items = Seq.init 1000000 (fun i -> i / 2)
let test f = items |> f |> (Seq.length >> printfn "%d")

test Seq.distinct        //Real: 00:00:01.038, CPU: 00:00:01.435, GC gen0: 47, gen1: 1, gen2: 1
test distinctWithoutHash //Real: 00:00:00.622, CPU: 00:00:00.624, GC gen0: 44, gen1: 0, gen2: 0

我无法找到一种方法来使用mutables代替refs(缺少手工编码的枚举器),我肯定会大大加快它(我试过它 - 没有区别).