我有一个关于列表搜索时效率差异的问题。为什么这两者有区别?
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)
当我使用更大的列表时,差异仍然存在。这两种方法有什么根本区别吗?
最佳答案
虽然从理论上讲,这些应该同时完成,但 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
关于python - Python中2线性线搜索的效率差异,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/48355323/