language-agnostic - 函数式编程 : Does a list only contain unique items?

Question

我有一个未排序的列表，想知道其中的所有项目是否都是唯一的。
我天真的方法是

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，在使用 System.currentTimeMillis 获取时间之前，整个基准测试运行了 5 次。
机器是C2D P8400 (2.26 GHz)，3GB RAM，java版本是OpenJDK 64bit server VM (1.6.0.20)。 java 参数是 -Xmx1536M -Xms512M

结果:

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

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

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

使用 HashSets 的解决方案绝对是最快的，正如他已经指出的那样，使用 .size 并没有什么大的区别。

Answer 1

这是我能想到的最快的纯函数式解决方案:

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 给出的 distinct 实现):

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