这段代码效率太低，如何提高内存和执行效率？

Question

我正在尝试完成以下挑战：https://app.codesignal.com/challenge/ZGBMLJXrFfomwYiPs。我编写的代码似乎工作正常，但是它效率太低，以致于测试失败(执行时间太长，占用的内存太多)。有什么办法能让这件事更有效率吗？我对构建高效的脚本非常陌生。有人提到"map()“可以代替"for I in range(1，n)”。感谢Xero Smith和其他人提出的优化方案的建议：

from functools import reduce
from operator import mul
from itertools import combinations

# Starting from the maximum, we can divide our bag combinations to see the total number of integer factors                                                                                    

def prime_factors(n):
    p = 2
    dct = {}
    while n != 1:
        if n % p:
            p += 1
        else:
            dct[p] = dct.get(p, 0) + 1
            n = n//p
    return dct


def number_of_factors(n):
    return reduce(mul, (i+1 for i in prime_factors(n).values()), 1)


def kinderLevon(bags):
    candies = list()
    for x in (combinations(bags, i) for i in range(1, len(bags)+1)):
        for j in x:
            candies.append(sum(j))
    satisfied_kids = [number_of_factors(i) for i in candies]
    return candies[satisfied_kids.index(max(satisfied_kids))]

任何帮助都将不胜感激。

谢谢,

Aaron

Answer 1

首先，组合是可迭代的。这意味着您不必在迭代它们之前将它们转换为列表；实际上，这样做效率很低。

接下来可以显著改进的是您的factors过程。目前它是线性的。我们可以做得更好。我们可以通过以下算法获得整数N的因子数：

1. 得到N的素因式分解，以便使N = p1^n1 * p2^n2 * ...
2. N的因子数为(1+n1) * (1+n2) * ...

详情请参见https://www.wikihow.com/Find-How-Many-Factors-Are-in-a-Number。

另外，您当前的解决方案有很多没有使用的变量和计算。把他们赶走。

有了这些，我们得到了应该工作的下列内容：

from functools import reduce
from operator import mul
from itertools import combinations

# Starting from the maximum, we can divide our bag combinations to see the total number of integer factors                                                                                    

def prime_factors(n):
    p = 2
    dct = {}
    while n != 1:
        if n % p:
            p += 1
        else:
            dct[p] = dct.get(p, 0) + 1
            n = n//p
    return dct


def number_of_factors(n):
    return reduce(mul, (i+1 for i in prime_factors(n).values()), 1)


def kinderLevon(bags):
    candies = list()
    for x in (combinations(bags, i) for i in range(1, len(bags)+1)):
        for j in x:
            candies.append(sum(j))
    satisfied_kids = [number_of_factors(i) for i in candies]
    return candies[satisfied_kids.index(max(satisfied_kids))]

Answer 2

根据我的评论，我已经可以识别出内存和复杂性的改进。在您的factors函数中，由于您只需要因素的数量，所以只能计算它们，而不是存储它们。

def factors(n):
    k = 2
    for i in range(2, n//2 +1):
        if n % i == 0:
            k += 1
    return k

编辑：正如注释中所建议的，请在前面停止计数器。

这实际上降低了庞大数字的时间复杂度，但对于较小的数字则不是这样。

这比使用列表理解(仍然分配内存)的改进要好得多。

此外，将组合列表分配两次是没有意义的。你在做什么

x = list(combinations(bags, i));
for j in list(x):
    ...

第一行将元组(由combinations返回)转换为列表，从而复制数据。第二行list(x)重新分配列表的副本，占用更多内存！你真的应该这样写：

for j in combination(bags, i):
    ...

作为语法问题，请不要在Python中使用分号;！

Answer 3

使用列表理解。要素函数可以这样转换：

def factors(n):
    return len([i for i in range(1, n + 1) if n % i == 0])