python prime factorizzazione performance

Question

Sono relativamente nuovo a Python e sono confuso circa le prestazioni di due blocchi di codice relativamente semplici. La prima funzione genera una fattorizzazione primaria di un numero n dato un elenco di numeri primi. Il secondo genera un elenco di tutti i fattori di n. Avrei anche se prime_factor sarebbe più veloce di factors (per lo stesso n), ma questo non è il caso. Non sto cercando algoritmi migliori, ma piuttosto mi piacerebbe capire perché prime_factor è molto più lento di 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) 

Utilizzando il modulo timeit,

{ i:factors(i) for i in range(1, 10000) } richiede 2,5 secondi

{ i:prime_factor(i, primes) for i in range(1, 10000) } prende 17 secondi

Questo è sorprendente per me. factors controlla ogni numero da 1 a sqrt (n), mentre prime_factor controlla solo i primi. Gradirei qualsiasi aiuto nella comprensione delle caratteristiche di prestazione di queste due funzioni.

Grazie

Edit: (risposta a roliu) Ecco il mio codice per generare un elenco di numeri primi da 2 a 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

Senza vedere quello che hai usato per primes, dobbiamo congettura (non possiamo eseguire il tuo codice).

Ma una grande parte di questo è semplicemente matematica: ci sono (molto grosso modo) su n/log(n) primi minori di n, e questo è molto più grande di sqrt(n). Quindi, quando si passa un numero primo, prime_factor(n) fa molto più lavoro: passa attraverso le operazioni O(n/log(n)) prima di trovare il primo fattore primo (n!), Mentre factors(n) si arresta dopo le operazioni O(sqrt(n)).

Questo può essere molto significativo. Ad esempio, sqrt(10000) è solo 100, ma ci sono 1229 numeri primi meno di 10000. Quindi prime_factor(n)può possibile eseguire più di 10 volte il lavoro necessario per gestire i numeri primi grandi nella tua gamma.