Remove duplicates from array of non-equatable objects

Question

I have an array of non-Equatable objects. I want to remove all the duplicates from the array.

class SearchResult { // non-equatable
    var index: Int!
    var score: Int!

    init(_ index: Int, score: Int = 0) { 
        self.index = index 
        self.score = score
    }
}
var searchResults: [SearchResult] = [SearchResult(0), SearchResult(1), SearchResult(1), SearchResult(2), SearchResult(2)]

searchResults.map { $0.index } gives us: 0, 1, 1, 2, 2

Currently, I do so by mapping the objects' property index, which is equatable, since it's an Int. This way, I can remove the duplicates from the indices array:

let withDupes: [SearchResult] = searchResults
let indices = withDupes.map { $0.index }.removingDuplicates()

---

For reference, .removingDuplicates() comes from a post on StackOverflow

---

Note: this is the part I want to be reviewed.

Then, I get the object with the corresponding index by looping through the indices array and add it to the noDupes array.

var noDupes: [SearchResult] = []
indices.forEach { (index) in
    guard let notADupe = (withDupes.filter { $0.index == index }).first else { return }
    noDupes.append(notADupe)
}

noDupes.map { $0.index } now is: 0, 1, 2

Now, this code works, but it will be executed very often. Since I feel like this is not a very efficient way to remove the duplicates, I fear a performance drop.
How can I improve and / or simplify my code and still successfully remove the duplicates from the array?

Answer 1

First note that there is no need to make the SearchResult properties (implicitly unwrapped) optionals, as they are always initialized:

class SearchResult { // non-equatable
    var index: Int
    var score: Int

    init(_ index: Int, score: Int = 0) {
        self.index = index
        self.score = score
    }
}

Your approach is indeed not optimal, after determining a unique set of property values, the original array must be searched for each value separately. This lookup can be improved slightly by using first(where:)

var noDupes: [SearchResult] = []
indices.forEach { (index) in
    guard let notADupe = withDupes.first(where: { $0.index == index }) else { return }
    noDupes.append(notADupe)
}

The advantage of first(where:) over filter + first is that it short-circuits and does not create an intermediate array.

But a better and faster solution would be to modify the removingDuplicates() method so that it compares the array elements according to a given key (which is then required to be Equatable).

Here is a possible implementation, using the “Smart KeyPath” feature from Swift 4:

extension Array {
    func removingDuplicates<T: Equatable>(byKey key: KeyPath<Element, T>)  -> [Element] {
        var result = [Element]()
        var seen = [T]()
        for value in self {
            let key = value[keyPath: key]
            if !seen.contains(key) {
                seen.append(key)
                result.append(value)
            }
        }
        return result
    }
}

This can then simply be used as

let searchResults: [SearchResult] = [SearchResult(0), SearchResult(1), SearchResult(1), SearchResult(2), SearchResult(2)]

let withoutDuplicates = searchResults.removingDuplicates(byKey: \.index)

It might also be worth to add another specialization for the case that the key is Hashable (as it is in your example) because then the seen array can be replaced by a set, which improves the lookup speed from O(N) to O(1):

extension Array {
    func removingDuplicates<T: Hashable>(byKey key: KeyPath<Element, T>)  -> [Element] {
        var result = [Element]()
        var seen = Set<T>()
        for value in self {
            if seen.insert(value[keyPath: key]).inserted {
                result.append(value)
            }
        }
        return result
    }
}

Note that if seen.insert(key).inserted does the “test and insert if not present” with a single call.

Another (more flexible) option is to pass a closure to the function which determines the uniquing key for each element:

extension Array {
    func removingDuplicates<T: Hashable>(byKey key: (Element) -> T)  -> [Element] {
        var result = [Element]()
        var seen = Set<T>()
        for value in self {
            if seen.insert(key(value)).inserted {
                result.append(value)
            }
        }
        return result
    }
}

Example:

let withoutDuplicates = searchResults.removingDuplicates(byKey: { $0.index })