Ada*_*lis 15 python optimization dictionary
我第一次在这里发帖,所以希望我以正确的方式问我的问题,
将元素添加到Python字典后,是否可以让Python告诉您添加该元素是否导致了冲突？(在找到放置元素的位置之前,碰撞解决策略探测了多少个位置？)
我的问题是:我使用字典作为更大项目的一部分,经过大量的分析后,我发现代码中最慢的部分是处理使用字典实现的稀疏距离矩阵.
我正在使用的键是Python对象的ID,它们是唯一的整数,所以我知道它们都散列为不同的值.但是将它们放在字典中仍然可能导致原则上的冲突.我不相信字典冲突会减慢我的程序速度,但我想从我的查询中删除它们.
因此,例如,给出以下字典:
d = {}
for i in xrange(15000):
d[random.randint(15000000, 18000000)] = 0
你能让Python告诉你创建它时发生了多少次碰撞吗？
我的实际代码与应用程序纠缠在一起,但上面的代码生成了一个与我正在使用的字典非常相似的字典.
重复:我不认为碰撞会减慢我的代码速度,我只是想通过显示我的字典没有多次碰撞来消除这种可能性.
谢谢你的帮助.
编辑:实现@Winston Ewert解决方案的一些代码:
n = 1500
global collision_count
collision_count = 0
class Foo():
def __eq__(self, other):
global collision_count
collision_count += 1
return id(self) == id(other)
def __hash__(self):
#return id(self) # @John Machin: yes, I know!
return 1
objects = [Foo() for i in xrange(n)]
d = {}
for o in objects:
d[o] = 1
print collision_count
请注意,当您__eq__在类上定义时,TypeError: unhashable instance如果您还没有定义__hash__函数,Python会为您提供.
它没有像我预期的那样运行.如果你有这个__hash__功能return 1,那么你会得到大量的碰撞,正如预期的那样(我的系统上n = 1500的1125560次碰撞).但是return id(self),有0次碰撞.
任何人都知道为什么这会说0次碰撞？
编辑: 我可能已经想到了这一点.
是因为__eq__只有__hash__在两个对象的值相同时调用,而不是它们的"嘎吱嘎吱的版本"(如@John Machin所说)？
简短回答:
您不能使用随机整数作为dict键来模拟使用对象ID作为dict键.它们具有不同的散列函数.
碰撞确实发生了."具有独特的东西意味着没有碰撞"对于"thingy"的几个值是错误的.
你不应该担心碰撞.
答案很长:
从阅读源代码得出的一些解释:
dict实现为2**i个条目的表,其中i是整数.
dicts不超过2/3满.因此对于15000个键,我必须是15和2**我是32768.
当0是没有定义的类的实例随心所欲__hash__(),这是不正确的散列(O)== ID(O) .由于地址可能在低位3或4位中具有零,因此通过将地址右旋4位来构造散列.查看源文件Objects/object.c,函数_Py_HashPointer
如果在低位中存在大量零,那将是一个问题,因为要访问大小为2**i的表(例如32768),哈希值(通常远大于该值)必须嘎吱嘎吱地拟合,通过获取散列值的低阶i(例如15)位,可以非常简单快速地完成这一过程.
因此,碰撞是不可避免的.
然而,这不是引起恐慌的原因.散列值的剩余位被计入下一次探测的位置计算中.需要第三次等待探测的可能性应该相当小,特别是因为dict永远不会超过2/3满.通过计算第一次和后续探针的槽的便宜成本来减轻多个探针的成本.
下面的代码是一个简单的实验,说明了上述大多数讨论.它假定dict在达到其最大大小后随机访问.使用Python2.7.1,它显示了15000个对象的大约2000次冲突(13.3%).
无论如何,最重要的是你应该把注意力转移到其他地方.碰撞不是你的问题,除非你已经为你的对象获得了一些非常不正常的获取内存的方法.你应该看看你是如何使用dicts的,例如use k in d或try/except,not d.has_key(k).考虑访问一个dict,d[(x, y)]而不是访问两个级别d[x][y].如果您需要帮助,请提出单独的问题.
在Python 2.6上测试后更新:
直到Python 2.7才引入旋转地址; 请参阅此错误报告以获得全面的讨论和基准.基本结论是恕我直言仍然有效,并可以通过"更新,如果你可以"增加.
>>> n = 15000
>>> i = 0
>>> while 2 ** i / 1.5 < n:
... i += 1
...
>>> print i, 2 ** i, int(2 ** i / 1.5)
15 32768 21845
>>> probe_mask = 2 ** i - 1
>>> print hex(probe_mask)
0x7fff
>>> class Foo(object):
... pass
...
>>> olist = [Foo() for j in xrange(n)]
>>> hashes = [hash(o) for o in olist]
>>> print len(set(hashes))
15000
>>> probes = [h & probe_mask for h in hashes]
>>> print len(set(probes))
12997
>>>
这个想法实际上没有用,请参阅问题中的讨论.
快速浏览python的C实现表明,解决冲突的代码不会计算或存储冲突的数量.
但是,它会调用PyObject_RichCompareBool键来检查它们是否匹配.这意味着__eq__将在每次碰撞时调用该键.
所以:
将键替换__eq__为在调用计数器时定义和递增计数器的对象.由于跳转到python进行比较所涉及的开销,这将会变慢.但是,它应该让您了解发生了多少次碰撞.
确保使用不同的对象作为键,否则python将采用快捷方式,因为对象始终等于自身.此外,请确保对象散列为与原始键相同的值.