为什么在使用用户定义的对象作为键时，在Python中查找字典总是比较慢？ [英] Why is dictionary lookup in Python always slower when using user defined objects as keys?

问题描述

我注意到，当我使用用户定义的对象(覆盖__hash__方法)作为我在Python中的词典的关键字时，查找时间至少增加了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__方法的覆盖，则性能与默认对象的性能相同

有没有办法在避免这种性能损失的同时仍然实现自定义的哈希计算？

CPython

自定义类的默认推荐答案__hash__实现是用C编写的，并使用对象的内存地址。因此，它不必从对象访问任何东西，并且可以非常快地完成，因为它只是CPU中的一个整数操作，如果真的是这样的话。

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

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

它必须读取self的属性a，我认为在本例中将调用object.__getattribute__(self, 'a')，这将在__dict__中查找‘a’的值。这已经涉及到计算hash('a')和查找它。然后，返回值将传递给hash。

---

回答附加问题：

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

任何访问对象属性的操作都将比不需要访问属性的实现慢，但您可以通过使用__slots__或为类实现高度优化的C扩展来加快属性访问速度。

然而，还有另一个问题：这真的是一个问题吗？我真的不敢相信应用程序会因为慢__hash__而变慢。__hash__应该仍然很快，除非词典有数万亿个条目，但之后，其他一切都会变慢，并要求进行更大的更改...

---

我做了一些测试，必须进行更正。在这种情况下，使用__slots__不会有任何帮助。我的测试实际上显示，在CPython3.7中，当使用__slots__时，上面的类会稍微变慢。

这篇关于为什么在使用用户定义的对象作为键时，在Python中查找字典总是比较慢？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！