Удалить дубликаты из массива не equatable объектов


У меня массив неEquatable объекты. Я хочу, чтобы удалить все дубликаты из массива.

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 } дает нам: 0, 1, 1, 2, 2

В настоящее время я делаю это путем сопоставления объектов недвижимости index, который equatable, так как это Int. Таким образом, я могу удалить дубликаты из массива индексов:

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

Для справки .removingDuplicates() приходит пост на StackOverflow


Примечание: в этой части я хочу быть пересмотрены.

Затем, я получаю объект с соответствующим индексом, перекрутив через индексы массива и добавить его в noDupes массив.

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 } сейчас: 0, 1, 2

Так вот, этот код работает, но он будет очень часто казнят. Поскольку я чувствую, что это не очень эффективный способ, чтобы удалить дубликаты, боюсь падение производительности.
Как я могу улучшить или упростить мой код и до сих пор успешно удалить дубликаты из массива?



2294
2
задан 19 марта 2018 в 03:03 Источник Поделиться
Комментарии
1 ответ

Прежде всего заметим, что нет необходимости делать SearchResult свойства (неявно развернул) варианты, так как они всегда инициализируются:

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

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

Ваш подход действительно не оптимально, после определения уникального набора собственность
значений исходного массива должны быть найдены для каждого значения отдельно. Этот поиск может быть улучшена немного с помощью first(where:)

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

Преимущество first(where:) за filter + first заключается в том, что в нем происходит короткое замыкание и не создавать промежуточный массив.

Но лучше и быстрее решение будет модифицировать removingDuplicates()
метод так, что он сравнивает элементы массива по заданному ключу (который
тогда должна быть Equatable).

Вот возможная реализация, используя “умный путь”характеристика
от 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
}
}

Это может просто быть использован в качестве

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

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

Она также может быть стоит добавить еще одну специализацию для случая, когда ключ
Hashable (как в вашем примере), потому что тогда seen массив может быть заменен на набор,
что улучшает скорость поиска от O(N) для 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
}
}

Обратите внимание, что if seen.insert(key).inserted тут “испытания и вставить, если нет” с помощью одного вызова.

Другой вариант (более гибким) заключается в передаче закрытие на функцию, которая определяет
ключ uniquing для каждого элемента:

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
}
}

Пример:

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

2
ответ дан 19 марта 2018 в 04:03 Источник Поделиться