Swift - performance wise - comparing two arrays and get the difference in each and common in both

Question

Hope you are having a great day.

I'm trying to understand what is the fastest approach to do the following:

Assuming I have these two Arrays:

var firstArray = ["a","b","c"]
var secondArray = ["a","d","e"]

I'd like to get as an output:

1)Array of objects that inside firstArray but no in secondArray .
1)Array of objects that inside secondArray but no in firstArray .
3)Array of the common objects between firstArray and secondArray.

So basically the output would be:

1) ["b","c"]
2) ["d","e"]
3) ["a"]

The main issue here is to understand what is the most efficient way to do so. Thank you very much!

Answer 1

If your arrays are sorted and the items are unique in each array, the fastest way would be to handle each of the items only once. Start by comparing the first items in each array; if they are equal, put that into the common array and then move on to the second items. If one item is less than another, it goes into the unique array of the lesser item and you move on to the next item in the lesser array. Continue this process until you run out of items for one array, then put the remaining items of the second array into the unique items array for that array.

var i = 0
var j = 0

let a = ["a", "b", "c"]
let b = ["a", "d", "e"]

var aUnique = [String]()
var bUnique = [String]()
var common = [String]()

while i < a.count && j < b.count {
    if a[i] == b[j] {
        common.append(a[i])
        i += 1
        j += 1
    } else if a[i] < b[j] {
        aUnique.append(a[i])
        i += 1
    } else {
        bUnique.append(b[j])
        j += 1
    }
}

if i < a.count {
    // put remaining items into aUnique
    aUnique += a[i ..< a.count]
} else if j < b.count {
    // put remaining items into bUnique
    bUnique += b[j ..< b.count]
}

print(common)  // ["a"]
print(aUnique) // ["b", "c"]
print(bUnique) // ["d", "e"]

---

Analysis

• This algorithm appends one item to one of the arrays each time through the loop. It will loop at most a.count + b.count - 1 times if both arrays are unique relative to each other, or only their last item is common.
• If both arrays are identical, it will loop only a.count times.
• If all elements of array b are greater than the elements of array a, it will loop only a.count times. If all elements of array a are greater than the elements of array b, it will loop only b.count times.

Answer 2

I will assume that the elements of your arrays are Equatable.

If they are also Hashable, and if the order of the elements is not important for you, and if (as in your example), all elements are unique, you might want to consider using set algebra rather than the an ordered collection type such as Array. E.g. using Set in Swift allows you to use the subtract(_:) or subtracting(_:) mutating/non-methods for 1) and 2), and intersection(_:)/formIntersection(_:) for 3), which all use O(1) (amortized) lookup for comparing elements between the sets (as compared to e.g. using O(n) contains(_:) of Array (with Equatable elements) to lookup existance of some specified element).

For additional details, see the language reference for Set as well as the thread linked to by vadian:

• Set operations (union, intersection) on Swift array?

---

If the elements in each array is not unique, and you want to keep multiples as well as the order between the elements, you could use the Set representation of one of the arrays while filtering the other one.

E.g., for:

var firstArray = ["a","b","c"]
var secondArray = ["a","d","e"]

A) in O(n):

let excludeElements = Set(secondArray)        // O(n)
secondArray = secondArray
    .filter { !excludeElements.contains($0) } // O(n) due to O(1) (amortized) .contains lookup

B) in O(n):

let excludeElements = Set(firstArray)         // O(n)
secondArray = secondArray
    .filter { !excludeElements.contains($0) } // O(n) due to O(1) (amortized) .contains lookup

C) in O(n), using order and duplicates as they occur in firstArray:

let includeElements = Set(secondArray)  // O(n)
let commonElements = firstArray
    .filter(includeElements.contains)   // O(n) due to O(1) (amortized) .contains lookup

C) in O(n), using order and duplicates as they occur in secondArray:

let includeElements = Set(firstArray) // O(n)
let commonElements = secondArray
    .filter(includeElements.contains) // O(n) due to O(1) (amortized) .contains lookup

---

Performance?

The above only looks at asymptotic time complexity, and doesn't take into account any actual benchmarking. Generally the functional methods such as filter are slower than just a for or while loop, so if performance becomes an issue for your app, you should consider, at that point, performing profiling as well as custom bench-marking possible bottlenecks in your algorithms.

Also, if your arrays are known to be sorted, there are more efficient ways to traverse them and filter out the result. See e.g. the following thread (C language, but the logic is the important part):

• Finding common elements in two arrays of different size