减少 python 嵌套循环的执行时间

Question

我编写了以下用于数值模拟的简单代码。我的编程水平是初学者。

import numpy as np
import time as t
start = t.time()
r=10**-8
alpha=60*(np.pi/180)
gamma_sa=58.6*10**-3 
gamma_sw=25*10**-3
gamma_pa=153*10**-3
gamma_pw=110*10**-3
gamma_aw=72.5*10**-3    
kt= 1.38*10**-23*293 
i=0
##############variables########################
omega=0 
zeta= (3/2 )*np.pi*r**3 *10**-3
dt=0.01 
std=np.sqrt(2*kt*zeta*dt)
for k in range(1,2):
    beta_i=[]
    j_i=[]
    B=[]
    time=np.arange(dt,10,dt)
    Fs_i=[]
    dE_i=[]
    j=0
    for i in range (len(time)):
        j_i.append(j)
        beta=(90-j)
        beta1=(90-j)*(np.pi/180)
        Fs=0
        Ft = (np.random.randn()*std*np.sqrt(dt))/zeta
        beta_i.append(beta)
        del(beta)
        j=(j+Ft+Fs)%360
    MSD=[]
    diff_i=[]
    tau_i=[]
    for l in range(1,len(time)):
        tau=l*dt
        tau_i.append(tau)
        del(tau)
        for i in range(1,(len(time)-l)):
            diff=(j_i[l+i]-j_i[i])**2*dt
            diff_i.append(diff)
        MSD_j=np.sum(diff_i)/np.max(time)
        MSD.append(MSD_j)
        del(MSD_j) 
    np.savetxt("MSD_no_fs%d"%k, MSD)
    np.savetxt("Tau_no_fs%d"%k,tau_i)
print(t.time() - start)

代码运行成功，执行时间为~38s。但是，如果我将 dt 从 .01 增加到 .001，它似乎会花费无限时间，因为脚本保持运行ning 没有错误。有人可以解释执行时间对 dt、k 范围和时间范围的依赖性以及任何有效的方法吗？因为我想要 dt=.0001、krange (0,100,dt) 和时间 (dt,100,dt)。这方面的最佳做法是什么？

PS：8 GB 内存和 3.31 GHz v6 处理器。

Answer 1

time的长度与dt的大小成反比。在每种情况下，您都有一个基于 time 长度的嵌套循环。只要该循环是您最热门的代码，您的代码就会经历二次增长 (O(n**2))。通过 0.01 从 0.01 步进到 10 意味着（足够接近）100 个元素的长度，以及约 10,000 个单位的内循环工作。用 0.001 从 0.001 到 10 做同样的事情意味着约 1000 个元素，约 1,000,000 个工作单元，增加了 100 倍。

从 38 秒的起点来看，这已经很极端了；即使内存不是问题，您也会看到 3800 秒（一个多小时）。内存是一个问题；你的内部循环重复 appends 到 diff_i，所以你要存储 ~10,000 floats（在 CPython x64 构建中似乎每个占用 24 个字节, 再加上 list 中引用的 8 个字节），这意味着您占用了大约三分之一 MB 的 RAM。使用 0.001 的 dt，最终接近 32 MB，而 0.0001 将使您达到 3.2 GB。即使你有那么多 RAM，这也意味着你不再从 CPU 缓存中获益很多东西，这可能会比直接 CPU 成本所表明的更慢。

您的代码很少利用 numpy 的功能，并且可能会收紧很多。这样做会节省大量内存，并允许将大部分工作推到单个函数调用中，在 C 中执行循环，运行比快得多 Python 解释器.

对于最简单的改进，取diff_i。在循环甚至运行之前，您就确切地知道它将有多少元素，并且计算可以简化为简单的数组操作，甚至在外循环开始之前将 j_i 转换为 numpy 数组，并替换在 j_i 上进行一系列简单计算的循环直接将 diff_i 作为 numpy 数组生成，根本没有 Python 级循环。

我还没有测试过这个（在这台机器上没有 numpy），但是一个粗略的尝试是在 j_i 被填充后立即转换：

j_i = np.array(j_i)

并将 diff_i 声明为：

diff_i = np.array()

然后替换：

for i in range(1,(len(time)-l)):
    diff=(j_i[l+i]-j_i[i])**2*dt
    diff_i.append(diff)

与：

new_diff = (j_i[l+1:] - j_i[:-(l+1)]) ** 2 * dt
diff_i = np.concatenate((diff_i, new_diff))

减少 python 嵌套循环的执行时间

Reducing execution time in python for nested loops

python

numpy

nested-loops