我需要一个类似字典的结构,它可以采用不可散列的键并将它们映射到一个值。我需要这个有两个原因:
在遍历列表时检查某个项目是否已在 O(1) 时间内出现
将每个项目映射到标识符,例如字符
创建的类似字典的结构将在该过程结束后被丢弃,因此一旦 key 发生变化就无法使用。
示例
d = MutableKeyDict()
d[[1, 2, 3]] = 'a'
print([1, 2, 3] in d) # True
print((1, 2, 3) in d) # False
实现
tl;dr 我实现了一些不起作用的东西。如果您看到实现此目的的规范方法,请跳过该部分。
现在,我编写了一个包装类,它实现了 __hash__
方法,该方法依靠相当于散列其数据的不可变类型。
class ForcedHashable:
@staticmethod
def hashable(obj):
try:
hash(obj)
return obj
except TypeError:
if isinstance(obj, (list, tuple)):
return tuple(ForcedHashable.hashable(o) for o in obj)
elif isinstance(obj, set):
return frozenset(ForcedHashable(o) for o in obj)
elif isinstance(obj, dict):
return tuple((k, ForcedHashable.hashable(v)) for k, v in obj.items())
...
def __init__(self, data):
self.data = data
def __eq__(self, other):
return self.data == other.data
def __hash__(self):
return hash(self.hashable(self.data))
这使我能够编写自定义 dict 类的草稿,该类使用 ForcedHashable
来包装其键。
class MutableKeyDict(UserDict):
def __setitem__(self, key, value):
self.data[ForcedHashable(key)] = value
def __getitem__(self, item):
return self.data[ForcedHashable(item)]
def __contains__(self, item):
return ForcedHashable(item) in self.data
它适用于基本情况...
d = MutableKeyDict()
d[[1, 2, 3]] = 'a'
print([1, 2, 3] in d) # True
print((1, 2, 3) in d) # False
但是遇到了一些嵌套在其自身中的对象的问题。
d = MutableKeyDict()
x = []
x.append(x)
d[x] = 'foo' # raises a 'RecursionError: maximum recursion depth exceeded'
递归当然源于该语句:
if isinstance(obj, (list, tuple)):
return tuple(ForcedHashable.hashable(o) for o in obj)
我正在使用 memo
实现修复,有点像 copy.deepcopy
使用的那样,但后来我意识到,即使我这样做了,此方法也会引发 RecursionError
。
def __eq__(self, other):
return self.data == other.data
问题
我希望以上内容至少适用于内置类型。
是否有一个聪明的方法来解决这个RecursionError
?如果没有,是否有一种规范的方法将相等的项(仅限内置类型)关联到临时哈希?其他方法也非常受欢迎。
最佳答案
deepcopy
技术没有理由不能帮助您解决递归问题。
我认为您可能会忽略的是,deepcopy
的内存是基于值的 id
的。您只需要捕获包含相同的对象,而不是包含相同但不同的对象的对象。毕竟,你不可能拥有无限深度的不同但相同的对象;这将需要无限的内存。
事实上,您可以使其比 deepcopy
和 pickle
更简单,因为重复返回的什么并不重要对象,只要它是可散列且唯一的。1
例如:
def hashable(obj, *, memo=None):
if memo is None:
memo = set()
if id(obj) in memo:
return (..., id(obj))
memo.add(id(obj))
try:
hash(obj)
return obj
except TypeError:
if isinstance(obj, (list, tuple)):
return tuple(ForcedHashable.hashable(o, memo=memo) for o in obj)
elif isinstance(obj, set):
return frozenset(ForcedHashable(o, memo=memo) for o in obj)
elif isinstance(obj, dict):
return frozenset((k, ForcedHashable.hashable(v, memo=memo)) for k, v in obj.items())
raise
现在:
>>> x = []
>>> x.append(x)
>>> ForcedHashable.hashable(x)
((Ellipsis, 4658316360),)
>>> d = MutableKeyDict()
>>> d[x] = d
>>> d[x]
{<__main__.ForcedHashable object at 0x115855240>: 2, <__main__.ForcedHashable object at 0x115a247f0>: {...}}
当我们这样做时,请执行以下操作:
elif isinstance(obj, (dict, MutableKeyDict)):
return frozenset((k, ForcedHashable.hashable(v, memo=memo)) for k, v in obj.items())
...现在:
>>> d = MutableKeyDict()
>>> d[d] = d
>>> d
{<__main__.ForcedHashable object at 0x11584b320>: {...}}
<小时/>
<子>1。除非您希望它们像奎因原子一样工作,在这种情况下您希望它可散列并由相同类型的所有其他奎因原子共享,这也很容易。
关于python - 具有可散列键的自定义字典无法处理递归结构,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/50979323/