SCALA：在使用“.contains()”或“.exists()”时，哪些数据结构在哪些情况下是最优的？

Question

我想知道在哪些情况下使用哪些数据结构最适合进行“包含”或“存在”检查。

我提出这个问题是因为我来自Python背景，并习惯于对所有事情都使用if x in something:表达式。例如，哪些表达式评估得最快：

val m = Map(1 -> 1, 2 -> 2, 3 -> 3, 4 -> 4)
                                          //> m  : scala.collection.immutable.Map[Int,Int] = Map(1 -> 1, 2 -> 2, 3 -> 3, 4
                                          //|  -> 4)
val l = List(1,2,3,4)                     //> l  : List[Int] = List(1, 2, 3, 4)
val v = Vector(1,2,3,4)                   //> v  : scala.collection.immutable.Vector[Int] = Vector(1, 2, 3, 4)

m.exists(_._1 == 3)                       //> res0: Boolean = true
m.contains(3)                             //> res1: Boolean = true
l.exists(_ == 3)                          //> res2: Boolean = true
l.contains(3)                             //> res3: Boolean = true
v.exists(_ == 3)                          //> res4: Boolean = true
v.contains(3)                             //> res5: Boolean = true

直觉上，我认为对于随机检查，向量应该是最快的，而如果我们知道所检查的值在列表的开头并且有大量数据，则列表会更快。然而，欢迎确认或更正。此外，请随意扩展其他数据结构。

注意：如果您觉得这个问题过于模糊，请告诉我，因为我不确定我是否表达正确。

- TimY

---

请注意：http://www.scala-lang.org/docu/files/collections-api/collections_40.html - om-nom-nom

在Python中，与其他语言一样，当您主要需要成员资格检查时，首选的抽象数据类型是集合，而不是序列或映射。 - user395760

检查特定元素并不是随机检查，而是短路扫描向量/列表/数组：*取第一个元素，比较，如果不相等，则取第二个元素，比较，...*。另一方面，对于集合和映射，contains 应该是常数时间（不像 exists，它必须首先应用一些谓词，因此我认为它也是线性的）。 - om-nom-nom

Answer 1

Set和Map（采用默认的哈希表实现）在contains操作中速度远比其他数据结构快，因为它们可以立即计算出哈希值并跳转到正确的位置。例如，如果您想从包含1000个字符串的列表中查找任意一个字符串，Set上的contains操作约比List、Vector或Array上的contains操作快100倍。

在使用exists操作时，您只关心集合遍历的速度，因为您必须遍历所有元素。在这种情况下，List通常是最佳选择（除非您想手动遍历数组），但是Set等其他数据结构通常表现不佳（例如，当每个数据结构都包含1000个元素时，List上的exists操作比Set上的exists操作快大约8倍）。其他数据结构与List的运行速度差别通常在2.5倍以内（通常为1.5倍，但Vector具有树状结构，遍历速度不太快）。

- Rex Kerr

---

这对大多数用例来说可能不相关，但如果您愿意为您的 exists 谓词提供比不透明函数更多的结构，那么将能够更有效地实现它。如果您为可能的关系定义一个简单的 AST，则基于哈希的结构将擅长相等谓词，而有序结构（TreeMap、带有陷阱的 IntMap）将擅长相等谓词和排序谓词。Tries 可能擅长前缀匹配谓词，并且您可以获得任意复杂的 DAWGs 等。在谓词 DSL 中添加变量绑定器，它将变得更加高级！ - Mysterious Dan

@MyseriousDan - exists 是集合库中无结构测试的名称。当然，对于相等性有转换为 contains，对于树有类似于 range 的东西。但那不是 exists，那是其他东西。(你是不是想回复 gzm0，他声称没有比 O(n) 更快的 exists？在那种情况下，你的回复会更有意义。) - Rex Kerr

抱歉 :)，但我知道 exists 是一个 API 方法 :P 我只是在说，如果我们愿意打破不透明的函数模型，我们可以做得更好（但仍然有一种嵌入任意函数的方式，带有隐式转换，这样人们就可以假装更智能的接口不存在）。 - Mysterious Dan

@MyseriousDan - 的确，而且字节码对编译器或JVM不是不透明的，因此即使具有相同的接口，智能性也可以在该级别发挥作用。 - Rex Kerr

@ZviMints - OrderedSet 是一个 TreeSet，它是一个红黑树。常规（不可变的）Set 是一个哈希树集合。 - Rex Kerr

Answer 2

如果您想广泛使用contains，您应该使用Set（或Map）。

据我所知，没有数据结构实现了高效（即快于O（n））的exists，因为您传递的闭包可能与其中的元素无关。

- gzm0