蟒蛇因式分解性能

Question

我是比較新的蟒蛇，我感到困惑的代碼的兩個相對簡單的模塊的性能。給定一列素數，第一個函數生成一個數n的素數分解。第二個生成所有n的因子列表。我會雖然prime_factor會比factors（同樣n）更快，但事實並非如此。我不是在尋找更好的算法，而是我想知道爲什麼prime_factor比factors慢得多。

def prime_factor(n, primes): 
    prime_factors = [] 
    i = 0 
    while n != 1: 
     if n % primes[i] == 0: 
      factor = primes[i] 
      prime_factors.append(factor) 
      n = n // factor 
     else: i += 1 
    return prime_factors 

import math 
def factors(n): 
    if n == 0: return [] 
    factors = {1, n} 
    for i in range(2, math.floor(n ** (1/2)) + 1): 
     if n % i == 0: 
      factors.add(i) 
      factors.add(n // i) 
    return list(factors) 

使用timeit模塊，

{ i:factors(i) for i in range(1, 10000) }需要2.5秒

{ i:prime_factor(i, primes) for i in range(1, 10000) }需要17秒

這令我感到詫異。 factors檢查每個數字從1到sqrt（n），而prime_factor只檢查素數。我希望在理解這兩個函數的性能特徵方面有所幫助。

感謝

編輯：（響應roliu） 這裏是我的代碼來生成從2素數以up_to列表：

def primes_up_to(up_to): 
    marked = [0] * up_to 
    value = 3 
    s = 2 
    primes = [2] 
    while value < up_to: 
     if marked[value] == 0: 
      primes.append(value) 
      i = value 
      while i < up_to: 
       marked[i] = 1 
       i += value 
     value += 2 
    return primes 

Answer 1

沒有看到你用什麼primes，我們要猜（我們不能運行你的代碼）。

但是這很大一部分是簡單的數學：有（非常粗略地講）約n/log(n)素數小於n，而這比sqrt(n)大很多。所以，當你傳遞素，prime_factor(n)做了很多工作：它找到第一個主要因素之前經過O(n/log(n))操作，而factors(n)後O(sqrt(n))業務放棄（n本身！）。

這是非常顯著。例如，sqrt(10000)僅僅是100，但也有1229素數小於10000。所以prime_factor(n)可以需要做的10倍多的工作來應對你的範圍大素數。