如何优化我的Python代码以使用更少的内存执行计算

Question

我把下面的代码放在一起，以确定一个数字的除数是奇数还是偶数。该代码适用于相对较小的数字，但一旦输入9位数等较大的数字，它就会挂断。

def divisors(n):
    num = len(set([x for x in range(1,n+1) if not divmod(n,x)[1]]))
    if (num != 0 and num % 2 == 0):
        return 'even'
    else:
        return 'odd'

我能做些什么来提高效率？

Answer 1

这是您的问题：

num = len(set([x for x in range(1,n+1) if not divmod(n,x)[1]]))

这会构造一个列表，然后从该列表中构造一个集合，然后获取集合的长度。您不需要做任何这些工作（range()或xrange()不产生重复的对象，所以我们不需要集合，而sum()适用于任何可迭代的对象，因此您也不需要列表）。当我们讨论这个主题时，divmod(n, x)[1]只是编写n % x的一种非常复杂的方式，它会消耗一点额外的内存来构建元组（由于丢弃了元组，因此会立即回收）。这是固定版本：

num = sum(1 for x in xrange(1,n+1) if not n % x)

Answer 2

您不需要测试每个可能的除数，最多测试sqrt（n）就足够了。这将使您的函数O（sqrt（n））而不是O（n）。

import math
def num_divisors(n):
    sqrt = math.sqrt(n)
    upper = int(sqrt)
    num = sum(1 for x in range(1, upper + 1) if not n % x)
    num *= 2
    if upper == sqrt and num != 0:
        num -= 1
    return num

在我使用python2的基准测试中，这比使用n = int(1e6)的sum(1 for x in range(1, n + 1) if not n % x)快1000倍，比使用1e8快10000倍。对于1e9，后一个代码给了我一个内存错误，表明在求和之前将整个序列存储在内存中，因为在python 2中，range()返回一个列表，而我应该使用xrange()。对于蟒蛇3，range()是可以的。