循环加速

Question

我在学校有一个项目，我必须编写一个高度递归的程序：

S = 0
T = 0
P = 3.1415926535897932384626433832795028841971693993751058209749445923078164062862089986280348253421170679
x = 10000000000000
for i in range(0, x):
    S += 1 / (-1) ** i / (2 * i + 1)
    if i == x-1:
        T = S

X 以 10 倍变大。x=100000000 的运行已经需要 26 秒，x=10000000000 的运行大约需要 3 小时。你知道我怎样才能加快速度吗？

Answer 1

我看不出你能在这里做很多事情，因为你的循环有很多迭代。如果你想让你的循环运行更快，你需要做的更少。

我认为你的部分没有理由

if i == x-1:
    T = S

因为它在 for 循环的最后一次迭代中只有运行s。删除该部分并将其写在循环下，以便在循环完成后它会运行。您现在已经保存了 10000000000 次 i 值的检查。

for i in range(0, x):
    S += 1 / (-1) ** i / (2 * i + 1)
T=S

另一种选择是将所有这些都放在对 sum()

的调用中

S = sum(1/(-1)**i / (2 * i + 1) for i in range(x))
T=S

现在一些旁注。

正如您在问题的评论中所指出的，这不是递归。递归是函数调用自身的时候。

其次，您似乎在尝试计算某个常量的最终值。从软件工程的角度来看，您最好用笔和纸计算出最终值在数学上是什么，而不是通过 100 万亿次循环迭代来强行强制计算。如果您确实需要迭代计算一个值（当然，有时您需要这样做）尝试弄清楚您离最终解决方案还有多远，并在非常接近时退出循环。例如，在前 100 次迭代中，您的 S 值变化很大，但接下来的 100 次变化较小，依此类推。在 100 万次迭代之后，是否还有任何显着差异？您可能可以提前退出循环。

Answer 2

考虑到您一遍又一遍地进行相同的计算，您可以通过 numba

并行化来缩短运行时间

from numba import jit
import numpy as np

@jit(nopython=True)
def ex1(start, stop):
    temp = 0
    for i in range(start, stop):
        temp += 1 / (-1) ** i / (2 * i + 1)
    return temp


start = 0
stop = 100000000
block_size = 10000000
temp_sum = 0
loops, remainder = divmod(stop-start, block_size)
for i in range(loops):
    print((i/loops)*100)
    start = i*block_size
    stop = i*block_size + block_size
    # print(start, stop)
    temp_sum += ex1(start, stop)

temp_sum += ex1(loops*block_size, loops*block_size+remainder)

print(temp_sum)

这段代码运行在我的电脑上大约需要 1 秒，而你的代码大约需要 30 秒。这可以通过使用 CUDA 到运行 GPU 上的代码来进一步改进，但这需要更仔细的内存管理。

另外，正如其他人所说，你真的需要做那么多次迭代吗？这段代码的用例是什么？它需要那种准确度吗？

Answer 3

布鲁夫：

替换

1 / (-1) ** i / (2 * i + 1)

与：

(1, -1)[i % 2] / (2 * i + 1)

更新：根据 @PresidentJamesK.Polk 的评论，当您将循环更改为在 range(0, x, 2) 上运行并在循环中使用时，可能会获得额外的性能：

1 / (2 * i + 1) - 1 / (2 * i + 3)

这在 x 为偶数时没问题，但您需要避免或解决 x 为奇数时的情况。除此之外，我们可以通过应用一些代数并用于内循环来获得一些额外的优化：

2 / (3 + i * (8 + 4 * i))

我更新了代码和观察到的结果以包含此方法。

对我来说突出的一件事是在你的内部循环中使用求幂...你所做的只是在 +/- 1 之间切换。你可以改用数组查找来提高循环的速度并删除最初的部门。这是一些时间比较的代码：

from timeit import default_timer as timer

S = 0
N = 10000000

print("original loop:")
start = timer()
for i in range(N):
    S += 1 / (-1) ** i / (2 * i + 1)
end = timer()
print("\tsum: {}\n\telapsed time: {}\n".format(S, end-start))

S = 0

print("original loop remove initial division:")
start = timer()
for i in range(N):
    S += (-1) ** i / (2 * i + 1)
end = timer()
print("\tsum: {}\n\telapsed time: {}\n".format(S, end-start))

S = 0

print("original loop remove exponentiation:")
start = timer()
for i in range(N):
    S += (1, -1)[i % 2] / (2 * i + 1)
end = timer()
print("\tsum: {}\n\telapsed time: {}\n".format(S, end-start))

S = 0

# Take care that N is an even number or handle the case N is odd
print("original loop double step:")
start = timer()
for i in range(0, N, 2):
    S += 2 / (3 + i * (8 + 4 * i))
end = timer()
print("\tsum: {}\n\telapsed time: {}\n".format(S, end-start))

print("condensed loop:")
start = timer()
S = sum(1/(-1)**i / (2 * i + 1) for i in range(N))
end = timer()
print("\tsum: {}\n\telapsed time: {}\n".format(S, end-start))

print("condensed loop remove initial division:")
start = timer()
S = sum((-1)**i / (2 * i + 1) for i in range(N))
end = timer()
print("\tsum: {}\n\telapsed time: {}\n".format(S, end-start))

print("condensed loop remove exponentiation:")
start = timer()
S = sum((1,-1)[i % 2] / (2 * i + 1) for i in range(N))
end = timer()
print("\tsum: {}\n\telapsed time: {}\n".format(S, end-start))

# Take care that N is an even number or handle the case N is odd
print("condensed loop double step:")
start = timer()
S = sum(2 / (3 + i * (8 + 4 * i)) for i in range(0, N, 2))
end = timer()
print("\tsum: {}\n\telapsed time: {}\n".format(S, end-start))

输出：

original loop:
    sum: 0.7853981383974479
    elapsed time: 8.1625896

original loop remove initial division:
    sum: 0.7853981383974479
    elapsed time: 7.968116500000001

original loop remove exponentiation:
    sum: 0.7853981383974479
    elapsed time: 2.9961853000000005

original loop double step:
    sum: 0.7853981383972237
    elapsed time: 1.6683908999999986

condensed loop:
    sum: 0.7853981383974479
    elapsed time: 7.5588762

condensed loop remove initial division:
    sum: 0.7853981383974479
    elapsed time: 7.3124993999999965

condensed loop remove exponentiation:
    sum: 0.7853981383974479
    elapsed time: 2.331167800000003

condensed loop double step:
    sum: 0.7853981383972237
    elapsed time: 1.2696155000000005

最后几位数字有点偏差，但对于用于得出总和的如此多的浮点运算来说，这应该是预料之中的。

循环加速

Speed-up for loop

python

math

for-loop

range