python - 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 级别工作，因此比编写自己的 完成得快得多>Python 中的 for 循环。

但是，如果您要将第二个代码段翻译为 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