python - 我将如何改进/使这个运行更快？

Question

我是 Python 的初学者，试图变得更好，我偶然发现了以下练习：

令 n 为大于 1 的整数，s(n) 为 n 的除数之和。例如，

s(12) 1 + 2 + 3 + 4 + 6 + 12 = 28

还，

s(s(12)) = s(28) = 1 + 2 + 4 + 7 + 14 + 28 = 56

和

s(s(s(12))) = s(56) = 1 + 2 + 4 + 7 + 8 + 14 + 28 + 56 = 120

我们使用符号：

s^1(n) = s(n)
s^2(n) = s(s(n))
s^3(n) = s(s(s(n)))
s^ m (n) = s(s(. . .s(n) . . .)), m times

对于存在正整数 k 的整数 n，使得

 s^m(n) = k * n

被称为 (m, k)-完美，例如 12 是 (3, 10)-完美，因为 s^3(12) = s(s(s(12))) = 120 = 10 * 12

特殊类别：

对于 m =1，我们有多重完美数

对于 m = 1 和 k = 2 存在上述一种特殊情况，它们被称为完美数。

对于 m = 2 和 k = 2，我们有超完美数。

编写一个程序，找出并打印所有小于或等于 (<=) MAXNUM 的 m <= MAXM 的完全数。如果整数属于上述特殊类别之一，则程序应打印相关消息。此外，程序必须打印找到了多少个不同的 (m, k) 完美数字，它们占测试数字的百分比，不同对 (m, k) 的出现次数，以及每对的次数发现了特殊类别（完美数字也被视为多重完美）。

这是我的代码：

import time
start_time = time.time()
def s(n):
    tsum = 0
    i = 1
    con = n
    while i < con:
        if n % i == 0:
            temp = n / i
            tsum += i
            if temp != i:
                tsum += temp 
            con = temp
        i += 1                    
    return tsum
#MAXM
#MAXNUM

i = 2

perc = 0
perc1 = 0
perf = 0
multperf = 0
supperf = 0
while i <= MAXNUM:
    pert = perc1
    num = i
    for m in xrange(1, MAXM + 1):        
        tsum = s(num)                
        if tsum % i == 0:            
            perc1 += 1
            k = tsum / i            
            mes = "%d is a (%d-%d)-perfect number" % (i, m, k)
            if m == 1:
                multperf += 1
                if k == 2:
                    perf += 1 
                    print mes + ", that is a perfect number"
                else:
                    print mes + ", that is a multiperfect number"               
            elif m == 2 and k == 2:
                supperf += 1
                print mes + ", that is a superperfect number"
            else:
                print mes        
        num = tsum        
    i += 1
    if pert != perc1: perc += 1
print "Found %d distinct (m-k)-perfect numbers (%.5f per cent of %d ) in %d occurrences" % (
perc, float(perc) / MAXNUM * 100, MAXNUM, perc1)
print "Found %d perfect numbers" % perf
print "Found %d multiperfect numbers (including perfect numbers)" % multperf
print "Found %d superperfect numbers" % supperf  
print time.time() - start_time, "seconds"

它工作正常，但我想要关于如何让它运行得更快的建议。例如使用起来是否更快

I = 1
while I <= MAXM:
    …..
    I += 1

代替

for I in xrange(1, MAXM + 1)

如果不是将 s(n) 定义为函数，而是将代码放入主程序中会更好吗？等等。如果您有什么建议让我了解如何使程序运行得更快，我将不胜感激。还有一件事，最初这个练习要求程序是用 C 语言编写的（我不知道），用 Python 编写了这个，把它变成 C 语言会有多困难？

Answer 1

最大的改进来自使用更好的算法。像

如果不是将代码定义s(n)为函数，而是将代码放入主程序中会更好吗？

或者是否使用while循环而不是没有太大区别，因此在达到算法改进至少很难for i in xrange(1, MAXM + 1):实现的状态之前不应考虑。

因此，让我们看一下您的算法，以及我们如何在不关心while循环或for迭代是否更快等小事的情况下大幅改进它。

def s(n):
    tsum = 0
    i = 1
    con = n
    while i < con:
        if n % i == 0:
            temp = n / i
            tsum += i
            if temp != i:
                tsum += temp 
            con = temp
        i += 1                    
    return tsum

