避免（或加速）Python 中的大循环？

Question

我正在使用 SageMath 执行一些数学计算，有一次我有一个 for 循环，如下所示：

uni = {}
end = (l[idx]^(e[idx] - 1)) * (l[idx] + 1) # where end in my case is about 2013265922, 
                                           # but can also be much much larger too.
for count in range(0, end):
    i = randint(1, 303325737249669131)     # this executes very fast in Sage
    if i in uni:
        uni[i] += 1
    else:
        uni[i] = 1

所以基本上，我想在给定范围内创建大量随机整数，检查数字是否已经在字典中，如果是，则增加其计数，如果不是，则将其初始化为 1。但是，循环花费了如此长的时间以至于它没有在合理的时间内完成，这不是因为循环内的操作很复杂，而是因为要执行大量的迭代。因此，我想问一下有什么方法可以避免（或加快）这种在Python?

中的循环

Answer 1

不用 low-level 魔法可以实现的最大加速是使用 defaultdict，即

uni = defaultdict(int)
for count in range(0, end):
    i = randint(1, 303325737249669131)     # this executes very fast in Sage
    uni[i] += 1

如果您使用的是 python2，请将 range 更改为 xrange。

除此之外 - 我很确定它接近 python 的极限。循环是

生成随机整数（在没有静态类型的情况下尽可能优化）
正在计算哈希值
正在更新字典。 defaultdict if-else 分支被分解为更优化的代码
不时地，malloc 调用调整字典大小 - 这很快（考虑到无法为字典预分配内存）

Answer 2

我分析了您的代码（为此使用 cProfile）并且花费的绝大部分时间都花在了为循环的每次迭代调用的 randint 函数中。

我建议您使用 numpy 随机数生成库对循环进行矢量化，然后单次调用计数器 class 以提取频率计数。

import numpy.random
import numpy
from collections import Counter

assert 303325737249669131 < 18446744073709551615 # limit for uint64
numbers = numpy.random.randint(low=0, high=303325737249669131, size=end, 
dtype=numpy.uint64)
frequency = Counter(numbers)

对于 1000000 次迭代的循环（比您建议的要小），我观察到从 6 秒减少到大约 1 秒。因此，即使这样，您也不能期望计算时间减少超过一个数量级。

你可能认为将所有值保存在内存中的数组效率低下，并且可能导致计算结束前内存耗尽。但是，由于 "end" 的值与随机整数的范围相比较小，因此您将记录碰撞的速率较低，因此完整数组的内存成本不会比存储字典大很多.但是，如果这成为问题，您可能希望分批执行计算。本着这种精神，您可能还希望使用多处理设施在多个 CPU 甚至多台机器上分配计算（但如果您选择这样做，请注意网络成本）。

避免（或加速）Python 中的大循环？

Avoiding (or speeding up) large loop in Python?

python

loops

for-loop

sage