Scala查找范围内的缺失值

Question

例如，对于给定的范围

val range = (1 to 5).toArray
val ready = Array(2,4)

缺失值(未准备好)是

val missing = range.toSet diff ready.toSet
Set(5, 1, 3)

实际用例包括数千个范围实例(可能)有数千个缺失值或未就绪值。 Scala 中是否有更省时的方法？

Answer 1

diff操作在 Scala 中实现为 foldLeft在左操作数上，右操作数的每个元素都从左集合中删除。让我们假设左右操作数有 m和 n元素，分别。

调用 toSet在 Array 上或 Range对象将返回 HashTrieSet ，这是一个 HashSet实现，因此，提供了复杂性几乎 O(1) 的删除操作.因此，diff 的整体复杂性操作是O(m) .

现在考虑一种不同的方法，我们会看到这实际上非常好。还可以通过对两个范围进行排序，然后以合并排序的方式遍历它们一次以消除出现在两个范围中的所有元素来解决该问题。这会给您带来 O(max(m, n) * log(max(m, n))) 的复杂性，因为您必须对两个范围进行排序。

更新

我进行了一些实验来研究是否可以通过使用可变哈希集而不是不可变来加快计算速度。如下表所示的结果是取决于range的大小比例和 ready .

如果 ready.size/range.size < 0.2 使用不可变散列集似乎更有效.在这个比率之上，可变散列集优于不可变散列集。

对于我的实验，我设置了 range = (1 to n) , 与 n是 range 中的元素数量.对于 ready我选择了一个随机子集 range与相应的元素数量。我将每次运行重复 20 次，并总结使用 System.currentTimeMillis() 计算的时间。 .

range.size == 100000
+-----------+-----------+---------+
| Fraction  | Immutable | Mutable |
+-----------+-----------+---------+
| 0.01      |        28 |     111 |
| 0.02      |        23 |     124 |
| 0.05      |        39 |     115 |
| 0.1       |       113 |     129 |
| 0.2       |       174 |     140 |
| 0.5       |       472 |     200 |
| 0.75      |       722 |     203 |
| 0.9       |       786 |     202 |
| 1.0       |       743 |     212 |
+-----------+-----------+---------+

range.size == 500000
+-----------+-----------+---------+
| Fraction  | Immutable | Mutable |
+-----------+-----------+---------+
| 0.01      |        73 |     717 |
| 0.02      |       140 |     771 |
| 0.05      |       328 |     722 |
| 0.1       |       538 |     706 |
| 0.2       |      1053 |     836 |
| 0.5       |      2543 |    1149 |
| 0.75      |      3539 |    1260 |
| 0.9       |      4171 |    1305 |
| 1.0       |      4403 |    1522 |
+-----------+-----------+---------+