python - 具有可散列键的自定义字典无法处理递归结构

Question

我需要一个类似字典的结构，它可以采用不可散列的键并将它们映射到一个值。我需要这个有两个原因:

1. 在遍历列表时检查某个项目是否已在 O(1) 时间内出现

2. 将每个项目映射到标识符，例如字符

创建的类似字典的结构将在该过程结束后被丢弃，因此一旦 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？如果没有，是否有一种规范的方法将相等的项(仅限内置类型)关联到临时哈希？其他方法也非常受欢迎。

Answer 1

deepcopy 技术没有理由不能帮助您解决递归问题。

我认为您可能会忽略的是，deepcopy 的内存是基于值的 id 的。您只需要捕获包含相同的对象，而不是包含相同但不同的对象的对象。毕竟，你不可能拥有无限深度的不同但相同的对象；这将需要无限的内存。

事实上，您可以使其比 deepcopy 和 pickle 更简单，因为重复返回的什么并不重要对象，只要它是可散列且唯一的。¹

例如:

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。除非您希望它们像奎因原子一样工作，在这种情况下您希望它可散列并由相同类型的所有其他奎因原子共享，这也很容易。