下面的脚本说明的能力set和frozenset,我想明白了,如果可能的话在collections.MutableSet的子类复制.(顺便说一句,这个功能是不是只是一个怪异set和frozenset:它在Python的单元测试这些类型的主动验证.)
该脚本为类似于集合的对象的几种类型/类中的每一种执行以下步骤:
d其n键是专门检测的整数,用于跟踪__hash__调用方法的次数(其d值是全部None,但这是无关紧要的);__hash__方法的累计次数;dds使用d构造函数的参数创建当前类集类型/类的对象(因此,d's键将成为结果对象的内容,而d将忽略的值);这n是所有类型/类的设置为10 的情况的输出(我在本文末尾给出了完整的代码):
set: 10 10
frozenset: 10 10
Set: 10 20
myset: 10 20
结论很清楚:构造a set或frozensetfrom d不需要调用key 的__hash__方法d,因此在这些构造函数返回后调用计数保持不变.但是,当实例Set或myset创建实例时,情况并非如此d.在每种情况下,似乎每个d's键'都__hash__被调用一次.
我如何修改
myset(见下文),以便运行其构造函数d作为其参数导致不调用d's键'哈希方法？
谢谢!
from sets import Set
from collections import MutableSet
class hash_counting_int(int):
def __init__(self, *args):
self.count = 0
def __hash__(self):
self.count += 1
return int.__hash__(self)
class myset(MutableSet):
def __init__(self, iterable=()):
# The values of self.dictset matter! See further notes below.
self.dictset = dict((item, i) for i, item in enumerate(iterable))
def __bomb(s, *a, **k): raise NotImplementedError
add = discard = __contains__ = __iter__ = __len__ = __bomb
def test_do_not_rehash_dict_keys(thetype, n=1):
d = dict.fromkeys(hash_counting_int(k) for k in xrange(n))
before = sum(elem.count for elem in d)
s = thetype(d)
after = sum(elem.count for elem in d)
return before, after
for t in set, frozenset, Set, myset:
before, after = test_do_not_rehash_dict_keys(t, 10)
print '%s: %d %d' % (t.__name__, before, after)
需要注意的是,值self.dictset是整数,且针对性不一样的(忽略)iterable.values()(在这种情况下iterable.values确实存在)!这是一个尝试(诚然微弱)来表示,即使iterable是一个字典(不必是这种情况)和它的values被忽略,在实际的代码,这个例子是站在对的values的self.dictset是总是显著.这意味着任何基于使用的解决方案self.dictset.update(iterable)仍然必须解决为其键分配适当值的问题,并且再次面临在不调用其__hash__方法的情况下迭代这些键的问题.(此外,基于的解决方案self.dictset.update(iterable)也必须解决正确处理案例的问题,当iterable不是一个合适的论据时self.dictset.update,虽然这个问题不是不可克服的.)
编辑:1)澄清了myset.dictset值的重要性; 2)重命名myset.__bomb__为myset.__bomb.
在最基本的层面上，它会重新哈希键，因为您传递的是 Genexdict而不是映射。
你可以试试这个：
\n\nclass myset(MutableSet):\n def __init__(self, iterable=()):\n self.dictset = {}\n self.dictset.update(iterable)\n\n def __bomb__(s, *a, **k): raise NotImplementedError\n add = discard = __contains__ = __iter__ = __len__ = __bomb__\n输出：
\n\nset: 10 10\nfrozenset: 10 10\nSet: 10 20\nmyset: 10 10\nupdate也接受 Genex，但如果iterable是映射，Python 就足够聪明，不会重新哈希键。事实上，您甚至不必像上面那样单独创建字典。dict(mapping)只要不将其封装在 Genex 中就可以。但您已表示您还想更改与该键关联的值。从某种意义上说，这是可能的，使用dict.fromkeys(mapping, default_val)：在这种情况下，您可以指定一个默认值，并且所有键都将采用该值，但因为您传递了映射，所以不会重新散列任何内容。但我猜这还不够。你似乎想给一个新的和独特的值。
所以你真正的问题是，非常简单，是否可以在不重新散列密钥的情况下为密钥分配新值。当这样表达时，也许你会发现这不可能以简单的方式实现。
\n\n一般来说，没有内置方法可以在不重新散列密钥的情况下更改任意键：值对的值。这有两个原因：
\n\n当为任意键分配值时，Python 需要知道该键及其哈希值，以防发生冲突。Python可以允许您同时传递密钥和预先计算的哈希值，但随后您可能会因为传递不一致的哈希值而真正搞砸事情。因此，对我们所有人来说，最好让 Python 在那里记账。调用的开销__hash__是值得的。（请注意，至少在某些情况下，Python 会缓存哈希 \xe2\x80\x94，在这些情况下，这只是查找缓存的哈希。）
更改值的另一种方法是更改存储在该值所指向的某个特定内存地址处的指针值dict，该指针值已保存并与该键关联。非常简单，这涉及暴露方式的 Python 内部结构。然而，这种方法是下面详细介绍的黑客解决方案的基础。
现在，Python 本身可以通过操作内部来有效地合并两个字典dict，因为 1 在这种情况下无效；保证所有碰撞都已得到处理！但同样，这些内部结构不应该被暴露。对于fromkeys，Python 可能会在内部执行类似于 2 的操作，但默认值始终相同。我可以想象一种情况，Python 会提供另一个关键字扩展来fromkeys接受一个函数不是默认值；它将使用关联的键调用该函数并使用返回的值。那会很酷。但它不存在。
所以我们唯一的希望就是做一些 hackish 的事情。由于我们根本无法在不重新哈希的情况下更改与 dict 键关联的值，因此我们只需将该键与一个可变的关联起来即可值相关联即可。
\n\n>>> a = dict((hash_counting_int(x), []) for x in range(10))\n>>> [x.count for x in a.keys()]\n[1, 1, 1, 1, 1, 1, 1, 1, 1, 1]\n>>> b = dict(a)\n>>> [x.count for x in a.keys()]\n[1, 1, 1, 1, 1, 1, 1, 1, 1, 1]\n>>> for n, v in enumerate(b.itervalues()):\n... v.append(n)\n... \n>>> [x.count for x in a.keys()]\n[1, 1, 1, 1, 1, 1, 1, 1, 1, 1]\n>>> b\n{0: [0], 1: [1], 2: [2], 3: [3], 4: [4], 5: [5], 6: [6], 7: [7], 8: [8], 9: [9]}\n不幸的是，这是唯一可能的解决方案，不涉及破坏 indict的内部结构。我希望你也同意这不是一件好事。