我想知道在哪种情况下哪种数据结构最适合使用“包含”或“存在”检查。
我问是因为我来自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
凭直觉,我认为向量应该是随机检查最快的,如果知道列表中的检查值位于列表的开头并且有很多数据,则列表将是最快的。但是,欢迎您确认或更正。另外,请随时扩展到其他数据结构。
注意:如果您觉得这个问题太含糊,请告诉我,因为我不确定我的措词是否正确。
最佳答案
到目前为止,Set
和Map
(具有默认的哈希表实现)在contains
上速度最快,因为它们计算哈希值并立即跳转到正确的位置。例如,如果要从一千个列表中查找任意字符串,则集合中的contains
大约比contains
或List
或Vector
上的Array
快100倍。
使用exists
,您实际上只关心集合的遍历速度-无论如何,您必须遍历所有内容。在那里,List
通常是冠军(除非您想手动遍历数组),但是通常只有Set
等等特别糟糕(例如,exists
上的List
比<< cc>,每个都有1000个元素)。其他的大约在Set
的2.5倍之内(通常是1.5倍,但是List
具有底层树结构,遍历的速度并不那么快)。
关于performance - SCALA:在使用“.contains()”或“.exists()”的情况下,哪种数据结构是最佳的?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/16443177/