减少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，似乎需要无限的时间，因为脚本一直在运行，没有出现错误。有人能解释一下执行时间对dt、k范围和时间范围的依赖性，以及任何有效的方法吗？因为我想选择dt=.0001，krange(0100，dt(和时间(dt，100，dt(。这方面的最佳实践是什么？

PS:8 gb ram和3.31 GHz v6处理器。

Answer 1

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

从38秒开始，这是非常极端的；即使内存不是问题，你也会看到3800秒(超过一个小时(。内存是一个问题；您的内部循环重复appends到diff_i，因此您将从存储约10000个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))