Python: rimuovere molti elementi da un elenco

Question

Sono nel tratto finale di un progetto su cui ho lavorato. Tutto funziona senza intoppi ma ho un collo di bottiglia che ho problemi a lavorare in giro.

Ho una lista di tuple. L'elenco ha una durata che va da 40.000 a 1.000.000 di record. Ora ho un dizionario in cui ognuno (valore, chiave) è una tupla nella lista.

Quindi, potrei avere

myList = [(20000, 11), (16000, 4), (14000, 9)...] 
myDict = {11:20000, 9:14000, ...} 

Voglio rimuovere ciascuno (v, k) tuple dalla lista.

Attualmente sto facendo:

for k, v in myDict.iteritems(): 
    myList.remove((v, k)) 

Rimozione 838 tuple dalla lista che contiene 20.000 tuple impiega da 3 - 4 secondi. Molto probabilmente rimuoverò più di 10.000 tuple da una lista di 1.000.000, quindi ho bisogno che questo sia più veloce.

C'è un modo migliore per farlo?

Posso fornire il codice utilizzato per testare, oltre ai dati in salamoia dall'applicazione effettiva se necessario.

Answer 1

Dovrete misurare, ma posso immaginare che questo è più performante:

myList = filter(lambda x: myDict.get(x[1], None) != x[0], myList) 

perché la ricerca avviene nel dizionario, che è più adatto per questo genere di cose. Si noti, tuttavia, che ciò creerà una nuova lista prima di rimuovere quella precedente; quindi c'è un compromesso di memoria. Se questo è un problema, ripensa il tuo tipo di contenitore come suggerito da jkp potrebbe essere in ordine.

Modifica: fai attenzione, però, se None è effettivamente nel tuo elenco, dovresti utilizzare un "segnaposto" diverso.

Answer 2

Il problema mi sembra il fatto che si sta utilizzando un list come contenitore da cui si sta tentando di rimuovere ed è un tipo completamente non ordinato. Quindi, per trovare ogni elemento nella lista è un'operazione lineare (O(n)), deve iterare sull'intero elenco fino a quando non trova una corrispondenza.

Se è possibile scambiare lo list per un altro contenitore (set?) Che utilizza uno hash() di ciascun articolo per ordinarli, allora ogni corrispondenza potrebbe essere eseguita molto più rapidamente.

Il seguente codice mostra come si potrebbe fare questo utilizzando una combinazione di idee offerti da me e Nick su questo thread:

list_set = set(original_list) 
dict_set = set(zip(original_dict.values(), original_dict.keys())) 
difference_set = list(list_set - dict_set) 
final_list = [] 
for item in original_list: 
    if item in difference_set: 
     final_list.append(item) 

Answer 3

Ogni volta che si chiama myList.remove, Python ha per eseguire la scansione su tutta la lista per la ricerca per quell'articolo e rimuoverlo. Nel peggiore dei casi, ogni oggetto che cerchi sarà alla fine della lista ogni volta.

Hai provato a fare l'operazione "inversa" di:

newMyList = [(v,k) for (v,k) in myList if not k in myDict] 

ma sono davvero non so come bene che sarebbe in scala, sia, dal momento che si sarebbe fare una copia della lista originale - potrebbe potenzialmente essere un sacco di utilizzo della memoria lì.

Probabilmente la migliore alternativa qui è aspettare Alex Martelli per postare un approccio incredibilmente intuitivo, semplice ed efficiente.

Answer 4

[(i, j) for i, j in myList if myDict.get(j) != i] 

Answer 5

provare qualcosa di simile:

myListSet = set(myList) 
myDictSet = set(zip(myDict.values(), myDict.keys())) 
myList = list(myListSet - myDictSet) 

Questo convertirà myList ad un set, cambierà le chiavi/valori in myDict e metterle in un set, per poi calcolare la differenza, turno torna in un elenco e assegnarlo a myList. :)

Answer 6

[i for i in myList if i not in list(zip(myDict.values(), myDict.keys()))] 

Answer 7

Un elenco contenente un milione di tuple da 2 non è grande sulla maggior parte delle macchine che eseguono Python. Tuttavia, se si deve assolutamente fare la rimozione in situ, ecco un modo pulito di fare in modo corretto:

def filter_by_dict(my_list, my_dict): 
    sentinel = object() 
    for i in xrange(len(my_list) - 1, -1, -1): 
     key = my_list[i][1] 
     if my_dict.get(key, sentinel) is not sentinel: 
      del my_list[i] 

Aggiornamento In realtà ciascuno del costa O (n) mischiare i puntatori della lista verso il basso con memmove di C(), quindi se ci sono d dels, è O(n*d) non O(n**2). Nota che (1) l'OP suggerisce che d approssimativamente == 0.01 * n e (2) lo sforzo O(n*d) sta copiando un puntatore in un'altra posizione nella memoria ... quindi questo metodo potrebbe in effetti essere un po 'più veloce di quanto una rapida occhiata potrebbe indicare. Benchmark, chiunque?

Cosa hai intenzione di fare con la lista dopo il hai rimosso gli elementi che sono nel dict? È possibile portare il filtro dict sul passo successivo?

Answer 8

Per rimuovere circa 10.000 tuple da un elenco di circa 1.000.000, se i valori sono hashable, l'approccio più veloce dovrebbe essere:

totoss = set((v,k) for (k,v) in myDict.iteritems()) 
myList[:] = [x for x in myList if x not in totoss] 

La preparazione del set è un piccolo costo una tantum, Wich salva facendo tuple decompressione e reimballaggio, o tuple indexing, un sacco di volte. Assignign a myList[:] invece di assegnare ad myList è anche semanticamente importante (nel caso in cui non ci sono altri riferimenti a myList in giro, non è sufficiente per associare nuovamente solo il nome - si vuole veramente associare nuovamente i contenuti -!).

Non ho i dati di test in giro per fare la misurazione del tempo, ahimè !, ma, fammi sapere come funziona sui nostri dati di test!

Se i valori non sono hashable (ad esempio, sono sotto-liste, per esempio), il più veloce è probabilmente:

sentinel = object() 
myList[:] = [x for x in myList if myDict.get(x[0], sentinel) != x[1]] 

o forse (non dovrebbe fare una grande differenza in entrambi i casi, ma ho il sospetto il precedente è meglio - indicizzazione è più economico di disimballaggio e ricondizionamento):

sentinel = object() 
myList[:] = [(a,b) for (a,b) in myList if myDict.get(a, sentinel) != b] 

In questi due varianti del linguaggio sentinella è utilizzato per allontanare contro valori di None (che non è un problema per il set-based preferito approccio - se i valori sono lavabili!) come sta andando a essere molto più economico di if a not in myDict or myDict[a] != b (che richiede due indicizzazioni in myDict).