访问Python字典的时间复杂度

Question

我正在写一个简单的Python程序。

我的程序在使用字典时似乎遇到了线性访问的问题，虽然算法是二次的，但运行时间却呈指数增长。
我用字典来存储一些值，这似乎成了一个瓶颈。

我正在哈希的值是一些点的元组。每个点的格式是：(x,y)，其中0 <= x,y <= 50。
字典中的每个键是一个包含2到5个点的元组：((x1,y1),(x2,y2),(x3,y3),(x4,y4))。

这些键被读取的次数远远超过写入的次数。

我是否正确理解，Python的字典在处理这样的输入时会有线性访问时间的问题？

据我所知，集合的访问时间是有保证的对数级别。
我该如何在Python中用集合（或类似的东西）来模拟字典呢？

编辑 根据请求，这里是一个（简化版的）记忆化函数：

def memoize(fun):
    memoized = {}
    def memo(*args):
        key = args
        if not key in memoized:
            memoized[key] = fun(*args)
        return memoized[key]
    return memo

Answer 1

如果你能提供一些示例代码和数据，给出建议会更容易。

访问字典一般不会有问题，因为这个操作的平均时间复杂度是 O(1)，最坏情况下是O(N)。有可能是你数据中的内置哈希函数出现了冲突。如果你在使用内置哈希函数时遇到问题，可以自己提供一个。

Python的字典实现通过要求键对象提供一个“哈希”函数，将字典查找的平均复杂度降低到O(1)。这个哈希函数会把键对象中的信息转化为一个整数，称为哈希值。然后，这个哈希值会用来决定这个（键，值）对应该放入哪个“桶”中。

你可以在你的类中重写 __hash__ 方法，来实现一个自定义的哈希函数，像这样：

def __hash__(self):    
    return hash(str(self))

根据你的数据实际情况，你可能能想出一个比标准函数更快的哈希函数，冲突更少。不过，这种可能性不大。想了解更多信息，可以查看 Python字典键的维基页面。

Answer 2

你说的不对。dict 的访问速度一般不会是你遇到的问题。它的速度几乎可以认为是 O(1)，除非你有一些非常奇怪的输入或者使用了很糟糕的哈希函数。如果你能贴一些你应用里的示例代码，可能能更好地诊断问题。

Answer 3

可以参考一下 时间复杂度 的内容。Python 的字典其实是一个哈希表，最糟糕的情况是 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 小时）