代码之家 › 专栏 › 技术社区 › tstenner

函数编程:列表是否只包含唯一的项?

functional-programming scala language-agnostic

tstenner · 技术社区 · 14 年前

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

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基于哈希集的解决方案。每个函数都运行了1000次,其中有10个项目的唯一列表、10000个项目的唯一列表和相同的列表,其中一个项目出现在第三季度,复制到列表中间。在每次运行之前,每个函数都被调用1000次以预热JIT,整个基准测试在使用System.CurrentTimeMillis获取时间之前运行了5次。该机器是一个带有2GB RAM的C2D P8400(2.26 GHz),Java版本是OpenJDK 64位服务器VM(1.60.20)。Java ARG是XMX1536M—XMS512M

结果:

l.size==l.distinct.size (3, 5471, 2, 6492)
l==l.distinct           (3, 5601, 2, 6054)
Alexey's 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's HashSet        MutableList(2, 2341, 3, 784)

使用哈希集的解决方案绝对是最快的,正如他已经指出的那样,使用.size并不会造成很大的差异。

3 回复 | 直到 14 年前

Alexey Romanov 14 年前

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

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)
}

这应该更快,但使用可变的数据结构(基于 distinct 由Vasil Remenuk提供的实施:

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

Vasil Remeniuk 14 年前

我只会用 distinct 方法:

scala> val l = List(1,2,3,4,3)
l: List[Int] = List(1, 2, 3, 4, 3)

scala> l.distinct.size == l.size
res2: Boolean = false

添加 : Standard distinct implementation (从 scala.collection.SeqLike )使用可变哈希集查找重复元素:

  def distinct: Repr = {
    val b = newBuilder
    val seen = mutable.HashSet[A]()
    for (x <- this) {
      if (!seen(x)) {
        b += x
        seen += x
      }
    }
    b.result
  }

oxbow_lakes 14 年前

一种更有效的方法是试图找到一个重复;如果找到一个重复,这将更快地返回:

var dupes : Set[A] = Set.empty

def isDupe(a : A) = if (dupes(a)) true else { dupes += a; false }

//then
l exists isDupe