python - 为什么 python 索引函数执行时间比我自己的线性搜索函数快？

Question

我正在做一个实验，比较索引函数和我自己的线性搜索函数的执行时间。据我了解，Python 为索引函数实现了线性搜索算法，因此执行时间应该大致相同，不是吗？

我自己的搜索功能是这样的

def linearSearch (x,numList,length):      
    n = 0
    for i in range(length):
            n = n + 1
            if numList[i] == x:
                    return i, n
    return -1, n

Answer 1

理解这一点非常重要...O(N) 告诉您没有操作完成的速度。仅仅因为您的实现和 Python 的实现都是 O(N)，这并不意味着它们都将花费相同的时间。

O(N) 告诉您的是，如果一个实现需要 1 秒来处理 100 个项目，那么它可能需要大约 2 秒来处理 200 个项目。换句话说，O(N) 告诉您花在算法上的时间将如何随着输入大小的变化缩放。

---

在这种情况下，python 的搜索将始终胜过您的搜索，因为 python 的搜索在 C(假设是 CPython)中运行，对解释器的开销很小——而您的实现必须做很多事情在“python-space”中查找(相比之下，这非常昂贵)。

一些具有良好 JIT 的 python 实现(例如 pypy)将能够减少这种差异，但我怀疑您是否能够超越优化的内置函数的性能.