这已经包含了一个好主意，您知道 的除数是n成对出现的，一旦您找到这对中的较小者，就将两个除数相加。您甚至可以正确处理正方形。

它适用于像 120 这样的数字：当你找到除数 2 时，将停止条件设置为 60，当你找到 3 时，设置为 40，...，当你找到 8 时，你将它设置为 15，当你找到10，你把它设置为12，然后你只有除以11，当i增加到12时停止。不错。

n但是当是 素数时，它的效果就不那么好了，那么con永远不会被设置为小于 的值n，并且您需要一直迭代到n找到除数之和。n = 2*p对于带有素数的形式的数字也很糟糕p，然后循环到n/2，或n = 3*p( n/3，除非p = 2) 等。

根据素数定理，不超过的素数x是渐近的x/log x（log自然对数在哪里），并且你有一个下限

Ω(MAXNUM² / log MAXNUM)

仅用于计算素数的除数和。这不好。

由于您已经考虑n成对d和的除数n/d，请注意两者中较小的一个（暂时忽略是平方的d = n/d情况n）小于 的平方根n，因此一旦测试除数达到平方根，您知道你已经找到并添加了所有除数，你就完成了。任何进一步的循环都是徒劳的浪费工作。

所以让我们考虑

def s(n):
    tsum = 0
    root = int(n**0.5)  # floor of the square root of n, at least for small enough n
    i = 1
    while i < root + 1:
        if n % i == 0:
            tsum += i + n/i
        i += 1
    # check whether n is a square, if it is, we have added root twice
    if root*root == n:
        tsum -= root
    return tsum

作为第一个改进。然后你总是循环到平方根，计算s(n)为1 <= n <= MAXNUMis Θ(MAXNUM^1.5)。这已经是相当大的进步了。（当然，您必须计算迭代除数和，并且s(n)可以大于MAXNUMsome n <= MAXNUM，因此您无法从中推断出O(MAXM * MAXNUM^1.5)整个算法的复杂度界限。但s(n)不能大得多，因此复杂度可以'也不会更糟。）

但是我们仍然可以通过使用twalberg 建议的方法来改进这一点，使用 的素数分解n来计算除数。

首先，如果n = p^k是素幂，则 的除数n是1, p, p², ..., p^k，除数和很容易计算（几何和的封闭公式是

(p^(k+1) - 1) / (p - 1)

但是否使用它或增加划分的k+1权力并不重要）。pn

接下来，如果n = p^k * m有一个素数p和一个不除的m这样，那么pm

s(n) = s(p^k) * s(m)

查看分解的一种简单方法是将 的每个除数写成where does not divided的形式。则必除，即，必除。相反，对于每一个除法，都是 的除数。所以我们可以列出（的除数在哪里）的除数nd = p^a * gpgp^ap^ka <= kgm0 <= a <= kgmp^a * gnn1 = g_1 < g_2 < ... < g_r = mm

 1*g_1   1*g_2  ...  1*g_r
 p*g_1   p*g_2  ...  p*g_r
  :        :           :
p^k*g_1 p^k*g_2 ... p^k*g_r

并且每一行的总和是p^a * s(m)。

如果我们手边有一个素数列表，我们可以写

def s(n):
    tsum = 1
    for p in primes:
        d = 1
        # divide out all factors p of n
        while n % p == 0:
            n = n//p
            d = p*d + 1
        tsum *= d
        if p*p > n: # n = 1, or n is prime
            break
    if n > 1:       # one last prime factor to account for
        tsum *= 1 + n
    return tsum

试除法采用n[if niscomposite] 的第二大素因数或 的最大素因数的平方根n，以较大者为准。对于 的最大除数，它有一个最坏情况界限，n**0.5对于素数，它达到了这个界限，但对于大多数复合数，除法停止得更早。

如果我们手边没有一个素数列表，我们可以for p in primes:用for p in xrange(2, n):[上限不重要，因为如果它大于n**0.5] 就永远不会达到该行，并得到一个不太慢的因式分解。（但是通过避免大于 2 的试验除数可以很容易地加快速度，即使用一个列表[2] + [3,5,7...]- 最好作为生成器 - 对于除数，甚至通过跳过 3 的倍数（3 除外），[2,3] + [5,7, 11,13, 17,19, ...]如果你需要更多的小素数。）

