我需要一個(gè)類(lèi)似字典的結(jié)構(gòu)，該結(jié)構(gòu)可以采用無(wú)法散列的鍵并將它們映射為一個(gè)值。我需要這樣做有兩個(gè)原因：在遍歷列表時(shí)檢查是否已在O（1）中看到項(xiàng)目將每個(gè)項(xiàng)目映射到一個(gè)標(biāo)識(shí)符，例如一個(gè)字符所創(chuàng)建的類(lèi)似dict的結(jié)構(gòu)將在處理之后被丟棄，因此一旦可以對(duì)鍵進(jìn)行突變，就無(wú)法使用它。例子d = MutableKeyDict()d[[1, 2, 3]] = 'a'print([1, 2, 3] in d) # Trueprint((1, 2, 3) in d) # False執(zhí)行tl; dr我實(shí)現(xiàn)了一些行不通的方法。如果您看到實(shí)現(xiàn)此目標(biāo)的規(guī)范方法，請(qǐng)?zhí)^(guò)該部分?，F(xiàn)在，我編寫(xiě)了一個(gè)包裝器類(lèi)，該包裝器實(shí)現(xiàn)了一個(gè)__hash__方法，該方法依賴(lài)于等同于哈希其數(shù)據(jù)的不可變類(lèi)型。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))這使我能夠編寫(xiě)使用ForcedHashable來(lái)包裝其鍵的自定義dict類(lèi)的草稿。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) # Trueprint((1, 2, 3) in d) # False但是遇到一些嵌套在其自身中的對(duì)象的問(wèn)題。d = MutableKeyDict()x = []x.append(x)d[x] = 'foo' # raises a 'RecursionError: maximum recursion depth exceeded'當(dāng)然，遞歸源自該語(yǔ)句：if isinstance(obj, (list, tuple)): return tuple(ForcedHashable.hashable(o) for o in obj)我在使用進(jìn)行修復(fù)的過(guò)程中途memo很像，就像copy.deepcopy使用的那樣，但是后來(lái)我意識(shí)到即使我這樣做了，該方法也將引發(fā)RecursionError。def __eq__(self, other): return self.data == other.data問(wèn)題我希望以上內(nèi)容至少適用于內(nèi)置類(lèi)型。會(huì)有一個(gè)聰明的辦法解決這個(gè)問(wèn)題RecursionError嗎？如果沒(méi)有，是否存在將相等項(xiàng)（僅內(nèi)置類(lèi)型）關(guān)聯(lián)到臨時(shí)哈希的規(guī)范方法？非常歡迎使用其他方法。
1 回答
米琪卡哇伊
TA貢獻(xiàn)1998條經(jīng)驗(yàn) 獲得超6個(gè)贊
沒(méi)有理由該deepcopy技術(shù)對(duì)您來(lái)說(shuō)無(wú)法解決遞歸問(wèn)題。
我認(rèn)為您可能會(huì)遺漏的是deepcopy的備注基于id值的。你只需要包含捕撈對(duì)象本身，相同的，而不是對(duì)象包含平等的，但不同的對(duì)象。畢竟，您不能擁有無(wú)窮無(wú)盡但相等的對(duì)象的深度；那將需要無(wú)限的記憶。
事實(shí)上，你可以比這更簡(jiǎn)單deepcopy和pickle，因?yàn)樗](méi)有真正的問(wèn)題是什么，你返回重復(fù)的對(duì)象，只要它是可哈希的和獨(dú)特的。1個(gè)
因此，例如：
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
現(xiàn)在：
>>> 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>: {...}}
在執(zhí)行此操作時(shí)，請(qǐng)執(zhí)行以下操作：
elif isinstance(obj, (dict, MutableKeyDict)):
return frozenset((k, ForcedHashable.hashable(v, memo=memo)) for k, v in obj.items())
… 現(xiàn)在：
>>> d = MutableKeyDict()
>>> d[d] = d
>>> d
{<__main__.ForcedHashable object at 0x11584b320>: {...}}
1.除非您希望它們像Quine原子一樣工作，否則您希望它可以被散列并由相同類(lèi)型的所有其他Quine原子共享，這是一樣容易的。
添加回答
舉報(bào)
0/150
提交
取消