做作业的时候无意中发现了算法速度的奇怪不一致。 这是具有相同功能的 2 个版本的代码,但有 1 个不同:在第一个版本中,我使用 3 次数组生成器来过滤一些数组,在第二个版本中,我使用 1 个 for 循环和 3 个 if 语句来完成相同的过滤工作。
所以,这是第一个版本的代码:
def kth_order_statistic(array, k):
pivot = (array[0] + array[len(array) - 1]) // 2
l = [x for x in array if x < pivot]
m = [x for x in array if x == pivot]
r = [x for x in array if x > pivot]
if k <= len(l):
return kth_order_statistic(l, k)
elif k > len(l) + len(m):
return kth_order_statistic(r, k - len(l) - len(m))
else:
return m[0]
这里是第二个版本的代码:
def kth_order_statistic2(array, k):
pivot = (array[0] + array[len(array) - 1]) // 2
l = []
m = []
r = []
for x in array:
if x < pivot:
l.append(x)
elif x > pivot:
r.append(x)
else:
m.append(x)
if k <= len(l):
return kth_order_statistic2(l, k)
elif k > len(l) + len(m):
return kth_order_statistic2(r, k - len(l) - len(m))
else:
return m[0]
第一个版本的 IPython 输出:
In [4]: %%timeit
...: A = range(100000)
...: shuffle(A)
...: k = randint(1, len(A)-1)
...: order_statisctic(A, k)
...:
10 loops, best of 3: 120 ms per loop
对于第二个版本:
In [5]: %%timeit
...: A = range(100000)
...: shuffle(A)
...: k = randint(1, len(A)-1)
...: kth_order_statistic2(A, k)
...:
10 loops, best of 3: 169 ms per loop
那么为什么第一个版本比第二个版本快?我还使用 filter() 函数而不是数组生成器制作了第三个版本,它比第二个版本慢(每个循环有 218 毫秒)
最佳答案
使用简单的 for
比 list comprehesion
更快。它快了将近 2 倍。检查以下结果:
使用列表理解
:58 usec
moin@moin-pc:~$ python -m timeit "[i for i in range(1000)]"
10000 loops, best of 3: 58 usec per loop
使用 for
循环:37.1 usec
moin@moin-pc:~$ python -m timeit "for i in range(1000): i"
10000 loops, best of 3: 37.1 usec per loop
但在您的情况下,for
比列表理解花费更多时间,这并不是因为您的 for 循环很慢。但是由于 .append()
,您在代码中使用。
在 for
循环中使用 append()
:114 usec
moin@moin-pc:~$ python -m timeit "my_list = []" "for i in range(1000): my_list.append(i)"
10000 loops, best of 3: 114 usec per loop
这清楚地表明 .append()
花费的时间是 for
循环的两倍。
但是,将“list.append”存储在不同的变量中
:69.3 usec
moin@moin-pc:~$ python -m timeit "my_list = []; append = my_list.append" "for i in range(1000): append(i)"
10000 loops, best of 3: 69.3 usec per loop
在上述比较中,与最后一种情况相比,性能有了巨大的提高,结果与列表理解
的结果相当。这意味着,不是每次都调用 my_list.append()
,而是可以通过将函数的引用存储在另一个变量中来提高性能,即 append_func = my_list.append
并使使用该变量 append_func(i)
的调用。
这也证明,调用存储在变量中的类的函数比直接使用类的对象调用函数更快。
谢谢 Stefan通知最后一个案例。
关于python - 比较列表理解和显式循环(3 个数组生成器比 1 个 for 循环更快),我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/39518899/