如何让最艰难的部分在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 = 1亿,l = 12,k = 12可以终止？

Answer 1

编辑:使用在块中生成随机数和多处理的组合,我在跛脚上在6分钟内完成了1亿次试验,总共比原始代码快12倍.

块生成随机数的单个过程

以下代码在我的机器上运行速度提高了3倍(15秒对45秒).主要变化是将所有随机数生成移出主循环.如果它iters是如此之大以至于你没有内存来做那个,那么你可以运行一个嵌套循环并生成尽可能大的块并冲洗并重复 - 我已经将下面的代码放在下面编辑你的问题.

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()非常罕见,现在你接触它的方式非常少.

N=100在下面的程序中设置运行1亿次.使用程序的当前值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

多个过程

编辑:这是一个"令人尴尬的并行"问题,因此您可以在多个处理器上运行模拟.一个简单的方法是使用一组工人.但请注意,在每个过程中设置随机种子非常重要.否则,您可能会冒险让每个进程使用相同的随机数集(请参阅此处,我假设这适用于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的核心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)