我有我寫這個因式分解功能:Python - 爲什麼這個素數因子分解函數從這裏獲得更好的性能?
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()
函數進行基準測試。
可能是因爲大數目有2個作爲大量素因子? – Kupiakos
我的猜測是你沒有正確地對它進行基準測試......你是否使用['timeit'](https://docs.python.org/2/library/timeit.html)進行測量? – alfasin
你使用的是什麼版本的Python? –