python - 优化非大量求和算法

我正在尝试解决this Project Euler question:



我的解决方案:

#returns a list of the divisors of a given number
def Divs(Number):
    Divisors = []

    for i in range(2 , int(Number**0.5) + 1):
        if Number % i == 0:
            Divisors.append(i)

    for q in range(len(Divisors)):
        if Divisors[q] != (Number / Divisors[q]):
            Divisors.append(Number / Divisors[q])

    Divisors.insert(0,1)
    return Divisors

#returns a list of abundant numbers up to and including the limit
def AbList(limit):
    Abundant = []

    for i in range(11,limit + 1):
        if sum(Divs(i)) > i:
            Abundant.append(i)

    return Abundant

#Finds the sum of all positive integers that cannot be written as the
#sum of two abundant numbers...
def AbSum(limit):
    Abundant = AbList(limit)
    NoAbSum = 0
    for i in range(1 , limit):
        AbSum = 0
        x = 0
        for x in Abundant:
            if i - x in Abundant[:i]:
                AbSum = 1
                break
        if AbSum == 0:
            NoAbSum += i
    return NoAbSum

我的3.4 GhZ处理器花了大约15分钟才能解决，我正在寻找更好的方法。我不关心前两个函数，因为它们一起运行只需不到一秒钟的时间。第三个功能是这里的踢脚板。它遍历最大范围内的数字(在本例中为20000左右)，并且每次遍历大量列表，从当前数中减去每个，然后对照大量列表检查答案数字。如果存在匹配项，则循环会中断并尝试使用下一个数字，直到极限为止。

我知道必须有一种更好的方法来做到这一点，但我对编程还是有些陌生。如何加快此算法的速度？

最佳答案

您正在针对每个丰富的数字测试介于1和限制(例如30000)之间的每个数字，因此您正在执行大约30000 * 7428迭代；并且您正在检查结果是否在列表中，这是一个非常慢的操作-它会检查列表中的每个项目，直到找到匹配项!

相反，您应该生成每个数字，该数字是两个丰富数字的总和。最多将需要7428 * 7428次迭代-如果正确执行，则迭代次数会更少(提示:通过确保b始终> = a来避免同时检查a + b和b + a；并且如其他人所建议，请务必停止当总和变得太大时)。将这些数字从limit下面的数字列表中标记出来，并对剩余的数字求和。

换句话说:

[... 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43 ...]

变成

[... 31, 0, 33, 34, 35, 0, 37, 0, 39, 0, 41, 0, 43 ...]

编辑:在玩了几分钟的实现后，我可以自信地说if i - x in Abundant[:i]:是问题所在。在Euler项目的p23论坛上发布的第一个python解决方案本质上是算法的巧妙实现，唯一的主要区别是它使用一组大量数字而不是列表。它可以在15秒内解决Atom处理器上的问题；当我将其更改为使用列表时，十五分钟后，它仍然没有解决问题。

故事的寓意:x in list很慢。

尽管如此，直接产生总和要比减去和检查要快。 :)

关于python - 优化非大量求和算法，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/4882428/