Python - “in”语句搜索对象列表的速度很慢

我希望有人能解释为什么搜索对象引用列表比搜索普通列表慢得多。这是使用 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")

---

Edit: So apparently this has something to do with old-style classes having way more overhead than new style classes. My script that was bogging down with only 400 objects can now easily handle up to 10000 objects simply by making all my classes inherit from the "object" class. Just when I thought I knew Python!.

I've read about new-style vs old-style before but it was never mentioned that old-style classes can be up to 100x slower than new style ones. What is the best way to search a list of object instances for a particular instance?
1. Keep using the "in" statement but make sure all classes are new style.
2. Perform some other type of search using the "is" statement like:

[obj for obj in spamlist if obj is target]

3.还有其他更Pythonic的方式吗？

这主要是由于不同的特殊方法查找机制旧式课程.

>>> 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运行速度要快得多，几乎与字符串的情况一样快。

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

对于旧式类，这是以一种简单但缓慢的方式实现的。 Python 必须真正寻找__eq__ and __cmp__每个实例的字典以及每个实例的类和超类的字典中的方法。__coerce__作为三向比较过程的一部分，也会被查找。当这些方法实际上都不存在时，就需要进行 12 次字典查找才能进行指针比较。除了字典查找之外，还有很多其他开销，我实际上不确定该过程的哪些方面是最耗时的，但足以说该过程比它可能的更昂贵。

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

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