快速观察告诉我们,函数代码中迭代之间存在数据依赖关系。现在,有不同种类的数据依赖关系。您正在查看的数据依赖性的类型是索引依赖性,即在任何迭代中的数据选择取决于先前的迭代计算。这种依赖似乎很难在迭代之间进行追踪,所以本文不是真正的矢量化解决方案。相反,我们会尽量预先计算将在循环中使用的值。基本的想法是在循环中做最低限度的工作。
下面是我们如何能够带预计算进行,因而具有更有效的解决方案的简要说明:
考虑的p
相对较小的形状从哪一行元素被提取基于输入row
,您可以预先选择p
与p[row]
中的所有行。
对于每次迭代,您正在计算一个随机数。你可以用一个随机数组替换它,你可以在循环之前设置它,因此,你也可以预先计算这些随机数。
根据到目前为止的预先计算的值,您将拥有p
中所有行的列索引。请注意,这些列索引将是一个包含所有可能的列索引的大型ndarray,而在我们的代码中,只会根据每次迭代计算选择一个列索引。使用每迭代列索引,您可以增加或减少X0
以获取每次迭代输出。
的实施应该是这样的 -
randarr = np.random.rand(n)
p = np.array([[ 0.499, 0.419, 0.639],
[ 0.099, 0.749, 0.319]])
def play_game_partvect(row,n,randarr,p):
X0 = 100
Y0 = X0 % 3
signvals = 2*(randarr[:,None] < p[row]) - 1
col_idx = (signvals + np.arange(3)) % 3
Y = Y0
currval = X0
out = np.empty(n+1)
out[0] = X0
for j in range(n):
currval = currval + signvals[j,Y]
out[j+1] = currval
Y = col_idx[j,Y]
return out
为针对原始代码验证,你会修改,像这样的原码 -
请注意,因为这代码会预先计算这些随机值,所以这已经可以让您对问题中的代码加速很多。
运行测试和验证输出 -
In [2]: # Inputs
...: n = 1000
...: row = np.random.randint(0,2,(n))
...: randarr = np.random.rand(n)
...: p = np.array([[ 0.499, 0.419, 0.639],
...: [ 0.099, 0.749, 0.319]])
...:
In [3]: np.allclose(play_game_partvect(row,n,randarr,p),play_game(row,n,randarr,p))
Out[3]: True
In [4]: %timeit play_game(row,n,randarr,p)
100 loops, best of 3: 11.6 ms per loop
In [5]: %timeit play_game_partvect(row,n,randarr,p)
1000 loops, best of 3: 1.51 ms per loop
In [6]: # Inputs
...: n = 10000
...: row = np.random.randint(0,2,(n))
...: randarr = np.random.rand(n)
...: p = np.array([[ 0.499, 0.419, 0.639],
...: [ 0.099, 0.749, 0.319]])
...:
In [7]: np.allclose(play_game_partvect(row,n,randarr,p),play_game(row,n,randarr,p))
Out[7]: True
In [8]: %timeit play_game(row,n,randarr,p)
10 loops, best of 3: 116 ms per loop
In [9]: %timeit play_game_partvect(row,n,randarr,p)
100 loops, best of 3: 14.8 ms per loop
因此,我们看到大约7.5x+
的加速,还不错!
如果你使用Python2,它可能会帮助一点点使用'xrange()'而不是'range()'。 – davejagoda
我正在使用Python 3. –