为大输入加速此 Python 代码

Question

我写这个 Python 代码是为了在一个更大的项目中做一个特定的计算，它适用于 N 的较小值，但它不能很好地扩展到大值，甚至虽然我运行它花了几个小时来收集数据，但我想知道是否有办法加快速度

import numpy as np

def FillArray(arr):
while(0 in arr):
    ind1 = np.random.randint(0,N)
    if(arr[ind1]==0):
        if(ind1==0):
            arr[ind1] = 1
            arr[ind1+1] = 2
        elif(ind1==len(arr)-1):
            arr[ind1] = 1
            arr[ind1-1] = 2
        else:
            arr[ind1] = 1
            arr[ind1+1] = 2
            arr[ind1-1] = 2
    else:
        continue
return arr

N=50000

dist = []
for i in range(1000):
    arr = [0 for x in range(N)]
    dist.append(Fillarr(arr).count(2))

对于 N = 50,000，目前在我的计算机上一次迭代填充数组需要一分钟多一点的时间。所以如果我想模拟这个，比方说，模拟 1000 次，需要很多小时。我可以做些什么来加快速度吗？

编辑 1：我忘了提及它的实际作用。我有一个长度为 N 的列表，我通过在每个条目中加入零来初始化它。然后我在 0 和 N 之间选择一个运行dom 数字，如果列表的索引为零，我将其替换为 1 并将其相邻索引替换为 2 表示它们没有被 1 填充，但不能再次填充。我一直这样做，直到我用 1 和 2 填充整个列表，然后我计算有多少条目包含 2 这是此计算的结果。因此我想知道如果我用这个约束运行domly 填充一个数组，有多少条目将不会被填充。

很明显，我并不是说这是找到这个数字的最有效方法，所以我希望如果不能加速这段代码，也许有更好的替代方法。

Answer 1

正如@SylvainLeroux 在评论中指出的那样，当您开始运行时，尝试通过绘制随机位置并希望它为零来找到您要更改的零的方法会变慢的零。简单地从你知道将要为零的那些中选择将大大加快它。像

def faster(N):
    # pad on each side
    arr = np.zeros(N+2)
    arr[0] = arr[-1] = -1 # ignore edges
    while True:
        # zeros left
        zero_locations = np.where(arr == 0)[0]
        if not len(zero_locations):
            break # we're done
        np.random.shuffle(zero_locations)
        for zloc in zero_locations:
            if arr[zloc] == 0:
                arr[zloc-1:zloc+2] = [2, 1, 2]
    return arr[1:-1] # remove edges

会快很多（我的旧笔记本上的时间）：

>>> %timeit faster(50000)
10 loops, best of 3: 105 ms per loop
>>> %time [(faster(50000) == 2).sum() for i in range(1000)]
CPU times: user 1min 46s, sys: 4 ms, total: 1min 46s
Wall time: 1min 46s

我们可以通过矢量化更多计算来改进这一点，但根据您的限制，这可能已经足够了。

Answer 2

首先，我会将问题从三变量重新表述为双变量。您正在做的是在随机点 k 将长度为 N 的向量分成两个较小的向量。

假设您从零向量开始，然后将“1”放在随机选择的 k 处，然后从那里取两个较小的零向量 - [0..k-2] 和 [k+2。 .N-1]。不需要第三状态。重复该过程直到精疲力尽 - 当您只剩下包含一个元素的向量时。

即使在我的带有 Pythonista 的 iPad mini 上，使用 recusion 也相当快。

import numpy as np
from random import randint

def SplitArray(l, r):
    while(l < r):
        k = randint(l, r)
        arr[k] = 1
        return SplitArray(l, k-2) + [k] + SplitArray(k+2, r)
    return []

N = 50000
L = 1000
dist=np.zeros(L)
for i in xrange(L):
    arr = [0 for x in xrange(N)]
    SplitArray(0, N-1)
    dist[i] = arr.count(0)

print dist, np.mean(dist), np.std(dist)

但是，如果你想让它变得非常快，那么双变量问题可以非常有效和自然地编码为位数组，而不是将 1 和 0 存储在整数数组中，或者更糟糕的是将浮点数存储在 numpy 数组中。位操作应该很快，在某些情况下您可以轻松地接近机器级别的速度。

沿线的一些事情：（这是一个想法而不是最佳代码）

from bitarray import BitArray
from random import randint
import numpy as np

def SplitArray(l, r):
    while(l < r):
        k = randint(l, r)           
        arr.set_bit(k)
        return SplitArray(l, k-2) + [k] + SplitArray(k+2, r)
    return []

def count0(ba):
    i = 0
    for n in xrange(1, N):
        if ba.get_bit(n) == 0:
            i += 1
    return i

N = 50000
L = 1000
dist = np.zeros(L)
for i in xrange(L):
    arr = BitArray(N, initialize = 0)
    SplitArray(1, N)    
    dist[i] = count0(arr)

print np.mean(dist), np.std(dist)

使用bitarray

解决方案收敛得很好，所以也许花半个小时寻找解析解决方案就不需要整个 MC 练习了吗？

为大输入加速此 Python 代码

Speeding up this Python code for large input

python

arrays

loops