当使用用户定义的对象作为键时,为什么Python中的字典查找总是较慢？

Question

我注意到当我使用用户定义的对象(覆盖__hash__方法)作为Python中我的dicts的键时,查找时间至少增加了5倍.

即使我使用非常基本的哈希方法,例如在以下示例中,也会观察到此行为:

class A:
    def __init__(self, a):
        self.a = a
    def __hash__(self):
        return hash(self.a)
    def __eq__(self, other):
        if not isinstance(other, A):
            return NotImplemented
        return (self.a == other.a and self.__class__ == 
                other.__class__)

# get an instance of class A
mya = A(42)
# define dict
d1={mya:[1,2], 'foo':[3,4]}

如果我通过两个不同的键进行访问,我会发现性能存在显着差异

%timeit d1['foo']

结果约为100 ns.而

%timeit d1[mya]

结果约为600 ns.

如果我删除覆盖__hash__和__eq__方法,性能与默认对象的级别相同

有没有办法避免性能损失并仍然实现自定义哈希计算？

Answer 1

__hash__自定义类的默认CPython 实现是用C编写的,并使用对象的内存地址.因此,它不必从对象访问绝对的anthing并且可以非常快速地完成,因为它只是CPU中的单个整数操作,即使这样.

__hash__示例中的"非常基本" 并不像看起来那么简单:

def __hash__(self):
    return hash(self.a)

这必须读取属性a的self,我会说在这种情况下将调用object.__getattribute__(self, 'a'),并会寻找的"A"的值__dict__.这已经涉及到计算hash('a')和查找.然后,返回的值将传递给hash.

要回答其他问题:

有没有办法实现一个__hash__返回可预测值的更快的方法,我的意思是,在每次运行时不会随机计算对象的内存地址？

访问对象属性的任何内容都将比不需要访问属性的实现慢,但您可以通过使用__slots__或实现类的高度优化的C扩展来更快地进行属性访问.

然而,还有另一个问题:这真的是一个问题吗？我真的不相信应用程序因为速度慢而变慢__hash__.__hash__应该仍然相当快,除非字典有数万亿条目,但是,其他一切都会变慢,并要求更大的变化......

我做了一些测试,不得不进行修正.__slots__在这种情况下,使用根本不会有所帮助.我的测试实际上表明,在CPython 3.7中,上面的类在使用时变得稍慢__slots__.