x10*_*x10 31 python hash complexity-theory dictionary
我正在编写一个简单的Python程序.
我的程序似乎受到字典线性访问的影响,即使算法是二次的,它的运行时间也呈指数级增长.
我使用字典来记忆值.这似乎是一个瓶颈.
我正在散列的值是点的元组.每个点是:(x,y),0 <= x,y <= 50
字典中的每个键是:2-5点的元组:((x1,y1),(x2,y2),(x3, Y3),(X4,Y4))
密钥的读取次数比写入次数多很多次.
我是否认为python dicts受到这些输入的线性访问时间的影响？
据我所知,集合保证了对数访问时间.
如何在Python中使用集合(或类似的东西)模拟dicts？
编辑根据请求,这是memoization函数的(简化)版本:
def memoize(fun):
memoized = {}
def memo(*args):
key = args
if not key in memoized:
memoized[key] = fun(*args)
return memoized[key]
return memo
Yac*_*oby 52
请参阅时间复杂性.python dict是一个hashmap,因此如果hash函数不好并导致大量冲突,则最坏的情况是O(n).然而,这是一种非常罕见的情况,其中添加的每个项目都具有相同的哈希值,因此被添加到同一个链中,对于主要的Python实现来说极不可能.平均时间复杂度当然是O(1).
最好的方法是检查并查看正在使用的对象的哈希值.的CPython的字典使用INT PyObject_Hash(的PyObject*O) ,其是相当于hash(o).
经过快速检查后,我还没有设法找到两个散列为相同值的元组,这表明查找是O(1)
l = []
for x in range(0, 50):
for y in range(0, 50):
if hash((x,y)) in l:
print "Fail: ", (x,y)
l.append(hash((x,y)))
print "Test Finished"
CodePad(24小时可用)
你不正确。dict访问不太可能是您的问题。几乎可以肯定是 O(1)，除非您有一些非常奇怪的输入或非常糟糕的散列函数。粘贴一些来自您的应用程序的示例代码，以便更好地进行诊断。
如果您提供示例代码和数据，则更容易提出建议。
访问字典不太可能成为问题，因为该操作平均为O(1)，并且 O(N) 分摊最坏情况。内置散列函数可能会遇到数据冲突。如果您在使用内置散列函数时遇到问题，您可以提供自己的散列函数。
Python 的字典实现通过要求键对象提供“散列”函数将字典查找的平均复杂度降低到 O(1)。这样的散列函数获取键对象中的信息并使用它生成一个整数，称为散列值。然后使用该散列值来确定应将此（键、值）对放入哪个“存储桶”。
您可以覆盖类中的 __hash__ 方法来实现自定义哈希函数，如下所示：
def __hash__(self):
return hash(str(self))
根据您的数据的实际情况，您可能能够提出一个比标准函数具有更少冲突的更快的哈希函数。然而，这不太可能。有关更多信息，请参阅字典键上的Python Wiki 页面。
要回答您的具体问题：
问题 1：
“我是否正确地认为 Python dicts 会受到此类输入的线性访问时间的影响？”
A1：如果你的意思是平均查找时间是 O(N)，其中 N 是字典中的条目数，那么你很可能是错的。如果您是正确的，Python 社区非常想知道您在什么情况下是正确的，以便可以减轻或至少警告问题。“示例”代码和“简化”代码都没有用。请显示重现问题的实际代码和数据。代码应该配备诸如每个 P 的 dict 项目数和 dict 访问次数之类的东西，其中 P 是键中的点数 (2 <= P <= 5)
Q2：
“据我所知，集合保证了对数访问时间。如何在 Python 中使用集合（或类似的东西）模拟字典？”
A2：集合在什么情况下有保证的对数访问时间？Python 实现没有这样的保证。最近的 CPython 版本实际上使用了一个精简的 dict 实现（只有键，没有值），所以期望是平均 O(1) 行为。你怎么能用任何语言的集合或类似的东西来模拟字典？简短回答：如果您想要任何超出dict.has_key(key).