trjhtr

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?

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 )