比较标准列表理解与NumPy的运行时间
我正在尝试使用NumPy来查看在Python中如何以及在哪里使用通用列表解析。 这是我用于此实验的标准编码问题。
Find the sum of all the multiples of 3 or 5 below 1000000.
我写了三个函数来计算这个数字。
def fA(M):
sum = 0
for x in range(M):
if x % 3 == 0 or x % 5 == 0:
sum += x
return sum
def fB(M):
multiples_3 = range(0, M, 3)
multiples_5 = range(0, M, 5)
multiples_15 = range(0, M, 15)
return sum(multiples_3) + sum(multiples_5) - sum(multiples_15)
def fC(M):
arr = np.arange(M)
return np.sum(arr[np.logical_or(arr % 3 == 0, arr % 5 == 0)])
我首先做了一个快速的完整性检查，看看这三个函数产生了相同的答案。
然后我用timeit来比较三个函数的运行时间。
%timeit -n 100 fA(1000000)
100 loops, best of 3: 182 ms per loop
%timeit -n 100 fB(1000000)
100 loops, best of 3: 14.4 ms per loop
%timeit -n 100 fC(1000000)
100 loops, best of 3: 44 ms per loop
fA是最慢的也就不足为奇了。 但为什么fB比fC好得多呢？ 有没有更好的方法来使用NumPy来计算这个答案？
我不认为大小是一个问题。 事实上，如果我将1e6更改为1e9，与fB相比，fC会变得更慢。
fB比fC快得多，因为fC不等于fB的NumPy。 fC是fA的NumPy等价物。 这是fB的NumPy等价物：
def fD(M):
multiples_3 = np.arange(0, M, 3)
multiples_5 = np.arange(0, M, 5)
multiples_15 = np.arange(0, M, 15)
return multiples_3.sum() + multiples_5.sum() - multiples_15.sum()
它运行速度更快：
In [4]: timeit fB(1000000)
100 loops, best of 3: 9.96 ms per loop
In [5]: timeit fD(1000000)
1000 loops, best of 3: 637 µs per loop
在fB您正在构建您想要的确切倍数的范围。 它们的尺寸从3变小到5到15，因此每个构造的构造时间比前一个构造的时间要少，在构建完成后，您只需要总和并进行一些算术运算。
在fC你正在构造一个100000个元素的数组，其大小并不像你所做的两个模比较那么重要，它必须查看数组中的每一个元素。 这占了fC执行时间的大部分（大约90％）。
你只是真的在那里使用numpy来生成一个数组。 如果您尝试对数组执行操作，而不是在列表或元组上执行操作，则会看到更大的差异。 关于这个问题，请看下面代码中的函数fD，它只计算每个范围应该有多少倍数，然后计算它们的总和，而不是生成数组。 实际上，如果你运行下面的代码片段，你会看到时间在M的函数中如何变化。另外，fC分解为M> = 100000.我无法告诉你为什么。
import numpy as np
from time import time
def fA(M):
sum = 0
for x in range(M):
if x % 3 == 0 or x % 5 == 0:
sum += x
return sum
def fB(M):
multiples_3 = range(0, M, 3)
multiples_5 = range(0, M, 5)
multiples_15 = range(0, M, 15)
return sum(multiples_3) + sum(multiples_5) - sum(multiples_15)
def fC(M):
arr = np.arange(M)
return np.sum(arr[np.logical_or(arr % 3 == 0, arr % 5 == 0)])
def fD(M):
return sum_mult(M,3)+sum_mult(M,5)-sum_mult(M,15)
def sum_mult(M,n):
instances=(M-1)/n
check=len(range(n,M,n))
return (n*instances*(instances+1))/2
for x in range(5,20):
print "*"*20
M=2**x
print M
answers=[]
T=[]
for f in (fA,fB,fC,fD):
ts=time()
answers.append(f(M))
for i in range(20):
f(M)
T.append(time()-ts)
if not all([x==answers[0] for x in answers]):
print "Warning! Answers do not match!",answers
print T
上一篇: Comparing runtime of standard list comprehension vs. NumPy
下一篇: Why is numpy much slower than matlab on a digitize example?