Использование не хешируемых объектов Python в качестве ключей в словарях

Question

Python не позволяет использовать не хэшируемые объекты в качестве ключей в других словарях. Как указал Андрей Власовских, есть хороший обходной путь для особого случая использования в качестве ключей не вложенных словарей:

frozenset(a.items())#Can be put in the dictionary instead

Есть ли способ использования произвольных объектов в качестве ключей в словарях?

Пример

Как это будет использоваться в качестве ключа?

{"a":1, "b":{"c":10}}

Крайне редко вам придется использовать что-то подобное в своем коде. Если вы считаете, что это так, сначала измените модель данных.

Точный вариант использования

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

Связанные проблемы

Эта подзадача была отделена от проблема здесь . Решения здесь относятся к случаю, когда словари не слоистые.

Answer 1

Не. Я согласен с комментариями Андрея по предыдущему вопросу, в которых нет смысла использовать словари в качестве ключей, особенно не вложенные. Ваша модель данных, очевидно, довольно сложна, и словари, вероятно, не правильный ответ. Вместо этого вы должны попробовать OO.

Answer 2

Опираясь на решение Криса Лутца снова.

import collections

def hashable(obj):
    if isinstance(obj, collections.Hashable):
        items = obj
    elif isinstance(obj, collections.Mapping):
        items = frozenset((k, hashable(v)) for k, v in obj.iteritems())
    elif isinstance(obj, collections.Iterable):
        items = tuple(hashable(item) for item in obj)
    else:
        raise TypeError(type(obj))

    return items

Answer 3

Основано на решении Криса Лутца. Обратите внимание, что это не обрабатывает объекты, которые изменяются путем итерации, такие как потоки, и не обрабатывает циклы.

import collections

def make_hashable(obj):
    """WARNING: This function only works on a limited subset of objects
    Make a range of objects hashable. 
    Accepts embedded dictionaries, lists or tuples (including namedtuples)"""
    if isinstance(obj, collections.Hashable):
        #Fine to be hashed without any changes
        return obj
    elif isinstance(obj, collections.Mapping):
        #Convert into a frozenset instead
        items=list(obj.items())
        for i, item in enumerate(items):
                items[i]=make_hashable(item)
        return frozenset(items)
    elif isinstance(obj, collections.Iterable):
        #Convert into a tuple instead
        ret=[type(obj)]
        for i, item in enumerate(obj):
                ret.append(make_hashable(item))
        return tuple(ret)
    #Use the id of the object
    return id(obj)

Answer 4

Я совершенно не согласен с комментариями и ответами о том, что этого не следует делать из соображений чистоты модели данных.

Словарь связывает объект с другим объектом, используя первый в качестве ключа. Словари нельзя использовать в качестве ключей, потому что они не могут быть хэшируемыми. Это не делает ничего менее значимым / практичным / необходимым для сопоставления словарей с другими объектами.

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

Я должен добавить, что я понятия не имею о том, как это можно / нужно сделать.

Я не совсем, должен ли это быть ответ или комментарий. Пожалуйста, поправьте меня, если нужно.

Answer 5

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

Для иллюстрации:

>>> ("a",).__hash__()
986073539
>>> {'a': 'b'}.__hash__()
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
TypeError: 'NoneType' object is not callable

Если ваш хэш не достаточно уникален, вы получите коллизии. Может быть и медленным.

Answer 6

Я согласен с Леннартом Регебро, что вы не согласны. Однако я часто нахожу полезным кэшировать некоторые вызовы функций, вызываемые объекты и / или объекты Flyweight, поскольку они могут использовать аргументы ключевых слов.

Но если вы действительно этого хотите, попробуйте pickle.dumps (или cPickle, если python 2.6) как быстрый и грязный хак. Это намного быстрее, чем любой из ответов, использующих рекурсивные вызовы, чтобы сделать элементы неизменяемыми, а строки можно хэшировать.

import pickle
hashable_str = pickle.dumps(unhashable_object)

Answer 7

Я столкнулся с этой проблемой при использовании декоратора, который кэширует результаты предыдущих вызовов на основе подписи вызовов. Я не согласен с комментариями / ответами здесь о том, что «вы не должны этого делать», но я думаю, что важно признать потенциал неожиданного и неожиданного поведения при переходе по этому пути. Я полагаю, что поскольку экземпляры являются как изменяемыми, так и хешируемыми, и изменить это не представляется практичным, нет ничего изначально неправильного в создании хеш-эквивалентов нехешируемых типов или объектов. Но, конечно, это только мое мнение.

Для тех, кому требуется совместимость с Python 2.5, может быть полезно следующее. Я основал это на предыдущем ответе.

from itertools import imap
tuplemap = lambda f, data: tuple(imap(f, data))
def make_hashable(obj):
  u"Returns a deep, non-destructive conversion of given object to an equivalent hashable object"
  if isinstance(obj, list):
    return tuplemap(make_hashable, iter(obj))
  elif isinstance(obj, dict):
    return frozenset(tuplemap(make_hashable, obj.iteritems()))
  elif hasattr(obj, '__hash__') and callable(obj.__hash__):
    try:
      obj.__hash__()
    except:
      if hasattr(obj, '__iter__') and callable(obj.__iter__):
        return tuplemap(make_hashable, iter(obj))
      else:
        raise NotImplementedError, 'object of type %s cannot be made hashable' % (type(obj),)
    else:
      return obj
  elif hasattr(obj, '__iter__') and callable(obj.__iter__):
    return tuplemap(make_hashable, iter(obj))
  else:
    raise NotImplementedError, 'object of type %s cannot be made hashable' % (type, obj)

Answer 8

с рекурсией !

def make_hashable(h):
    items = h.items()
    for item in items:
        if type(items) == dict:
            item = make_hashable(item)
    return frozenset(items)

Вы можете добавить другие типы тестов для любых других изменяемых типов, которые вы хотите сделать хэш Это не должно быть трудно.