在较大的迭代值时更高效的 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 循环来加快速度，或者有没有一种方法可以完全不使用 for 循环？

Answer 1

操纵(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³) 降低到 O(n²)

Answer 2

我将采用数学方法与计算机科学方法。减少那些 for 循环显然有一些有趣的问题，但数学方法可能会让你得到几乎相同的东西，但有一个小错误。

我想知道这个序列是否有一个封闭形式的公式，因为它总是比任何循环都快！在你提供的OEISlink中，FORMULA下有人提供了"empirical"生成函数

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

我稍后会谈到 "empirical" 部分。但是因为这是多项式的比率，如果您了解生成函数的工作原理，就很容易得到一个封闭形式的解决方案。如果这种方法最终成为您喜欢的东西，我可以将代数添加到我的答案中，但现在，让我们直接切入公式：

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's Theorem is used to deduct vanishing regions from the naive count. The first deduction is at n=15 for n odd and n=20 for n even.

15和20恰好是empirical的第一个分歧！所以看起来经验生成函数在大多数时候都是正确的（"naive count"？），但在某些地方当必须进行推论时它是一个上限。这进入了特定领域的领域，我对 Ceva 定理的了解还不够，无法确切地了解何时以及如何进行这些推论——所以我担心我无法改进这个封闭形式的上限，因为我有它以上。

你原来的问题是想测试10**10。所以现在立即int(empirical(10**10))：

299999999939999956992

这要么是完全正确的，要么是一个非常非常接近真实答案的上限。

我知道这是一个 "alternative" 的解决方案，但希望它是一个信息转移。这就像有人要你找到第 (10**10) 个斐波那契数。您可以使用循环，但如果存在闭式公式，请使用它！

在较大的迭代值时更高效的 python for 循环（3 个冗余循环）

More efficient python for loop (3 redundant loops) at large values of iterations

python

performance

for-loop

largenumber