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 |
+-----------+-----------+---------+