Python. Идентичность в наборах объектов. И хеширование

Как использовать __hash__ и __eq__ в идентификации в наборах? Например, некоторый код, который должен помочь решить головоломку домино:

class foo(object): def __init__(self, one, two): self.one = one self.two = two def __eq__(self,other): if (self.one == other.one) and (self.two == other.two): return True if (self.two == other.one) and (self.one == other.two): return True return False def __hash__(self): return hash(self.one + self.two) s = set() for i in range(7): for j in range(7): s.add(foo(i,j)) len(s) // returns 28 Why? 

Если я использую только __eq __ (), то len (s) равно 49. Его нормально, потому что, поскольку я понимаю объекты (1-2 и 2-1, например), не одинаковые, но представляют собой одно и то же домино. Поэтому я добавил хэш-функцию.
Теперь он работает так, как я хочу, но я ничего не понял: хеш 1-3 и 2-2 должен быть таким же, чтобы они учитывались как один и тот же объект и не должны были добавляться в набор. Но они делают! Я застрял.

5 Solutions collect form web for “Python. Идентичность в наборах объектов. И хеширование”

Равенство для целей dict / set зависит от равенства, определенного __eq__ . Тем не менее, требуется, чтобы объекты, сравнивающие одинаковые, имели одно и то же значение хеша, и именно поэтому вам нужно __hash__ . См. Этот вопрос для некоторых подобных обсуждений.

Сам хэш не определяет, совпадают ли два слова в словарях. Хэш похож на «ярлык», который работает только одним способом: если у двух объектов разные хэши, они определенно не равны; но если они имеют одинаковый хеш, они все равно могут быть не равными.

В вашем примере вы определили __hash__ и __eq__ чтобы делать разные вещи. Хэш зависит только от суммы чисел на домино, но равенство зависит от обоих отдельных чисел (по порядку). Это законно, поскольку все равно, что равные домино имеют равные хэши. Однако, как я уже говорил выше, это не означает, что равные суммы домино будут считаться равными. Некоторые неравные домино будут по-прежнему иметь равные хэши. Но равенство по-прежнему определяется __eq__ , и __eq__ прежнему смотрит на оба числа в порядке, поэтому это определяет, являются ли они равными.

Мне кажется, что в вашем случае правильная вещь – определить как __hash__ и __eq__ чтобы зависеть от упорядоченной пары — то есть сначала сравнить большее из двух чисел, а затем сравнить меньшее. Это будет означать, что 2-1 и 1-2 будут считаться одинаковыми.

Хэш – это лишь подсказка, чтобы помочь Python организовать объекты. При поиске какого-либо объекта foo в наборе все равно нужно проверить каждый объект в наборе с тем же хэшем, что и foo .

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

Если вы хотите использовать другое значение для фильтрации «дубликатов», используйте диктовку, которая отображает общее значение домино в первом домино, который вы видели. Не подрывайте встроенное поведение Python, чтобы означать нечто совершенно другое. (Как вы обнаружили, в любом случае это не работает).

Требование хэш-функций состоит в том, что если x == y для двух значений, то hash(x) == hash(y) . Обратное не обязательно должно быть правдой.

Вы можете легко понять, почему это происходит, рассматривая хеширование строк. Допустим, что hash(str) возвращает 32-битное число, и мы будем хешировать строки длиной более 4 символов (т. Е. Содержать более 32 бит). Есть более возможные строки, чем есть возможные значения хэширования, поэтому некоторые неравные строки должны иметь один и тот же хеш (это приложение принципа пигментной скважины ).

Наборы Python реализованы как хэш-таблицы. При проверке того, является ли объект членом набора, он будет вызывать свою хэш-функцию и использовать результат для выбора ведра, а затем использовать оператор равенства, чтобы убедиться, что он соответствует любому из элементов в ведре.

С вашей реализацией, 2-2 и 1-3 домино окажутся в хэш-ведре, но они не сравниваются с равными. Поэтому оба могут быть добавлены в набор.

Вы можете прочитать об этом в документации по модели данных Python, но короткий ответ заключается в том, что вы можете переписать хэш-функцию как:

 def __hash__(self): return hash(tuple(sorted((self.one, self.two)))) 

