python-此代码效率太低,如何增加内存和执行效率？

我正在尝试完成以下挑战：https://app.codesignal.com/challenge/ZGBMLJXrFfomwYiPs.我编写的代码似乎可以正常工作,但是效率很低,以至于无法通过测试(执行时间太长,使用的内存过多).有什么方法可以提高效率？我对构建...

我正在尝试完成以下挑战：https://app.codesignal.com/challenge/ZGBMLJXrFfomwYiPs.
我编写的代码似乎可以正常工作,但是效率很低,以至于无法通过测试(执行时间太长,使用的内存过多).有什么方法可以提高效率？我对构建高效的脚本还很陌生.可以使用提到的“ map()”代替“ for range(1,n)中的i”.感谢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))]

任何帮助将不胜感激.

谢谢,

亚伦

解决方法:

首先,组合是可迭代的.这意味着您无需遍历它们就可以将它们转换为列表.实际上,这样做的效率极低.

下一个可以明显改善的是您的因素程序.目前它是线性的.我们可以做得更好.我们可以通过以下算法获得整数N的因数：

>得到N的素因式分解,使得N = p1 ^ n1 * p2 ^ n2 * …
> 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))]