在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

你可以在没有低级魔法的情况下获得最大的加速就是使用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分支是更优化代码的因素
• qazxsw poi不时调用调整dict的大小 - 这很快（考虑不能为dict预分配内存）

Answer 2

我分析了你的代码（使用cProfile）和花费的绝大部分时间，是在为循环的每次迭代调用的randint函数中花费的。

我建议你使用numpy随机数生成库来矢量化循环，然后单次调用Counter类来提取频率计数。

malloc

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

您可能认为在内存中保留所有值的数组是低效的，并且可能在计算结束之前导致内存耗尽。但是，由于“结束”的值小于随机整数的范围，因此记录冲突的速率很低，因此完整数组的内存成本并不比存储字典大得多。但是，如果这成为问题，您可能希望分批执行计算。本着这种精神，您可能还希望使用多处理工具在许多CPU甚至许多机器上分配计算（但如果您选择那样，请注意网络成本）。