SCALA：當使用「.contains（）」或「.exists（）」時，哪些數據結構是最優的？

我想知道哪些數據結構對於使用「包含」或「存在」檢查是最佳的。SCALA：當使用「.contains（）」或「.exists（）」時，哪些數據結構是最優的？

我問，因爲我來自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

直覺上，我會假設，載體應該是最快的隨機檢查，如果一個人知道該檢查值在的開頭列出將最快清單，並有大量的數據。但是，確認或更正將是最受歡迎的。另外，請隨意擴展到其他數據結構。

注意：請讓我知道，如果您覺得這個問題太含糊，因爲我不確定我是否正確地措詞。

來源

2013-05-08 TimY

僅供參考http://www.scala-lang.org/docu/files/collections-api/collections_40.html – 2013-05-08 14:25:08

在Python中，與其他語言一樣，當您主要需要成員資格檢查時選擇的抽象數據類型是**集**，而不是序列或映射。 – delnan 2013-05-08 14:27:48

檢查一個特定的元素是**不是**一個隨機檢查，而是對向量/列表/數組進行全掃描shortcircuting：*取第一個元素，比較，如果不是等於，則取第二個，比較...... *。另一方面，集合和地圖上的「包含」應該是恆定時間的（不同於存在的，它必須首先應用一些謂詞，因此我認爲它也是線性的） – 2013-05-08 14:28:00

Set和Map（帶有默認散列表實現）在contains中是最快的，因爲它們計算散列值並立即跳到正確的位置。例如，如果您想從一千個列表中找到一個任意字符串，則集合上的contains大約比List或Vector或Array上的contains快100倍。

隨着exists，你真的只關心收集的速度有多快 - 無論如何你必須遍歷所有的東西。在那裏，List通常是冠軍（除非你想手動遍歷一個數組），但是隻有Set等等通常特別糟糕（例如List上的exists比每個有1000個元素的Set快約8倍）。其他的是在List（通常是1.5x，但是Vector具有底層樹結構，並不是所有的快速遍歷）的約2.5倍。

來源

2013-05-08 16:39:30

這與大多數用法無關的情況下，但如果你願意給你的'exists'謂詞更多的結構比不透明的函數，它可以更有效地實現它。如果你爲可能的關係定義了一個簡單的AST，那麼基於散列的結構將會很好地處理等式謂詞，而有序結構（'TreeMap'，'IntMap'帶有陷阱）將很好地處理謂詞和排序謂詞。嘗試可能擅長前綴匹配謂詞，並且可以獲得任意複雜的DAWG等。在您的謂詞DSL中添加變量綁定器，它會更有趣！ – 2013-05-08 18:30:43

@MyseriousDan - 'exists'是集合庫中無結構測試的名稱。當然有轉換爲'包含'的平等和相當於'範圍'的樹木。但那不是'存在'，那是別的。（你的意思是回答gzm0，他聲稱沒有比O（n）更快的存在'嗎？你的回答在這種情況下會更有意義。） – 2013-05-08 18:46:36

Err，yep，抱歉:)但我知道'存在「是一種API方法：P我只是說，如果我們願意從不透明函數模型中突破，我們可以做得更好（但仍然可以通過隱式轉換來嵌入任意函數，因此人們可以假裝更聰明的接口不存在） – 2013-05-08 19:24:15

如果您想廣泛使用contains，則應使用Set（或Map）。由於您通過的關閉可能甚至與內部元素不相關，因此沒有數據結構實現高效（即快於O（n））exists。

來源

2013-05-08 15:35:20 gzm0

SCALA：當使用「.contains（）」或「.exists（）」時，哪些數據結構是最優的？

回答

相關問題