作为一个练习,主要是为了我自己的娱乐,我正在实现一个回溯包装解析器.对此的灵感是我想更好地了解hygenic宏如何在类似algol的语言中工作(与你通常在其中找到的语法免费lisp方言相对应).因此,通过输入的不同传递可能会看到不同的语法,因此缓存的解析结果无效,除非我还存储语法的当前版本以及缓存的解析结果.(编辑:使用键值集合的结果是它们应该是不可变的,但我不打算公开接口以允许它们被更改,因此可变或不可变集合都可以)
问题是python dicts不能作为其他dicts的键.即使使用元组(正如我将要做的那样)也无济于事.
>>> cache = {}
>>> rule = {"foo":"bar"}
>>> cache[(rule, "baz")] = "quux"
Traceback (most recent call last):
File "<stdin>", line 1, in <module>
TypeError: unhashable type: 'dict'
>>>
我想它必须一直是元组.现在python标准库提供了我所需要的,collections.namedtuple具有非常不同的语法,但可以用作键.继续上述会议:
>>> from collections import namedtuple
>>> Rule = namedtuple("Rule",rule.keys())
>>> cache[(Rule(**rule), "baz")] = "quux"
>>> cache
{(Rule(foo='bar'), 'baz'): 'quux'}
好.但是我必须为我想要使用的规则中的每个可能的键组合创建一个类,这不是那么糟糕,因为每个解析规则确切地知道它使用了什么参数,因此可以同时定义该类作为解析规则的函数.
编辑:namedtuples 的另一个问题是它们是严格定位的.两个看起来应该不同的元组实际上可以是相同的:
>>> you = namedtuple("foo",["bar","baz"])
>>> me = namedtuple("foo",["bar","quux"])
>>> you(bar=1,baz=2) == me(bar=1,quux=2)
True
>>> bob = namedtuple("foo",["baz","bar"]) …简短版本:作为无序项目字典实现的多集合的最佳散列算法是什么？
我正在尝试将一个不可变的multiset(这是一个包或其他语言的多重集合:像一个数学集,除了它可以容纳多个元素)作为字典实现.我已经创建了标准库类的子类collections.Counter,类似于这里的建议:Python hashable dicts,它建议像这样的哈希函数:
class FrozenCounter(collections.Counter):
# ...
def __hash__(self):
return hash(tuple(sorted(self.items())))
创建完整的项目元组会占用大量内存(相对于使用生成器而言),并且哈希将在我的应用程序的内存密集型部分中发生.更重要的是,我的字典键(multiset元素)可能不会是可订购的.
我正在考虑使用这个算法:
def __hash__(self):
return functools.reduce(lambda a, b: a ^ b, self.items(), 0)
我想使用按位XOR意味着顺序与散列值无关,与元组的散列不同？我想我可以在我的数据的无序流序列上半实现Python元组散列算法.请参阅https://github.com/jonashaag/cpython/blob/master/Include/tupleobject.h(在页面中搜索"hash"一词) - 但我几乎不知道有足够的C来阅读它.
思考？建议？谢谢.
set(),但事情必须是哈希的.)
@marcin和@senderle都给出了相同的答案:使用hash(frozenset(self.items())).这是有道理的,因为items()"视图"是设置的.@marcin是第一个,但我给@senderle打了一个复选标记,因为对不同解决方案的大O运行时间进行了很好的研究.@marcin还提醒我要包含一个__eq__方法 - 但是继承自的方法dict会很好用.这就是我实现所有内容的方式 - 欢迎基于此代码的进一步意见和建议:
class FrozenCounter(collections.Counter):
# Edit: A previous version of this code included a __slots__ definition.
# But, from the Python documentation: "When …在Python中,当你想使用列表作为某些字典的键时,你可以把它们变成元组,这些元组是不可变的,因此是可以删除的.
>>> a = {}
>>> a[tuple(list_1)] = some_value
>>> a[tuple(list_2)] = some_other_value
当您想要将set对象用作某些字典的键时,也会发生同样的情况- 您可以构建一个冷冻集,这也是不可变的,因此是可清除的.
>>> a = {}
>>> a[frozenset(set_1)] = some_value
>>> a[frozenset(set_2)] = some_other_value
但似乎对于字典没有等价物.
我想到的第一个想法(最终发现它很糟糕)是str(some_dict)用作关键.但是,字典总是使用不同的散列函数,因此相同字典的字符串可能不同.
是否有任何解决方法称为良好实践,或者是否有人有其他想法如何使用类字典对象作为其他词典的键？