为什么“for ... in ...”比“list.index()”慢得多？

Question

在比较搜索算法在列表中的执行时间时，我得出了一个结论，即 list.index() 比简单的 for in 要快得多。根据 这篇文章，它们都应该是 O(n) 级别的。我在我的测试中得到了以下结果：

简单的解决方案在 3 秒内通过了大约 350 个测试：

def linear_simple(arr):
    for i in range(len(arr)):
        if arr[i] == #my searched value#:
            return i

索引解决方案在3秒内通过了所有2000个测试（实际上即使在2秒内也完成了）：

def linear_index(arr):
    return arr.index( #my searched value# )

所有的测试数组都是随机生成的。测试进行了多次，结果相似。

这意味着 index() 大约快了 9 倍。为什么？ index() 不是像 for in 一样简单地在列表上迭代吗？

- Superluminal

---

list.index 在 C 中被实现和优化。 - Chris_Rands

大O符号是复杂度的一种度量方式（即执行时间或空间使用量如何随输入大小增长），而不是有效执行时间的度量方式，因此两个算法都是O(n)并不意味着它们在相同的输入集上执行所需的时间相同。 - bruno desthuilliers

是的，我知道。但是在相同时间复杂度内很少看到执行时间有9倍差异的情况。 - Superluminal

Answer 1

正如Chris_Rands所说，list.index是用C语言实现的。由于它是编译而不是解释，代码运行得更快。

无论如何，你可以对你的代码进行一些优化：

def linear_simple(arr, value):
    for i, e in enumerate(arr):
        if e == value:
            return i

这段代码在我的电脑上运行更快（但不如list.index快）

- Corentin Limier

---

Python被编译成由虚拟机执行的字节码，它不是“解释性”的（或者你也会把Java描述为“解释性”吗？）。 - bruno desthuilliers

@brunodesthuilliers，两者都是先编译再根据分析器进行编译/解释的，不是吗？此外，我认为他是在说Python是编译而不是解释的。 - Gsk

不是的，我是说Python是解释执行的，当然它比这复杂得多。使用CPython https://en.wikipedia.org/wiki/CPython，字节码被解释执行，而CPython是实际的参考。无论如何，如果Python在执行之前没有编译成机器指令，它将比优化和编译的C函数慢。 - Corentin Limier

@CorentinLimier 如果你选择这条路，那么“机器码”也会被处理器“解释”。问题不在于“编译 vs 解释”，而在于编译成什么，由什么解释，并且可以应用哪些优化（实际上，在由CPython执行的纯Python代码的情况下几乎没有任何优化，但这是另一个问题）。我必须再次问一遍：你会写“Java很慢，因为它是解释性的”吗？ - bruno desthuilliers

我以为那是修辞手法。 - Corentin Limier