Элемент соответствия из коллекций, другой тип, общий элемент

Question

У меня есть две коллекции (скажем, Set и Array). Каждый имеет Object/Struct разного типа, но оба имеют primary key.

struct A {
    var name: String
    var primaryID: Int
}

class B {
    var kind: String
    var primaryID: Int
}

У меня есть эти коллекции:

var setOfA: Set<A>
var arrayOfB: Array<B>

Мне нужно обновить arrayOfB значением setOfA. Например, переберите arrayOfB, извлеките элемент из setOfA (где primaryID равен) и обновите arrayOfB.

будет выглядеть так:

for bElement in arrayOfB {
    let a = setOfA.first(where: { $0.primaryID == bElement.primaryID })
    bElement.kind = a.name // Just an example
}

Если эффективность first(where:) равна O (n) (я действительно не знаю), приведенный выше код равен O (n ^ 2) (учитывая, что обе коллекции имеют одинаковую длину).

Единственное, о чем я могу думать, - это удалить каждый элемент set, который я извлекаю, уменьшив внутренний цикл вдвое.

Есть ли лучший способ сделать это?

Answer 1

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

Вот что я бы сделал: сначала создайте словарь , который отображает каждый первичный идентификатор соответствующего элемента из setOfA:

var idToA: [Int: A] = [:]
for a in setOfA {
    idToA[a.primaryID] = a
}

Затем перейдите arrayOfB, найдите идентификатор в словаре и обновите элемент при необходимости:

for b in arrayOfB {
    if let a = idToA[b.primaryID] {
        b.kind = a.name
    }
}

Для этого требуется один обход setOfA и arrayOfB, плюс поиск по словарю. (И поиск в словаре быстр, если есть несколько коллизий на ключевых хешах, что имеет место для целочисленные ключи.)