Использование не хешируемых объектов Python в качестве ключей в словарях
Python не позволяет использовать не хэшируемые объекты в качестве ключей в других словарях. Как указал Андрей Власовских, есть хороший обходной путь для частного случая использования в качестве ключей не вложенных словарей:
frozenset(a.items())#Can be put in the dictionary instead
Есть ли способ использования произвольных объектов в качестве ключей в словарях?
Пример:
Как это будет использоваться в качестве ключа?
{"a":1, "b":{"c":10}}
Крайне редко вам придется использовать что-то подобное в своем коде. Если вы считаете, что это так, сначала подумайте об изменении своей модели данных.
Точный вариант использования
Вариант использования - кэширование вызовов произвольной функции только для ключевых слов. Каждый ключ в словаре представляет собой строку (имя аргумента), и объекты могут быть довольно сложными, состоящими из многоуровневых словарей, списков, кортежей и т. Д.
Связанные проблемы
Эта подзадача была отделена от проблемы здесь. Решения здесь имеют дело со случаем, когда словари не являются многоуровневыми.
8 ответов
Основано на решении Криса Лутца. Обратите внимание, что это не обрабатывает объекты, которые изменяются путем итерации, такие как потоки, и не обрабатывает циклы.
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)
На основе решения Криса Лутца снова.
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
Не. Я согласен с комментарием Андрея по предыдущему вопросу, который не имеет смысла иметь словари в качестве ключей, и особенно не вложенные. Ваша модель данных, очевидно, довольно сложна, и словари, вероятно, не правильный ответ. Вы должны попробовать OO вместо этого.
Я согласен с Леннартом Регебро, что вы этого не делаете. Однако я часто нахожу полезным кэшировать некоторые вызовы функций, вызываемые объекты и / или объекты Flyweight, поскольку они могут использовать ключевые аргументы.
Но если вы действительно этого хотите, попробуйте pickle.dumps (или же cPickle если python 2.6) как быстрый и грязный хак. Это намного быстрее, чем любой из ответов, использующих рекурсивные вызовы, чтобы сделать элементы неизменяемыми, а строки можно хэшировать.
import pickle
hashable_str = pickle.dumps(unhashable_object)
Если вам действительно нужно, сделайте ваши объекты хэшируемыми. Подкласс, который вы хотите вставить в качестве ключа, и предоставляет функцию __hash__, которая возвращает уникальный ключ для этого объекта.
Проиллюстрировать:
>>> ("a",).__hash__()
986073539
>>> {'a': 'b'}.__hash__()
Traceback (most recent call last):
File "<stdin>", line 1, in <module>
TypeError: 'NoneType' object is not callable
Если ваш хэш не достаточно уникален, вы получите коллизии. Может быть и медленным.
Я полностью не согласен с комментариями и ответами, говоря, что это не должно быть сделано по причине чистоты модели данных.
Словарь связывает объект с другим объектом, используя первый в качестве ключа. Словари нельзя использовать в качестве ключей, потому что они не могут быть хэшируемыми. Это не делает ничего менее значимым / практичным / необходимым для отображения словарей на другие объекты.
Как я понимаю систему привязки Python, вы можете привязать любой словарь к ряду переменных (или наоборот, зависит от вашей терминологии), что означает, что все эти переменные знают один и тот же уникальный "указатель" на этот словарь. Разве нельзя было бы использовать этот идентификатор в качестве ключа хеширования? Если ваша модель данных гарантирует / обеспечивает, что вы не можете иметь два словаря с одинаковым содержимым, используемым в качестве ключей, то это кажется мне безопасным методом.
Я должен добавить, что я понятия не имею о том, как это может / должно быть сделано, хотя.
Я не совсем, должен ли это быть ответ или комментарий. Пожалуйста, поправьте меня, если это необходимо.
Я столкнулся с этой проблемой при использовании декоратора, который кэширует результаты предыдущих вызовов на основе подписи вызова. Я не согласен с комментариями / ответами здесь о том, что "вы не должны этого делать", но я думаю, что важно признать потенциал неожиданного и неожиданного поведения при переходе по этому пути. Я думаю, что поскольку экземпляры являются как изменяемыми, так и хешируемыми, и изменить это не представляется практичным, нет ничего изначально неправильного в создании хешируемых эквивалентов нехешируемых типов или объектов. Но, конечно, это только мое мнение.
Для тех, кому требуется совместимость с 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)
С рекурсией!
def make_hashable(h):
items = h.items()
for item in items:
if type(items) == dict:
item = make_hashable(item)
return frozenset(items)
Вы можете добавить другие типы тестов для любых других изменяемых типов, которые вы хотите сделать хэшируемыми. Это не должно быть сложно.