python - 如何让最难的部分在 python 中花费最长的时间

Question

我有一些简单的代码如下。

count =0 
iters = 1000000 
l=10 
k=10 
for i in xrange(iters):
    t = np.random.choice([-1,1],size=l+k-1)
    v = np.random.choice([-1,1], size = l)
    if (not np.convolve(v, t, 'valid').any()):
        count += 1

print count

当我对此进行分析时，我惊讶地发现只有一小部分时间花在了 np.convolve 上，这在理论上应该是最昂贵的部分。有什么方法可以加快其他部分的速度，使 np.convolve 占用大部分时间吗？

我很乐意使用 pypy，但遗憾的是它还不支持 np.convolve。

---

有没有办法让它足够快，iters = 100 million and l = 12, k= 12 可以终止？

Answer 1

编辑:结合在 block 中生成随机数和多处理，我在 latop 上 6 分钟内完成了 1 亿次试验，总共比原始代码快 12 倍。

单进程随机数生成 block

以下代码在我的机器上运行速度提高了 3 倍(15 秒对 45 秒)。主要变化是将所有随机数生成移出主循环。如果 iters 太大以至于您没有足够的内存来执行此操作，那么您可以运行嵌套循环并生成尽可能大的 block 并冲洗并重复 - 我已经在对您的问题进行编辑后，将此代码放在下面。

import numpy as np

count = 0 
iters = 1000000

l=10 
k=10
l0=l+k-1

t = np.random.choice([-1,1], size = l0 * iters)
v = np.random.choice([-1,1], size = l  * iters)

for i in xrange(iters):
    if (not np.convolve(v[(l*i):(l*(i+1))], t[(l0*i):(l0*(i+1))], 'valid').any()):
        count += 1

print count

将原始代码的性能提高约 2% 的另一个小改动是将计算 l+k-1 移到循环之外。顺便说一句，我发现你处理 count 的方式非常有效。因此，例如，count += np.convolve(v[(l*i):(l*(i+1))], t[(l0*i):(l0*(i+1) )], 'valid').any() 然后在最后执行 iters - count 速度较慢。这是因为条件 not...any() 非常罕见，而您现在接触计数的方式很少。

要运行 1 亿次，请在下面的程序中设置 N=100。使用 N=4 的当前值，程序执行需要 1 分钟(计数为 26)。在 l=12、k=12 和 N=4 的情况下，程序只花了一分多钟的时间来执行(计数为 4) .所以你应该看不到半小时的 1 亿。

import numpy as np, time

start = time.clock()

count = 0 
iters = 1000000 # 1million

l=10 
k=10
l0=l+k-1

N = 4 # number of millions

for n in range(N):
    t = np.random.choice([-1,1], size=l0 * iters)
    v = np.random.choice([-1,1], size = l * iters)

    for i in xrange(iters):
        if (not np.convolve(v[(l*i):(l*(i+1))], t[(l0*i):(l0*(i+1))], 'valid').any()):
            count += 1

print (time.clock() - start)

print count

多进程

编辑:这是一个“令人尴尬的并行”问题，因此您可以在多个处理器上运行模拟。一个简单的方法是 using a pool of workers .但请注意 set the random seed in each process 很重要.否则，您可能会冒着让每个进程使用同一组随机数的风险(请参阅 here ，我假设这适用于 numpy 随机数以及基本随机数)。代码如下。

import numpy as np, time
from multiprocessing import Pool

def countconvolve(N):
    np.random.seed() # ensure seed is random

    count = 0 
    iters = 1000000 # 1million

    l=12 
    k=12
    l0=l+k-1

    for n in range(N):
        t = np.random.choice([-1,1], size=l0 * iters)
        v = np.random.choice([-1,1], size = l * iters)

        for i in xrange(iters):
            if (not np.convolve(v[(l*i):(l*(i+1))], t[(l0*i):(l0*(i+1))], 'valid').any()):
                count += 1

    return count

if __name__ == '__main__':
    start = time.clock()

    num_processes = 8
    N = 13

    pool = Pool(processes=num_processes)
    res = pool.map(countconvolve, [N] * num_processes)    
    print res, sum(res)

    print (time.clock() - start)

它在 370 秒内运行了 1.04 亿次模拟，并产生了以下输出

[4, 9, 10, 6, 7, 8, 11, 9] 64

我的笔记本电脑是带有 8GB 内存的 core-i7，所以在 8 核的情况下，我通过并行处理获得了 4 倍的加速。我发现每个进程的内存使用量约为 160MB(峰值更高)。如果您的内核或内存较少，您需要相应地调整程序中的参数。

@moarningsun 建议将数组限制为每个元素 1 个字节，每个进程的内存使用量下降到 60MB。

        t = np.random.choice(np.array([-1,1], dtype=np.int8), size=l0 * iters)
        v = np.random.choice(np.array([-1,1], dtype=np.int8), size = l * iters)