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 

大約需要0.387秒我的機器上對於n = 10^13。但是，如果我複製for循環的內容並在運行實際for循環之前運行它，我會得到相同的正確結果，但運行時間爲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，的計算由於浮點精度的限制，最終會產生錯誤的界限。您可以通過比較candidate * candidate <= n或使用諸如decimal模塊之類的東西來計算邊界以獲得足夠的精度來解決此問題。

Answer 2

的原因是內部_prime_candidates功能。 在您的第一個示例中，它會生成所有數字3,5,...,3162277，並嘗試將所有這些候選人的n除。

在你的第二個例子中，你首先大大減少了你的n，所以_prime_candidates生成數字3,5,...,34939。它的檢查數量要少得多。