私はPythonに比較的慣れていないため、2つの比較的単純なコードブロックのパフォーマンスについて混乱しています。最初の関数は、素数のリストを指定して、数値 n の素因数分解を生成します。2 番目は、n のすべての因数のリストを生成します。私は（同じnの場合）prime_factorよりも高速になると思いますが、そうではありません。より良いアルゴリズムを探しているわけではありませんが、 がよりもはるかに遅いfactors理由を理解したいと思います。prime_factorfactors
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これら 2 つの関数のパフォーマンス特性を理解する上で、お役に立てば幸いです。
ありがとう
編集: (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