如何測試一個集合包含另一至少一個值設置

而一個Set B，其中A尺寸b

什麼是最高效的解決方案來測試b是否包含a中的至少一個值。

解決方案1：相交的複雜性是什麼？

def containsAtLeastOne[A](a:Set[A], b: Set[A]) = a.intersect(b).nonEmpty

解決方案2：O（一）在最壞的情況下

def containsAtLeastOne[A](a:Set[A], b: Set[A]) = a.exists(b.contains(_))

解決方案3：在最壞的情況下

def containsAtLeastOne[A](a:Set[A], b: Set[A]) = b.exists(a.contains(_))

回答這個問題的最好方法是基準測試。解決方案2和3也有一個lambda分派，而解決方案1是純JVM調用。 – tryx

你所有的解決方案都是'O（ab）'，除了2/3的lambda以外，可能沒有真正的性能差異。 – Noah

這裏需要編輯嗎？解決方案2和3是相同的。 – jwvh

解決方案2和3 O（b）的更快的相比第一解。

但是解決方案2和解決方案3哪個更快？

這取決於每個集合包含的數據。例如，假設setA有100個元素，setB有3個元素，setA中的最後一個元素只是這兩個集合中的通用元素。在這種情況下，第三種解決方案更快所以這不取決於設置的大小，而是設置的數據也是如此。

無論如何，如果你需要更多的優化，你應該總是喜歡第二個和第三個解決方案，你可以在更小的集合上調用exists方法，在大多數情況下它應該更快。

2017-03-02 08:13:50 Shailesh

回答