Python 中 2 线性搜索之间的效率差异

Question

我有一个关于列表搜索时效率差异的问题。为什么这两者有区别？

test_list= [2,4,6,8,10,12,14,16,18,20,22,24,26,28,30,32,34,36,38,40,42,44,46,48,50]

第一个-

def linearSearch(A,x):
    if x in A:
        return True
    return False

第二个-

def linearSearch_2(A,x):
    for element in A:
        if element == x:
            return True
    return False

测试它们

%timeit linearSearch(test_list, 3)
438 ns ± 5.86 ns per loop (mean ± std. dev. of 7 runs, 1000000 loops each)

%timeit linearSearch_2(test_list, 3)
1.28 µs ± 7.05 ns per loop (mean ± std. dev. of 7 runs, 1000000 loops each)

当我使用更大的列表时，差异仍然存在。这两种方法有什么本质区别吗？

Answer 1

虽然理论上这些应该同时完成，但 Python 的 in 运算符被编写为在原始 C 级别工作，因此比您自己编写要快得多for-loop 在 Python.

但是，如果您要将第二个片段翻译成 C，那么它的表现会优于 Python 中的第一个片段，因为 C 的级别要低得多，所以跑得更快。

注：

第一个函数几乎没用，因为它等同于：

def linearSearch(A,x):
    return x in A

现在很清楚，无论何时调用它，您都可以直接编写：x in A 来产生相同的结果！

出于兴趣，我在 C 中写了第二个片段，但为了让时间更加夸张，让它完成整个事情 1000000 次：

#include <stdio.h>
#include <time.h>

void main(){
    clock_t begin = clock();
    for (int s = 0; s < 1000000; s++){
        int x = 3;
        int a[25] = {2,4,6,8,10,12,14,16,18,20,22,24,26,28,30,32,34,36,38,40,42,44,46,48,50};
        for (int i = 0; i < 25; i++){
            if (i == x) break;
        }
    }
    printf("completed in %f secs\n", (double)(clock() - begin) / CLOCKS_PER_SEC);
}

输出：

completed in 0.021514 secs

而我在 Python 中对你的第一个片段的修改版本：

import time
start = time.time()

for _ in range(1000000):
    x = 3
    l = [2,4,6,8,10,12,14,16,18,20,22,24,26,28,30,32,34,36,38,40,42,44,46,48,50]
    if x in l:
        continue;

print("completed in", time.time() - start, "seconds")

输出：

completed in 1.1042814254760742 seconds

Python 中 2 线性搜索之间的效率差异

Efficiency difference between 2 linear line search in Python

python

coding-efficiency