Python - "in"语句搜索对象列表缓慢

Question

我希望有人能解释为什么搜索对象引用列表比搜索普通列表要慢得多。这是使用python“in”关键字来搜索我认为以“C编译器”速度运行的。我认为列表只是对象引用(指针)的数组，因此搜索应该非常快。这两个列表在内存中都是 412236 字节。

普通列表(搜索需要 0.000 秒):

alist = ['a' for x in range(100000)]
if 'b' in alist:
    print("Found")

对象引用列表(搜索需要 0.469 !! 秒):

class Spam:
    pass
spamlist = [Spam() for x in range(100000)]
if Spam() in spamlist:
    print("Found")

---

编辑:所以显然这与旧式类的开销比新式类更多有关。我的脚本只有 400 个对象，现在可以轻松地处理多达 10000 个对象，只需让我的所有类都继承自“对象”类。就在我以为我知道 Python 的时候!。

我以前读过关于新样式与旧样式的文章，但从未提到旧样式类可以比新样式类慢 100 倍。在对象实例列表中搜索特定实例的最佳方法是什么？
1. 继续使用“in”语句，但要确保所有类都是新样式。
2. 使用“is”语句执行一些其他类型的搜索，例如:

[obj for obj in spamlist if obj is target]

3。其他更 Pythonic 的方式？

Answer 1

这主要是由于旧式类的不同的特殊方法查找机制。

>>> timeit.timeit("Spam() in l", """
... # Old-style
... class Spam: pass
... l = [Spam() for i in xrange(100000)]""", number=10)
3.0454677856675403
>>> timeit.timeit("Spam() in l", """
... # New-style
... class Spam(object): pass
... l = [Spam() for i in xrange(100000)]""", number=10)
0.05137817007346257
>>> timeit.timeit("'a' in l", 'l = ["b" for i in xrange(100000)]', number=10)
0.03013876870841159

如您所见，Spam 继承自 object 的版本运行得更快，几乎与使用字符串的情况一样快。

列表的 in 运算符使用 == 来比较项目是否相等。 == 被定义为按顺序尝试对象的 __eq__ 方法、它们的 __cmp__ 方法和指针比较。

对于老式类，这是以简单但缓慢的方式实现的。 Python 必须在每个实例的字典以及每个实例的类和父类(super class)的字典中实际查找 __eq__ 和 __cmp__ 方法。 __coerce__ 也被查找，作为 3 路比较过程的一部分。当这些方法实际上都不存在时，这就像 12 dict 查找只是为了进行指针比较。除了 dict 查找之外，还有很多其他开销，我实际上不确定该过程的哪些方面最耗时，但可以说该过程比它可能的成本更高。

对于内置类型和新型类，情况会更好。首先，Python 不会在实例的字典上寻找特殊方法。这节省了一些 dict 查找并启用下一部分。其次，类型对象具有对应于 Python 级特殊方法的 C 级函数指针。当在 C 中实现或不存在特殊方法时，相应的函数指针允许 Python 完全跳过方法查找过程。这意味着在 new-style 的情况下，Python 可以快速检测到它应该直接跳到指针比较。

至于你应该做什么，我建议使用 in 和新式类。如果您发现此操作正在成为瓶颈，但您需要旧式类以实现向后兼容性，则 any(x is y for y in l) 的运行速度比 x in 快约 20 倍l:

>>> timeit.timeit('x in l', '''
... class Foo: pass
... x = Foo(); l = [Foo()] * 100000''', number=10)
2.8618816054721936
>>> timeit.timeit('any(x is y for y in l)', '''
... class Foo: pass
... x = Foo(); l = [Foo()] * 100000''', number=10)
0.12331640524583776