Cos'è un modo veloce e pitonioso/pulito per rimuovere una lista ordinata da un'altra lista ordinata in python?

Question

Sto creando un metodo veloce per generare un elenco di numeri primi nell'intervallo (0, limite + 1). Nella funzione finisco per rimuovere tutti gli interi nell'elenco chiamato rimovibile dalla lista chiamata primi. Sto cercando un modo veloce e pitonico per rimuovere gli interi, sapendo che entrambe le liste sono sempre ordinate.

Potrei sbagliarmi, ma credo che list.remove (n) itera sulla lista confrontando ogni elemento con n. il che significa che il codice seguente viene eseguito in tempo O (n^2).

# removable and primes are both sorted lists of integers 
for composite in removable: 
    primes.remove(composite) 

in base al largo la mia ipotesi (che potrebbe essere sbagliato e si prega di confermare o meno questo è corretto) e il fatto che entrambe le liste sono sempre ordinati, penserei che il seguente codice corre più veloce, dal momento che solo i loop sulla lista una volta per un tempo O (n). Tuttavia, non è affatto pitonico o pulito.

i = 0 
j = 0 
while i < len(primes) and j < len(removable): 
    if primes[i] == removable[j]: 
     primes = primes[:i] + primes[i+1:] 
     j += 1 
    else: 
     i += 1 

C'è forse una funzione incorporata o un modo più semplice per farlo? E qual è il modo più veloce?

Note a margine: in realtà non ho programmato le funzioni o il codice riportato sopra. Inoltre, non importa se l'elenco rimovibile viene modificato/distrutto nel processo.

Per chiunque sia interessato le funzioni completo è qui sotto:

import math 

# returns a list of primes in range(0, limit+1) 
def fastPrimeList(limit): 
    if limit < 2: 
     return list() 
    sqrtLimit = int(math.ceil(math.sqrt(limit))) 
    primes = [2] + range(3, limit+1, 2) 
    index = 1 
    while primes[index] <= sqrtLimit: 
     removable = list() 
     index2 = index 
     while primes[index] * primes[index2] <= limit: 
      composite = primes[index] * primes[index2] 
      removable.append(composite) 
      index2 += 1 
     for composite in removable: 
      primes.remove(composite) 
     index += 1 
    return primes 

Answer 1

questo è abbastanza veloce e pulito, lo fa O(n) controlli di appartenenza set, e nel tempo ammortizzato viene eseguito in O(n) (prima riga è O(n) ammortizzato, secondo linea è O(n * 1) ammortizzato, perché un controllo di appartenenza è O(1) ammortizzato):

removable_set = set(removable) 
primes = [p for p in primes if p not in removable_set] 

Ecco la modifica del vostro seconda soluzione. Lo fa O(n) operazioni di base (caso peggiore):

tmp = [] 
i = j = 0 
while i < len(primes) and j < len(removable): 
    if primes[i] < removable[j]: 
     tmp.append(primes[i]) 
     i += 1 
    elif primes[i] == removable[j]: 
     i += 1 
    else: 
     j += 1 
primes[:i] = tmp 
del tmp 

Si prega di notare che le costanti anche importanti. L'interprete Python è piuttosto lento (cioè con una grande costante) per eseguire il codice Python. La seconda soluzione ha un sacco di codice Python, e può effettivamente essere più lenta per piccoli valori pratici di n rispetto alla soluzione con set s, perché le operazioni set sono implementate in C, quindi sono veloci (cioè con una piccola costante).

Se si dispone di più soluzioni di lavoro, eseguirle su formati di input tipici e misurare il tempo. Potresti rimanere sorpreso della loro velocità relativa, spesso non è ciò che potresti prevedere.

Answer 2

La cosa più importante qui è rimuovere il comportamento quadratico. Hai questo per due motivi.

Innanzitutto, chiamando remove cerca nell'intero elenco i valori da rimuovere. Questa operazione richiede tempo lineare e lo stai facendo una volta per ogni elemento in removable, quindi il tuo tempo totale è O(NM) (dove N è la lunghezza di primes e M è la lunghezza di removable).

In secondo luogo, la rimozione di elementi dal centro di un elenco obbliga a spostare l'intero resto dell'elenco su uno slot. Quindi, ognuno prende tempo lineare, e di nuovo lo stai facendo M volte, quindi di nuovo è O(NM).

---

Come puoi evitare questi?

Per il primo, è necessario sfruttare l'ordinamento o semplicemente utilizzare qualcosa che consente di eseguire ricerche a tempo costante anziché in tempo lineare, ad esempio set.

Per il secondo, è necessario creare un elenco di indici da eliminare e quindi eseguire un secondo passaggio per spostare ciascun elemento sul numero appropriato di indici tutti in una volta oppure creare semplicemente un nuovo elenco anziché tentare di mutare l'originale sul posto.

Quindi, ci sono una varietà di opzioni qui. Qual è il migliore? Quasi certamente non importa; cambiare il tuo tempo di O(NM) a solo O(N+M) sarà probabilmente più che sufficiente per un'ottimizzazione che sei soddisfatto dei risultati. Ma se hai bisogno di spremere più prestazioni, dovrai implementarle tutte e testarle su dati realistici.

L'unico di questi che non penso sia ovvio è come "utilizzare l'ordinamento". L'idea è quella di utilizzare lo stesso tipo di sfalsati-zip iterazione che usereste in un merge sort, in questo modo:

def sorted_subtract(seq1, seq2): 
    i1, i2 = 0, 0 
    while i1 < len(seq1): 
     if seq1[i1] != seq2[i2]: 
      i2 += 1 
      if i2 == len(seq2): 
       yield from seq1[i1:] 
       return 
     else: 
      yield seq1[i1] 
      i1 += 1