Python - 为什么这个素数因式分解函数能够获得更好的性能？

Question

我写了一个素因子分解函数：

def prime_factorization(n):
    prime_factors = {}
    for i in _prime_candidates(n):
        if n % i == 0:
            prime_factors[i] = 0
            while n % i == 0:
                n /= i
                prime_factors[i] += 1
    if n != 1: prime_factors[int(n)] = 1
    return prime_factors

def _prime_candidates(n):
    yield 2
    for i in range(3, int(n**.5)+1, 2):
        yield i

在我的机器上n=10^13大约需要0.387秒。但是，如果我复制for循环的内容并在运行实际的for循环之前对数字2运行它，我会得到相同的正确结果，但是对于n=10^13，运行时间大约为0.003秒。您可以看到下面的代码：

def prime_factorization(n):
    prime_factors = {}
    if n % 2 == 0:
        prime_factors[2] = 0
    while n % 2 == 0:
        n /= 2
        prime_factors[2] += 1
    for i in _prime_candidates(n):
        if n % i == 0:
            prime_factors[i] = 0
            while n % i == 0:
                n /= i
                prime_factors[i] += 1
    if n != 1: prime_factors[int(n)] = 1
    return prime_factors

def _prime_candidates(n):
    yield 2
    for i in range(3, int(n**.5)+1, 2):
        yield i

为什么这会导致如此巨大的性能提升？你知道吗

编辑：我使用的是python3.5，我使用的是clock()模块的time函数来进行基准测试。你知道吗

Answer 1

原因在_prime_candidates函数内部。 在您的第一个示例中，它生成所有的数字3,5,...,3162277，您尝试用这些候选数除以n。你知道吗

在第二个例子中，首先大大减少n，这样_prime_candidates生成数字3,5,...,34939。要核对的数字要少得多。你知道吗

Answer 2

在您的初始版本中，_prime_candidates通过10^13，因此它生成的候选者达到该值的平方根。你知道吗

在您的第二个版本中，_prime_candidates通过了5^13，因为2的所有因子都被除掉了。它产生的候选者要少得多。你知道吗

通过将_prime_candidates逻辑折叠成prime_factorization并在找到因子时重新计算上界，可以得到更好、更一般的改进：

def prime_factorization(n):
    prime_factors = {}

    factor_multiplicity = 0
    while n % 2 == 0:
        n //= 2
        factor_multiplicity += 1
    if factor_multiplicity:
        prime_factors[2] = factor_multiplicity

    factor_bound = n**.5
    candidate = 3

    while candidate <= factor_bound:
        factor_multiplicity = 0
        while n % i == 0:
            n //= i
            factor_multiplicity += 1
        if factor_multiplicity:
            prime_factors[candidate] = factor_multiplicity
            factor_bound = n**.5
        candidate += 2

    if n != 1:
        prime_factors[n] = 1
    return prime_factors

注意，对于足够大的n，由于浮点精度的限制，n**.5的计算最终会生成错误的界限。您可以通过比较candidate * candidate <= n，或者使用decimal模块之类的工具来计算绑定以达到足够的精度来解决这个问题。你知道吗