语言不可知 – 功能编程：一个列表只包含唯一的项目？

发布时间：2020-12-16 19:08:35 所属栏目：安全来源：网络整理

导读：我有一个未排序的列表,想知道,它中的所有项目是否是唯一的. 我天真的做法是 val l = List(1,2,3,4,3)def isUniqueList(l: List[Int]) = (new HashSet()++l).size == l.size 基本上,我检查包含列表的所有元素的集合是否具有相同的大小(因为在原始列表中出现两

我有一个未排序的列表,想知道,它中的所有项目是否是唯一的.
我天真的做法是

val l = List(1,2,3,4,3)
def isUniqueList(l: List[Int]) = (new HashSet()++l).size == l.size

基本上,我检查包含列表的所有元素的集合是否具有相同的大小(因为在原始列表中出现两次的项目只会在集合中出现一次),但是我不知道这是否是理想的解决方案对于这个问题.

编辑：
我基于3个最流行的解决方案,l == l.distinct,l.size == l.distinct.size和Alexey的基于HashSet的解决方案.
每个功能运行1000次,唯一的10个项目列表,10000个项目的唯一列表,以及第三个季度中出现的一个项目的列表中的相同列表,复制到列表的中间.在每次运行之前,每个功能都被调用1000次以加热JIT,整个基准运行5次,然后再次使用System.currentTimeMillis.
该机器是具有3GB RAM的C2D P8400(2.26 GHz),Java版本是OpenJDK 64位服务器虚拟机(1.6.0.20). java参数是-Xmx1536M -Xms512M

结果：

l.size==l.distinct.size (3,5471,6492)
l==l.distinct           (3,5601,6054)
Alexey's HashSet        (2,1590,781)

具有较大对象的结果(从1KB到5KB的字符串)：

l.size==l.distinct.size MutableList(4,5566,7,6506)
l==l.distinct           MutableList(4,5926,6075)
Alexey's HashSet        MutableList(2,2341,784)

使用HashSets的解决方案绝对是最快的,正如他已经指出的,使用.size并没有产生重大的区别.

解决方法

这是我能想到的最快的纯功能解决方案：

def isUniqueList(l: List[T]) = isUniqueList1(l,new HashSet[T])

@tailrec
def isUniqueList1(l: List[T],s: Set[T]) = l match {
  case Nil => true
  case (h :: t) => if (s(h)) false else isUniqueList1(t,s + h)
}

这应该更快,但使用可变数据结构(基于由Vasil Remeniuk提供的不同实现)：

def isUniqueList(l: List[T]): Boolean = {
  val seen = mutable.HashSet[A]()
  for (x <- this) {
    if (seen(x)) {
      return false
    }
    else {
      seen += x
    }
  }
  true
}

这里是最简单的(相当于你的)：

def isUniqueList(l: List[T]) = l.toSet.size == l.size

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!