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

直觉上,我认为向量应该是随机检查的最快,如果知道检查的值是在列表的开头并且有大量数据,则列表将是最快的.但是,我们非常欢迎确认或更正.另外,请随意扩展到其他数据结构.

注意:如果您觉得这个问题太模糊,请告诉我,因为我不确定我是否正确地说它.

Answer 1

Set和Map(使用默认的哈希表实现)是迄今为止最快的,contains因为它们计算哈希值并立即跳转到正确的位置.例如,如果contains要从一千个列表中查找任意字符串,则在一个集合上比containson List或Vectoror 快约100倍Array.

有了exists,你真的只关心集合的移动速度 - 无论如何你必须遍历所有东西.在那里,List通常是冠军(除非你想手动遍历一个阵列),但只有Set等等通常特别糟糕(例如exists,List比Set每个拥有1000个元素的时候快8倍).其他的大约是2.5倍List(通常是1.5倍,但Vector有一个基础树结构,并不是那么快速遍历).