Scala 集合交集性能

Question

使用 Scala 的scala.collection.Set[T]. s给定一个仅包含几个元素的小集合和另一个b包含大量元素的大集合，两者之间是否存在性能差异：

s & b // s intersect b

和

b & s // b intersect s.

如果是，哪个最快？

Answer 1

答案是：很复杂。

不可变集的默认实现是scala.collection.immutable.Set。对于大小为 1 到 4 的情况有特殊情况。一旦元素超过 4 个，它将使用scala.collection.immutable.HashSet。

非常小的 s (1..4)

假设您有一个大 setb和一个小 set s，其中s包含 <4 个元素。

那么就会有很大的不同：

b & s将过滤b针对成员资格的所有元素s，因此进行 b.count * s.count 相等比较。由于 b 很大，所以速度会很慢。

s & bs将针对 中的成员资格过滤 的几个元素b，即 s.length 乘以哈希值，如果哈希值匹配，则进行相等比较（记住 b 是一个 HashSet）。由于它很小，所以应该非常快。

小 s (n>4)

一旦s大于4个元素，它也将是一个HashSet。HashSets 的交集是以对称且非常有效的方式编写的。它将组合s和的树结构b，并在哈希值匹配时执行相等比较。它将使用最大的结构共享。例如，如果b包含 的所有元素s，则结果将是与 s相同的实例，因此不会分配任何对象。

一般建议

如果您只是编写不太关心高性能的通用代码，那么使用默认实现（例如scala.collection.Set. 但是，如果您关心性能特征，最好使用具体的实现。例如，如果s和b被声明为scala.collection.immutable.HashSet，只要您有一个好的哈希函数，您将获得与顺序无关的一致高性能。