python - 加快Python求和速度

Question

我有一个很大的列表，其中 listn1 中有数字 n1。如果被乘数不在另一个列表 listn2(具有特定特征的质数)中，并且乘积低于最大值 max_n，我想将每个数字的所有倍数相加。大多数情况下，被乘数小于 10，但最多可达 100,000。到目前为止我的代码如下所示:

s = 0
for n1 in listn1:
    s += sum(n1 * i for i in range(1, 1 + max_n // n1) if i not in listn2)

问题:这种方法很慢。计算 listn1 和 listn2 需要几秒钟的时间，所以我知道有超过一百万个数字需要添加。但我昨天晚上就开始求和了，今天早上还在运行。

有没有一种Python式的方法来加速这个求和？

Answer 1

我有 2 条建议给你。

首先，您不需要在每次迭代时将 i 与 n1 相乘。您可以更换

s += sum(n1 * i for i in range(1, 1 + max_n // n1) if i not in listn2)

与

s += n1 * sum(i for i in range(1, 1 + max_n // n1) if i not in listn2)

它们完全一样。

其次，如果没有 if i not in listn2 条件，您将得到一个简单的求和:

sum(i for i in range(1, 1 + max_n // n1)

这与 sum([1, 2, 3, 4, 5, 6, 7, 8, ..., (max_n//n1)]) 相同，并且等于 (max_n//n1) * (1 + max_n//n1)/2。举个简单的例子，看看this .

要处理if i not in listn2条件，如果您的listn2较小，您可以对listn2而不是listn1<求和。

所以，求 listn1 的总和并减去 listn2 中的项目:

def sum_until(l, max):
    return sum([x for x in l if x < max])

listn2 = list(set(listn2))

for n1 in listn1:
    finish = max_n // n1
    s += n1 * (finish * (finish + 1) / 2 - sum_until(listn2, finish)) 

编辑:

我猜 NumPy 求和会更快。使 listn2 成为 numpy 数组:

import numpy as np

listn2 = np.array(list(set(listn2))) 

并使用这个sum_until函数:

def sum_until(listn2, max):
    l = listn2[np.where(listn2 <= max)]
    return int(np.sum(l))