Мне нравится звук ответа, предоставленного Eevee, но мне трудно представить реализацию. Вот моя интерпретация, объяснение и реализация ответа, предоставленного Eevee.

  • Используйте сумму двух значений домино в качестве словаря.
  • Храните оба значения домино в качестве значения словаря.

Например, учитывая домино «12», сумма равна 3, и поэтому ключ словаря будет равен 3. Затем мы можем выбрать либо значение (1 или 2) для хранения в этой позиции (мы выберем первое значение, 1 ).

 domino_pairs = {} pair = '12' pair_key = sum(map(int, pair)) domino_pairs[pair_key] = int(pair[0]) # Store the first pair's first value. print domino_pairs 

Выходы:

 {3: '1'} 

Хотя мы сохраняем только одно значение из пары домино, другое значение можно легко вычислить из словарного ключа и значения:

 pair = '12' pair_key = sum(map(int, pair)) domino_pairs[pair_key] = int(pair[0]) # Store the first pair's first value. # Retrieve pair from dictionary. print pair_key - domino_pairs[pair_key] # 3-1 = 2 

Выходы:

 2 

Но поскольку две разные пары могут иметь одинаковое общее количество, нам нужно сохранить несколько значений по одному ключу. Таким образом, мы сохраняем список значений по одному ключу (т.е. сумме двух пар). Вводя это в функцию:

 def add_pair(dct, pair): pair_key = sum(map(int, pair)) if pair_key not in dct: dct[pair_key] = [] dct[pair_key].append(int(pair[0])) domino_pairs = {} add_pair(domino_pairs, '22') add_pair(domino_pairs, '04') print domino_pairs 

Выходы:

 {4: [2, 0]} 

Это имеет смысл. Обе пары суммируются до 4, но первое значение в каждой паре отличается, поэтому мы сохраняем оба. Реализация до настоящего времени позволит дублировать:

 domino_pairs = {} add_pair(domino_pairs, '40') add_pair(domino_pairs, '04') print domino_pairs 

Выходы

  {4: [4, 0]} 

«40» и «04» одинаковы в Dominos, поэтому нам не нужно хранить оба. Нам нужен способ проверки дубликатов. Для этого мы определим новую функцию has_pair :

  def has_pair(dct, pair): pair_key = sum(map(int, pair)) if pair_key not in dct: return False return (int(pair[0]) in dct[pair_key] or int(pair[1]) in dct[pair_key]) 

Как обычно, мы получаем сумму (наш словарь). Если это не в словаре, то пара не может существовать. Если он находится в словаре, мы должны проверить, существует ли какое- либо значение в нашей паре в словаре «ведро». Вставьте эту проверку в add_pair , и поэтому мы не добавляем повторяющиеся пары домино:

 def add_pair(dct, pair): pair_key = sum(map(int, pair)) if has_pair(dct, pair): return if pair_key not in dct: dct[pair_key] = [] dct[pair_key].append(int(pair[0])) 

Теперь добавление повторяющихся домино-пар работает правильно:

 domino_pairs = {} add_pair(domino_pairs, '40') add_pair(domino_pairs, '04') print domino_pairs 

Выходы:

 {4: [4]} 

Наконец, функция печати показывает, как сохранить только сумму пары домино и одно значение из той же пары, это то же самое, что и сохранение самой пары:

 def print_pairs(dct): for total in dct: for a in dct[total]: a = int(a) b = int(total) - int(a) print '(%d, %d)'%(a,b) 

Тестирование:

 domino_pairs = {} add_pair(domino_pairs, '40') add_pair(domino_pairs, '04') add_pair(domino_pairs, '23') add_pair(domino_pairs, '50') print_pairs(domino_pairs) 

Выходы:

 (4, 0) (2, 3) (5, 0) 
  • Классы словаря Python (которые являются объектами класса) сравниваются с несколькими компараторами
  • Разница между hash () и id ()
  • Как создать уникальный ключ для словаря в Python
  • Переопределение функции хищения Python в словаре
  • Хеширование словаря?
  • Можете ли вы предложить хорошую реализацию Minhash?
  • Python - лучший язык программирования в мире.