Rimuovi elementi da un elenco durante l'iterazione senza utilizzare memoria aggiuntiva in Python

Question

Il mio problema è semplice: ho una lunga lista di elementi che voglio scorrere e controllare ogni elemento in base a una condizione. A seconda dell'esito della condizione, desidero eliminare l'elemento corrente dell'elenco e continuare a ripetere come al solito.

Ho letto alcuni altri thread su questo argomento. Sono state proposte due soluzioni. O fai un dizionario fuori dalla lista (il che implica fare una copia di tutti i dati che stanno già riempiendo tutta la RAM nel mio caso). O esegui la lista al contrario (che interrompe il concetto dell'algoritmo che voglio implementare).

Esiste un modo migliore o più elegante di farlo?

def walk_list(list_of_g): 
    g_index = 0 
    while g_index < len(list_of_g): 
     g_current = list_of_g[g_index] 
     if subtle_condition(g_current): 
      list_of_g.pop(g_index) 
     else: 
      g_index = g_index + 1 

Answer 1

Ecco una risposta alternativa per se è assolutamente necessario rimuovere le voci dalla lista originale, e si non hanno memoria sufficiente per fare una copia - spostare gli elementi in basso nell'elenco te stesso:

def walk_list(list_of_g): 
    to_idx = 0 
    for g_current in list_of_g: 
     if not subtle_condition(g_current): 
      list_of_g[to_idx] = g_current 
      to_idx += 1 
    del list_of_g[to_idx:] 

Questo sposterà ogni elemento (in realtà un puntatore a ciascuna voce) esattamente una volta, quindi sarà O (N). La dichiarazione alla fine della funzione rimuoverà tutti gli elementi indesiderati alla fine della lista e penso che Python sia abbastanza intelligente da ridimensionare la lista senza allocare memoria per una nuova copia della lista.

Answer 2

Che ne dici di questo?

[x for x in list_of_g if not subtle_condition(x)] 

il suo ritorno il nuovo elenco con l'eccezione da subtle_condition

Answer 3

Per semplicità, utilizzare un elenco di comprensione:

def walk_list(list_of_g): 
    return [g for g in list_of_g if not subtle_condition(g)] 

Naturalmente, questo non altera l'elenco originale, in modo che il chiamante il codice dovrebbe essere diverso.

Se davvero si vuole mutare la lista (raramente la scelta migliore), camminando all'indietro è più semplice:

def walk_list(list_of_g): 
    for i in xrange(len(list_of_g), -1, -1): 
     if subtle_condition(list_of_g[i]): 
      del list_of_g[i] 

Answer 4

li = [ x for x in li if condition(x)] 

e anche

li = filter(condition,li) 

Thanks to Dave Kirby

Answer 5

Il built -in funzione filtro è fatto solo per fare questo:

list_of_g = filter(lambda x: not subtle_condition(x), list_of_g) 

Answer 6

rimuovere elementi da un elenco è costoso, dal momento che Python deve copiare tutti gli elementi sopra g_index in un punto. Se il numero di elementi che vuoi rimuovere è proporzionale alla lunghezza della lista N, allora il tuo algoritmo sarà O (N ** 2). Se la lista è abbastanza lunga da riempire la tua RAM, ti aspetterà molto tempo per il completamento.

E 'più efficiente per creare una copia filtrata della lista, sia utilizzando una lista di comprensione come mostrato Marcelo, o utilizzare il filtro o funzioni itertools.ifilter:

g_list = filter(not_subtle_condition, g_list) 

Se non è necessario utilizzare il nuovo elenco e solo voglia di scorrere su di esso una volta, allora è meglio usare IFilter dal momento che non sarà creare un secondo elenco:

for g_current in itertools.ifilter(not_subtle_condtion, g_list): 
    # do stuff with g_current 

Answer 7

Suona come un ottimo caso d'uso per la funzione di filtro.

def should_be_removed(element): 
    return element > 5 

a = range(10) 
a = filter(should_be_removed, a) 

Questo, tuttavia, non eliminerà l'elenco durante l'iterazione (né lo consiglio).Se per la memoria-spazio (o altri motivi di prestazioni) si ha realmente bisogno, è possibile effettuare le seguenti operazioni:

i = 0 
while i < len(a): 
    if should_be_removed(a[i]): 
     a.remove(a[i]) 
    else: 
     i+=1 
    print a 

Answer 8

Se si esegue un'iterazione inversa, è possibile rimuovere gli elementi al volo senza influenzare i prossimi indici che visiterai:

numbers = range(20) 

# remove all numbers that are multiples of 3 
l = len(numbers) 
for i, n in enumerate(reversed(numbers)): 
    if n % 3 == 0: 
     del numbers[l - i - 1] 

print numbers 

Il enumerate(reversed(numbers)) è solo una scelta stilistica. È possibile utilizzare una serie se questo è più leggibile per voi:

l = len(numbers) 
for i in range(l-1, -1, -1): 
    n = numbers[i] 
    if n % 3 == 0: 
     del numbers[i] 

Se avete bisogno di viaggiare l'elenco in ordine, è possibile invertire in posizione con .reverse() prima e dopo l'iterazione invertito. Questo non duplicherà neanche la tua lista.