在列表中查找重复元素的基本功能是什么？

Question

在列表中查找重复元素的基本功能是什么？

翻译过来,我该如何简化以下功能:

let numbers = [ 3;5;5;8;9;9;9 ]

let getDuplicates = numbers |> List.groupBy id
                            |> List.map snd
                            |> List.filter (fun set -> set.Length > 1)
                            |> List.map (fun set -> set.[0])

我确定这是重复的.但是,我无法在此网站上找到问题.

UPDATE

let getDuplicates numbers =

    numbers |> List.groupBy id
            |> List.choose (fun (k,v) -> match v.Length with
                                         | x when x > 1 -> Some k
                                         | _            -> None)

Answer 1

简化您的功能:

每当你有一个过滤器后面跟一个地图,你可以用一个选择替换该对.选择的目的是为列表中的每个值运行一个函数,并仅返回返回Some值的项(无值被删除,这是过滤器部分).无论你放入什么价值,有些是地图部分:

let getDuplicates = numbers |> List.groupBy id
                            |> List.map snd
                            |> List.choose( fun( set ) ->
                               if set.Length > 1
                                  then Some( set.[0] )
                                  else None )

我们可以通过删除地图再采取一个步骤.在这种情况下,保持包含密钥的元组是有帮助的,因为它消除了获取列表的第一项的需要:

let getDuplicates = numbers |> List.groupBy id
                            |> List.choose( fun( key, set ) ->
                               if set.Length > 1
                                  then Some key
                                  else None )

这比原来简单吗？也许.因为选择结合了两个目的,它必然比那些保持独立的目的(过滤器和地图)更复杂,这使得一眼就能更难理解,也许撤消更"简化"的代码.稍后会详细介绍.

分解这个概念

但是,简化代码并不是直接的问题.您询问了有助于查找重复项的函数.从高层次来看,你如何找到重复的？这取决于您的算法和具体需求:

• 您给定的算法使用"根据其值在桶中放置项目",以及"查找具有多个项目的存储桶".这是与List.groupBy和List.choose(或过滤器/地图)的直接匹配
• 一种不同的算法可能是"遍历所有项目","在我们看到每个项目时修改累加器",然后"报告所有已多次看到的项目".这有点像第一个算法,其中像List.fold这样的东西正在替换List.groupBy,但如果你需要拖动其他类型的状态,它可能会有所帮助.

• 也许您需要知道有多少次重复.满足这些要求的不同算法可以是"对项目进行排序以使它们总是在升序",并且"如果下一项与当前项目相同则标记".在这种情况下,你有一个List.sort,后面是List.toSeq,然后是Seq.windowed:

  let getDuplicates = numbers |> List.sort
                              |> List.toSeq
                              |> Seq.windowed 2
                              |> Seq.choose( function
                                | [|x; y|] when x = y -> Some x
                                | _ -> None )
  

  注意,这会返回一个带有[5; 9; 9],通知你9重复两次.

• 这些算法主要基于List函数.已经有两个答案,一个是可变的,另一个是不是,它们基于集合和存在.

我的观点是,有助于查找重复项的完整功能列表将像一个列出现有集合函数的人一样 - 这一切都取决于您尝试做什么以及您的具体要求.我认为您选择List.groupBy和List.choose可能就像它获得的一样简单.

简化可维护性

关于简化的最后一个想法是要记住,简化代码将在一定程度上提高代码的可读性.超越这一点的"简化"很可能涉及技巧或模糊的意图.如果我回顾一下我写的代码样本,甚至几个星期和几个项目之前,最短也许最简单的代码可能不是最容易理解的.因此,最后一点 - 简化未来的代码可维护性可能是您的目标.如果是这种情况,您的原始算法仅修改了groupBy元组,并添加了关于管道的每个步骤正在做什么的注释可能是您最好的选择:

// combine numbers into common buckets specified by the number itself
let getDuplicates = numbers |> List.groupBy id
                            // only look at buckets with more than one item
                            |> List.filter( fun (_,set) -> set.Length > 1)
                            // change each bucket to only its key
                            |> List.map( fun (key,_) -> key )

最初的问题评论已经表明,对于不熟悉它的人来说,您的代码并不清楚.这是一个经验问题吗？当然.但是,无论我们是在团队中工作,还是孤狼,优化代码(如果可能)以便快速理解应该可以接近每个人的首要任务.(从沙箱上爬下来......):)

祝你好运.

Answer 2

如果您不介意在本地范围内使用可变集合,则可以这样做:

open System.Collections.Generic

let getDuplicates numbers =
    let known = HashSet()
    numbers |> List.filter (known.Add >> not) |> set

Answer 3

您可以将最后三个操作包装在 a 中List.choose：

let duplicates =
   numbers 
   |> List.groupBy id
   |> List.choose ( function
          | _, x::_::_ -> Some x
          | _ -> None )