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 必须在每个实例的 dict 以及每个实例的类和超类的 dict 中实际查找__eq__和__cmp__方法。__coerce__也被查找，作为 3 路比较过程的一部分。当这些方法都不存在时，这就像 12 次 dict 查找只是为了进行指针比较。除了 dict 查找之外，还有很多其他开销，我实际上不确定该过程的哪些方面是最耗时的，但可以说该过程比它可能更昂贵就足够了。

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

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