Scala find missing values ​​in a range

Question

For a given range, for example

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

missing values ​​(not ready)

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

A real use case involves thousands of instances of a range with (possibly) thousands of missing or unprepared values. Is there a more time-efficient approach in Scala?

Answer 1

The diff operation is implemented in Scala as foldLeft on the left operand, where each element of the right operand is removed from the left collection. Suppose that the left and right operands have elements m and n respectively.

Calling the toSet an Array or Range object will return a HashTrieSet , which is an implementation of the HashSet and thus offers a delete operation with a complexity of almost O(1) . Thus, the total complexity of the diff operation is O(m) .

Given now a different approach, we will see that this is actually not bad. You can also solve the problem by sorting both ranges and then going through them once in the merge sort mode to eliminate all the elements that occur in both ranges. This will give you O(max(m, n) * log(max(m, n))) complexity because you need to sort both ranges.

Update

I conducted several experiments to find out if computation can be accelerated using mutable hash sets instead of immutable ones. The result, as shown in the tables below, is that it depends on the size of the rank Range and ready .

Using immutable hash sets seems to be more efficient if ready.size/range.size < 0.2 . Above this relationship, mutable hash tables are superior to immutable hash sets.

In my experiments, I set range = (1 to n) , with n being the number of elements in Range . For ready I chose a random subset of Range with the appropriate number of elements. I repeated each run 20 times and summarized the time calculated using 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 | +-----------+-----------+---------+