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，我会得到相同的正确结果，但运行ning 时间为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

为什么这会带来如此巨大的性能提升？

编辑：我正在使用 Python 3.5，并且正在使用 time 模块的 clock() 函数进行基准测试。

Answer 1

在您的初始版本中，_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 模块的方法来计算足够精度的界限来解决此问题。

Answer 2

原因在 _prime_candidates 函数中。在您的第一个示例中，它生成所有数字 3,5,...,3162277 并且您尝试将您的 n 除以所有这些候选人。

在您的第二个示例中，您首先大大减少了 n，因此 _prime_candidates 生成了数字 3,5,...,34939。要检查的数字要少得多。

Python - 为什么这个质因数分解函数会因此获得更好的性能？

Python - Why does this prime factorization function get better performance from this?

primes