更高效的Python for循环（3个冗余环路）在迭代

Question

我想实现下面的代码的较大值：

def foo(n, p): 
    for i in range(1,n): 
     for j in range(1,n): 
      for k in range(1,n): 
       if ((n-j)*i*k)==(j*(n-i)*(n-k)): 
        p=p-11 

但n为将要接近10^10个值，这使得严重效率低下。事实上，即使当n = 1000时，这也是很慢的。

有没有办法通过压缩for循环来加速这个过程，或者也许有办法在没有循环的情况下做到这一点？

Answer 1

我要带数学方法与计算机科学方法。减少这些循环显然有一些有趣的问题，但数学方法可能会带来几乎相同的事情，并带有一个小错误。

我想知道是否有这个序列的封闭形式公式，因为这总是比任何循环都快！在您提供的OEIS链接，在公式中，有人提供的

x*(1+5*x+11*x^2+x^3+6*x^4)/(1-x)^3/(1+x)^2 

的“经验”生成函数我会得到一个位的“经验”的一部分。但是因为这是一个多项式的比率，所以如果您阅读了关于生成函数的工作方式，那么获得封闭形式的解决方案相当容易。我可以代数添加到我的答案，如果这种做法最终你喜欢被什么东西，但现在，就让我们直切公式：

def empirical(n): 
    return ((-1)**n * (-1.5*n + 2.5)) + \ 
       (3.0*n**2 - 4.5*n + 3.5) 

这是非常干净和简单。这有多准确？那么，我检查了前500个值。这两个函数通常排队完美，但有些时候empirical夸大了真正的序列偶尔次：

correct empirical pct_diff 
1   1  1.0 0.000000 
2   6  6.0 0.000000 
3  19  19.0 0.000000 
4  30  30.0 0.000000 
5  61  61.0 0.000000 
6  78  78.0 0.000000 
7  127  127.0 0.000000 
8  150  150.0 0.000000 
9  217  217.0 0.000000 
10  246  246.0 0.000000 
11  331  331.0 0.000000 
12  366  366.0 0.000000 
13  469  469.0 0.000000 
14  510  510.0 0.000000 
15  625  631.0 0.009600* 
16  678  678.0 0.000000 
17  817  817.0 0.000000 
18  870  870.0 0.000000 
19  1027  1027.0 0.000000 
20  1080  1086.0 0.005556* 
21  1261  1261.0 0.000000 
22  1326  1326.0 0.000000 

这偶尔的差异几乎总是小于1％。现在，我不能保证，这种模式是要保持n = 10**10（即，经验几乎总是正确的，有轻微的高估，每隔一段时间），但检查出OEIS页面上的其他评论：

Ceva定理用于从天真计数中扣除消失区域。对于n奇数，第一个推导是n = 15，对于n偶数，n = 20。

15和20碰巧是第一个与empirical分歧！所以似乎大部分时间实证生成函数都是正确的（“天真计数”？），但是当必须进行推论时，它在某些点上是一个上界。这是进入特定领域的领域，我不太了解Ceva的定理，以确切地知道何时以及如何进行这些推理 - 所以恐怕我无法改进这种封闭形式的上限，因为我拥有它以上。

你原来的问题想测试10 ** 10。所以现在做int(empirical(10**10))瞬间：

299999999939999956992 

这可能是完全正确的，或上限这是非常，非常接近真正的答案。

我知道这是一个“替代”解决方案，但希望它是一个信息转移。这就像有人要求你找到（10 ** 10）斐波那契数。你可以做循环，但如果存在一个封闭形式的公式，使用它！

Answer 2

操作(n-j)*i*k=j*(n-i)*(n-k)。我们有j=n/(((n-i)*(n-k))/(i*k) + 1)和j应该是1和n-1之间的整数，所以：

def foo(n, p): 
    for i in range(1,n): 
     for k in range(1,n): 
      j=n/(((n-i)*(n-k))/(i*k) + 1) 
      if n%(((n-i)*(n-k))/(i*k) + 1) == 0 and j > 0 and j < n: 
       p=p-11 

这降低了从O（N 3）复杂度为O（N²）