Расширение CGPoint для соответствия Hashable

Для Пришествия кодового дня 1 , я обнаружил, что мне нужно использовать кортеж как ключ в словаре. Видя, что я не могу распространять кортежи в Swift, я решил расширить CGPoint, чтобы соответствовать Hashable:

extension CGPoint: Hashable {
    public var hashValue: Int {
        return hash()
    }

    func hash() -> Int {
        var hash = 23
        hash = hash &* 31 &+ Int(self.x)
        return hash &* 31 &+ Int(self.y)
    }
}

Это основано на реализации, найденной в Stack Overflow. Другим жизнеспособным вариантом может быть self.x.hashValue << sizeof(CGFloat) ^ self.y.hashValue (от здесь ).

Это работает, если x и y значения CGPoint являются целыми числами, но Int дает преобразование с потерями из CGFloat в Int, что может привести к хэш-коллизиям.

Как я могу улучшить эту реализацию и получить числа с плавающей запятой, чтобы хорошо играть с хеш-значением, которое является Int?

Или, лучший подход даже не должен заключаться в расширении CGPoint вообще и просто использовать пользовательскую конструкцию контейнера Swift или ---- +: = 12 =: + ----?

8 голосов | спросил JAL 2 FriEurope/Moscow2016-12-02T19:45:04+03:00Europe/Moscow12bEurope/MoscowFri, 02 Dec 2016 19:45:04 +0300 2016, 19:45:04

1 ответ


12

Я не вижу преимущества вычисления хэш-значения из Int(self.x) и Int(self.y). Как вы уже заметили, усечение плавающей запятой номера целых чисел теряют информацию и поэтому хэш-коллизий.

CGFloat (как и все типы числовых чисел Swift) Hashable и его hashValue - это целое число с таким же представлением памяти (как видно из реализации ). Таким образом, все возможные значения CGFloat имеют разные значения хэширования, что делает x.hashValue, y.hashValue намного лучше для вычисления хэш-значения для CGPoint, чем Int(self.x) и Int(self.y).

Остается вопрос, как вычислить хэш-значение точки из хеш-значений его координат. Конечно, не может быть «лучший хэш», который работает для всех наборов данных. Но чтобы получить по крайней мере, идея, которая может быть лучше или хуже, я использовал после простого теста:

var hv = Set<Int>()
var count = 0
for i in -200 ..< 200 {
    for j in -200 ..< 200 {
        count += 1
        let p = CGPoint(x: CGFloat(i)/20, y: CGFloat(j)/20)
        hv.insert(p.hashValue)
    }
}

print(count, hv.count)

Он вычисляет значения хэша 16 000 точек, где оба x и y диапазон от -20 до 19.9 с шагами 0.1 и подсчитывает сколько разных значений хэша мы получаем.

Связанная хеш-функция из hash_combine () функции для этой цели и реализация имеет один общий вариант

public var hashValue: Int {
    return (self.x.hashValue << MemoryLayout<CGFloat>.size) ^ self.y.hashValue
}
// # of points: 160000 hash values:  79976

, а также специализации для public var hashValue: Int { var hash = 23 hash = hash &* 31 &+ Int(self.x) return hash &* 31 &+ Int(self.y) } // # of points: 160000 hash values: 1249 и hashValue

Int()

Здесь важно использовать целые числа unsigned , иначе правый сдвиг public var hashValue: Int { var hash = 23 hash = hash &* 31 &+ self.x.hashValue return hash &* 31 &+ self.y.hashValue } // # of points: 160000 hash values: 68827 сохранит бит знака.

Swift template <typename SizeT> inline void hash_combine_impl(SizeT& seed, SizeT value) { seed ^= value + 0x9e3779b9 + (seed<<6) + (seed>>2); } - целое число со знаком, однако, поэтому мы должны соответственно преобразовать:

uint32_t

Как видно, эта хеш-функция имеет всего 42 столкновения и намного лучше предыдущих (для этого набора данных). Он также относительно прост для вычисления и может быть легко адаптирован для типов с большим количеством свойств.

Если это не достаточно хорошо, вы можете попробовать другие методы «хэш-комбинирования», например, 32-разрядный или 64-битные специализации из библиотеки Boost (в зависимости от размер uint64_t на вашей платформе) и проверьте, работает ли это лучше. Другой здесь , и, вероятно, гораздо больше.

Наконец, вы спросили:

  

Или, лучший подход даже не должен расширять CGPoint вообще и просто использовать пользовательскую структуру Swift-контейнера или подкласс NSObject?

Это зависит. Если кортеж представляет собой «точку в пространстве», то использование (и расширение)func hash_combine(seed: inout UInt, value: UInt) { let tmp = value &+ 0x9e3779b9 &+ (seed << 6) &+ (seed >> 2) seed ^= tmp } кажется прекрасным для меня. Если кортеж представляет что-то else (и вы просто выбрали seed >> 2, потому что у него два свойства), тогда я бы предпочел определить пользовательский hashValue, который ясно показывает его цель. Подкласс public var hashValue: Int { var seed = UInt(0) hash_combine(seed: &seed, value: UInt(bitPattern: x.hashValue)) hash_combine(seed: &seed, value: UInt(bitPattern: y.hashValue)) return Int(bitPattern: seed) } // # of points: 160000 hash values: 159958 будет тип ссылки и должен быть выбран только в том случае, если вам нужна ссылка семантика. В противном случае предпочтительны типы значений.


Обновление: . По сравнению с Swift 4.1, компилятор может синтезировать совместимость с Equatable /Hashable, если все ее члены являются Equatable /Hashable, см. SE-0185 Синтезирование соответствия Equalable и Hashable .

Пример:

Int

Фактическая хэш-функция - это деталь реализации, но в моем тесте он отлично работал: вышеупомянутый тестовый код не вызывал никаких столкновений для 16 000 пунктов.

ответил Martin R 2 FriEurope/Moscow2016-12-02T23:14:36+03:00Europe/Moscow12bEurope/MoscowFri, 02 Dec 2016 23:14:36 +0300 2016, 23:14:36

Похожие вопросы

Популярные теги

security × 330linux × 316macos × 2827 × 268performance × 244command-line × 241sql-server × 235joomla-3.x × 222java × 189c++ × 186windows × 180cisco × 168bash × 158c# × 142gmail × 139arduino-uno × 139javascript × 134ssh × 133seo × 132mysql × 132