Swift: прерывистое, противоречивое, неожиданное поведение с использованием Set.insert () - PullRequest
Новая
       10

Swift: прерывистое, противоречивое, неожиданное поведение с использованием Set.insert ()

0 голосов
/ 05 января 2019

Редактировать: Я никогда не думал перезапустить Xcode после удаления производных данных. Теперь все работает точно так, как ожидалось.

У меня периодически возникают сбои в приложении. Я сузил это до некоторой странности с Set.insert(). Иногда вставка приводит к вызову моей функции ==, а иногда нет, без видимой причины. Вот лучший урезанный образец, который я могу придумать; бегает на детской площадке. 

// Results are the same whether I use Equatable or not
struct ID: Hashable, Equatable {
    let idNumber: Int

    // Results are the same whether I implement this or not
    func hash(into hasher: inout Hasher) {
        hasher.combine(idNumber)
    }

    // Always return true; it doesn't matter. What matters
    // is that sometimes the Set.insert() doesn't even
    // call this function.
    static func == (_ lhs: ID, _ rhs: ID) -> Bool {
        print("(eq)", terminator: ""); return true
    }
}

let id0 = ID(idNumber: 0)
let id1 = ID(idNumber: 1)

var uniqueIDs = Set<ID>()

print("a", terminator: "")
uniqueIDs.insert(id0)
print("b", terminator: "")
uniqueIDs.insert(id1)
print("c", terminator: "")

Если я проведу это десять раз на игровой площадке, примерно половину времени я увижу eq на выходе, а половину - нет. То есть примерно половина времени Set.insert() не вызывает мой == до попытки вставки.

Я читал о наборах Swift и не нашел ничего, что могло бы пролить свет. Я вроде думал, что если бы это было предполагаемое поведение, оно было бы задокументировано с прикрепленным большим предупреждающим знаком. Отсутствие таких предупреждений говорит о том, что я неправильно использую Sets, но я не знаю, что я делаю неправильно. Какой документ или какой SO ответ я пропустил?

Ответы [ 2 ]

0 голосов
/ 05 января 2019

Set не имеет смысла вызывать == для вашего типа, если нет столкновений значений. Я это красная сельдь.

Set вызывает hash(into hasher: inout Hasher) для ваших значений, а затем принимает модуль по размеру внутреннего массива набора. Результатом является индекс, по которому должно быть значение (если оно уже существует в наборе). Естественно, этот процесс позволяет нескольким значениям после хэширования и взятия по модулю оказаться в одном слоте массива.

Чтобы компенсировать это, вместо того, чтобы хранить элементы непосредственно в слотах массива, они хранятся в связанном списке. Концептуально предметы внутри одного слота называются «ведром». При поиске элемента Set использует значение хеш-функции для поиска правильного сегмента, но для поиска точного элемента необходимо выполнить итерацию по связанному списку. На этом этапе хеши больше не используются для идентификации элементов, поэтому Set использует == проверки, пока не найдет правильное совпадение. Это обычно довольно эффективно, потому что Set должен сделать массив достаточно большим, чтобы сегменты были маленькими и содержали очень мало коллизий.

Поскольку нахождение элемента внутри корзины - это O(N), если вы можете вызвать много коллизий хэшей, тогда вы можете заставить Set O(1) операции вставки / удаления / проверки выродиться в O(N) обходы над целые элементы Set (поскольку вы можете сделать так, чтобы все элементы отображались в одно ведро. Чтобы противостоять уязвимости DOS, современные ассоциативные структуры данных используют «начальное число», которое выбирается случайным образом при каждом запуске приложения, и использовать его для шифрования. хэши. Таким образом, становится очень трудно создавать полезные нагрузки с одинаковыми значениями хеш-функции (что может вызвать проблему с большим размером сегмента.) Отсюда и ваш недетерминизм. См. PSA: stdlib теперь использует случайным образом хешированные значения .

По сути, Set<T> - это просто Dictionary типа [T: Void]. Поэтому, если вы прочтете, как работают ассоциативные структуры данных на основе хеша (другие распространенные имена - словари, хеши, хэш-карты и т. Д.), Многое из этого применимо.

0 голосов
/ 05 января 2019

Похоже, площадка как-то сломана Это потому, что один и тот же код, который я вставил в пустой проект приложения, имеет другой вывод, чем тот же код на игровой площадке. Пожалуйста, посмотрите: 

@UIApplicationMain
class AppDelegate: UIResponder, UIApplicationDelegate {

    var window: UIWindow?


    func application(_ application: UIApplication, didFinishLaunchingWithOptions launchOptions: [UIApplication.LaunchOptionsKey: Any]?) -> Bool {
        // Override point for customization after application launch.
        doSmth()
        return true
    }

    func doSmth(){


        // Results are the same whether I use Equatable or not
        struct ID: Hashable, Equatable {
            let idNumber: Int

            // Results are the same whether I implement this or not
            func hash(into hasher: inout Hasher) {
                hasher.combine(idNumber)
            }

            // Always return true; it doesn't matter. What matters
            // is that sometimes the Set.insert() doesn't even
            // call this function.
            static func == (_ lhs: ID, _ rhs: ID) -> Bool {
                // print("(eq)", terminator: "");
                // return false
                return true
            }
        }

        let id0 = ID(idNumber: 0)
        let id1 = ID(idNumber: 1)
        let id2 = ID(idNumber: 2)

        var uniqueIDs = Set<ID>([id0, id1])

        uniqueIDs.insert(id0)
        uniqueIDs.insert(id1)
        uniqueIDs.insert(id2)
        uniqueIDs.insert(id0)
        uniqueIDs.insert(id1)

        uniqueIDs.forEach{ value in
            print("value - \(value)")
        } 
    }
}

Распечатывает: 

value - ID(idNumber: 0)
value - ID(idNumber: 1)
value - ID(idNumber: 2)

Нет дубликатов (даже когда я пытался добавить дубликаты).

...