现在，这有帮助，但是计算所有的除数总和n <= MAXNUM仍然需要Ω(MAXNUM^1.5 / log MAXNUM)时间（我没有分析过，这也可能是一个上限，或者MAXNUM^1.5仍然可能是一个下限，无论如何，对数因子很少有很大的不同[超出常数因子]）。

并且您不止一次地计算了很多除数（在您的示例中，您s(56)在调查 12 时计算，在调查 28 时再次计算，在调查 56 时再次计算）。为了减轻这种影响，记忆s(n)将是一个好主意。然后你只需要计算s(n)一次。

现在我们已经用空间换了时间，所以我们可以使用更好的算法一次性计算所有的除数和1 <= n <= MAXNUM，具有更好的时间复杂度（以及更小的常数因子）。我们可以直接只标记倍数，而不是尝试每个足够小的（素数）数是否除以n，从而避免所有留下余数的除法 - 这是绝大多数。

简单的方法是

def divisorSums(n):
    dsums = [0] + [1]*n
    for k in xrange(2, n+1):
        for m in xrange(k, n+1, k):
            dsums[m] += k
    return dsums

具有O(n * log n)时间复杂度。您可以通过使用素数分解来做得更好（O(n * log log n)复杂性），但该方法有点复杂，我现在不添加它，也许稍后再添加。

然后，您可以使用所有除数和的列表来查找s(n)if n <= MAXNUM，并使用上述实现来计算大于[或者您可能希望将值记忆到更大的限制]的值s(n)的除数。MAXNUM

dsums = divisorSums(MAXNUM)
def memo_s(n):
    if n <= MAXNUM:
        return dsums[n]
    return s(n)

---

这还不算太破旧，

Found 414 distinct (m-k)-perfect numbers (0.10350 per cent of 400000 ) in 496 occurrences
Found 4 perfect numbers
Found 8 multiperfect numbers (including perfect numbers)
Found 7 superperfect numbers
12.709428072 seconds

为了

import time
start_time = time.time()


def s(n):
    tsum = 1
    for p in xrange(2,n):
        d = 1
        # divide out all factors p of n
        while n % p == 0:
            n = n//p
            d = p*d + 1
        tsum *= d
        if p*p > n: # n = 1, or n is prime
            break
    if n > 1:       # one last prime factor to account for
        tsum *= 1 + n
    return tsum
def divisorSums(n):
    dsums = [0] + [1]*n
    for k in xrange(2, n+1):
        for m in xrange(k, n+1, k):
            dsums[m] += k
    return dsums

MAXM = 6
MAXNUM = 400000

dsums = divisorSums(MAXNUM)
def memo_s(n):
    if n <= MAXNUM:
        return dsums[n]
    return s(n)

i = 2

perc = 0
perc1 = 0
perf = 0
multperf = 0
supperf = 0
while i <= MAXNUM:
    pert = perc1
    num = i
    for m in xrange(1, MAXM + 1):
        tsum = memo_s(num)
        if tsum % i == 0:
            perc1 += 1
            k = tsum / i
            mes = "%d is a (%d-%d)-perfect number" % (i, m, k)
            if m == 1:
                multperf += 1
                if k == 2:
                    perf += 1
                    print mes + ", that is a perfect number"
                else:
                    print mes + ", that is a multiperfect number"
            elif m == 2 and k == 2:
                supperf += 1
                print mes + ", that is a superperfect number"
            else:
                print mes
        num = tsum
    i += 1
    if pert != perc1: perc += 1
print "Found %d distinct (m-k)-perfect numbers (%.5f per cent of %d ) in %d occurrences" % (
perc, float(perc) / MAXNUM * 100, MAXNUM, perc1)
print "Found %d perfect numbers" % perf
print "Found %d multiperfect numbers (including perfect numbers)" % multperf
print "Found %d superperfect numbers" % supperf
print time.time() - start_time, "seconds"

通过记住所需的除数和n > MAXNUM：

d = {}
for i in xrange(1, MAXNUM+1):
    d[i] = dsums[i]
def memo_s(n):
    if n in d:
        return d[n]
    else:
        t = s(n)
        d[n] = t
        return t

时间下降到

3.33684396744 seconds

Answer 2

from functools import lru_cache

...

@lru_cache
def s(n):
    ...

应该使它显着更快。

[更新] 哦，对不起，这是根据文档在 3.2 中添加的。但任何缓存都可以。请参阅 是否有一个装饰器可以简单地缓存函数返回值？