我将如何改进/使这次运行更快？

Question

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

设n是大于1的整数,s(n)是n的d个的和.例如,

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

对于整数n,其中存在正整数k

 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 <= MAXM的所有(m,k) - 完美数字,它们小于或等于(<=)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有多难？

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 <= MAXNUM是?(MAXNUM^1.5).这已经是一个很大的改进.(当然,你必须计算迭代的除数和,并且s(n)可能比MAXNUM某些更大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这样p不分m,然后

s(n) = s(p^k) * s(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除数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

并且每行的总和是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[如果n是复合] 的第二大素数因子或最大素数因子的平方根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)是否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