Consider following task.
Let A be a list of Comparable
items. Let B be a list of Comparable
items. Entries in these lists can be compared.
Output is a list of entries in A that are not in the list B.
Two conditions.
- Assume A and B are sorted.
- Count of the same entries are considered as difference of count in A and count in B. Output duplicates respectively to this difference if it is greater than zero. Otherwise, skip them.
Example:
A = [1, 1, 1, 2, 4, 7]
B = [1, 2, 2, 4, 6]
Output:
[1, 1, 7]
Description:
A has three 1, one 2.
B has one 1, two 2.
Result has three - one 1 and one - two 2.
Result has two 1 and (-1) 2.
Result has two 1.
Functional condition:
- Do it without loops.
Try to solve this task for different count ( 900 - 100_000 )
I am asking for effective (tail call optimized) solution.
Is it possible?
func generateArray(count: UInt = 900, range: UInt = 1000) -> [UInt] {
return Array(0..<count).map{ _ in return UInt.random(in: 0...range) }
}
func test_ListsDifference() {
let count = 10_000
let a = generateArray(count: count).sorted()
let b = generateArray(count: count).sorted()
var result = [UInt]()
self.measure {
result = rejecting(a, b)
}
}
My dirty solution so far
func rejecting(_ a: ArraySlice<T>, _ b: ArraySlice<T>) -> ArraySlice<T> {
func _rejecting(_ a: ArraySlice<T>, _ b: ArraySlice<T>, aStart: ArraySlice<T>.Index, bStart: ArraySlice<T>.Index) -> ArraySlice<T> {
if aStart == a.endIndex {
return []
}
else if bStart == b.endIndex {
return a[aStart..<a.endIndex]
}
else if a[aStart] == b[bStart] {
return _rejecting(a, b, aStart: aStart.advanced(by: 1), bStart: bStart.advanced(by: 1))
}
else if a[aStart] > b[bStart] {
return _rejecting(a, b, aStart: aStart, bStart: bStart.advanced(by: 1))
}
else {
return _rejecting(a, b, aStart: aStart.advanced(by: 1), bStart: bStart)
}
}
return _rejecting(a, b, aStart: a.startIndex, bStart: b.startIndex)
}