python - 我将如何改善/使其运行更快？

This question is unlikely to help any future visitors; it is only relevant to a small geographic area, a specific moment in time, or an extraordinarily narrow situation that is not generally applicable to the worldwide audience of the internet. For help making this question more broadly applicable, visit the help center。

7年前关闭。

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

令n为大于1的整数，并且s（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，我们有超完美数。

编写一个程序，查找并打印所有（m，k）个完美数字
m <= MAXM，小于或等于（<=）MAXNUM。如果是整数
属于上述程序的特殊类别之一
应该打印一条相关的消息。另外，程序必须打印
发现了许多不同的（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有多困难？

最佳答案

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

如果不将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的根，因此一旦测试除数达到平方根，您就知道已经找到并添加了所有除数，然后就完成了。任何进一步的循环都是徒劳的浪费工作。

所以让我们考虑

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

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

但是我们仍然可以通过使用twalberg suggested，使用s(n)的素因式分解来计算除数和来改善这一点。

首先，如果n是素数，则n = p^k的除数是n，并且除数之和很容易计算（几何和的封闭式为

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

但是否使用它或将1, p, p², ..., p^k的k+1次幂除以p并不重要）。

接下来，如果n具有素数n = p^k * m和p，使得m不除p，则

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

一种简单的分解方法是将m的每个除数d编写为n形式，其中d = p^a * g不除p。然后g必须除以p^a，即p^k，并且a <= k必须除以g。相反，对于每个m和每个0 <= a <= k除以g的每个元素，m是p^a * g的除数。因此，我们可以布置n的除数（其中n是1 = g_1 < g_2 < ... < g_r = m的除数）

 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

每行的总和为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

尝试除法使用p^a * s(m)的第二大素数系数（如果n是合成的）或n的最大素数的平方根，取较大者。对于尝试使用n的最大除数，它有最坏的情况，对于素数可以达到此除数，但是对于大多数复合材料，除法会更早停止。

如果没有方便的质数列表，可以将n**0.5行替换为for p in primes: [上限并不重要，因为如果大于for p in xrange(2, n):则永远不会达到此上限]，并得到一个分解速度太慢。（但是，即使避免使用大于2的试验除数，也可以很容易地加快速度，也就是使用列表n**0.5-最适合作为除数的生成器，甚至可以跳过3的倍数（除3之外），从而获得更多收益， [2] + [3,5,7...]，如果您需要其他一些小的素数。）

现在，这有所帮助，但是计算所有[2,3] + [5,7, 11,13, 17,19, ...]的除数总和仍需要n <= MAXNUM的时间（我尚未分析，这可能也是一个上限，或者Ω(MAXNUM^1.5 / log MAXNUM)仍然可能是一个下限，对数因子很少会产生很大的变化（除了恒定因子以外）。

而且您不只计算一次除数之和（在您的示例中，在调查12时再次计算MAXNUM^1.5，在调查28时再次计算s(56)，在调查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)（如果是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

关于python - 我将如何改善/使其运行更快？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/17279480/

上一篇：R 优化问题

下一篇：google-drive-api - 找不到文件错误Google Drive API

相关文章：

c - "more threads"是否意味着更快的速度？

python - 需要一个测试用例，其中给定的最小硬币数量代码在 python 中失败了吗？

android - 长时间运行的 XML 解析方法中的奇怪行为

python - 使用 python 验证一个 shapefile 是一个 shapefile (fiona, ogr)

python - 在 Python 中计算位置数据的 K 均值聚类

python - 从 Celery 任务登录到 Sentry

performance - 构建高性能计算系统

php - 如何优化 PHP 代码以上传 SQL 转储

c++ - 你会如何优化这个功能？

python - 值错误: ('Series lengths must match to compare' when Using Pandas Style