Python: Entfernen Sie viele Elemente aus einer Liste

Question

Ich bin in der letzten Phase eines Projekts, an dem ich gearbeitet habe. Alles läuft reibungslos, aber ich habe einen Flaschenhals, mit dem ich Probleme habe.

Ich habe eine Liste von Tupeln. Die Liste reicht von etwa 40.000 bis 1.000.000 Datensätzen. Jetzt habe ich ein Wörterbuch, wo jeder (Wert, Schlüssel) ein Tupel in der Liste ist.

So könnte ich habe

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

Ich mag jeden (v, k) Tupel aus der Liste entfernen.

Derzeit mache ich:

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

Entfernen 838 Tupel aus der Liste 20.000 Tupel enthält, überall dauert 3 bis 4 Sekunden. Ich werde wahrscheinlich mehr als 10.000 Tupel aus einer Liste von 1.000.000 entfernen, also brauche ich das schneller.

Gibt es einen besseren Weg, dies zu tun?

Ich kann Code zum Testen, sowie gebeizte Daten aus der tatsächlichen Anwendung bei Bedarf bereitstellen.

Answer 1

Sie werden messen müssen, aber ich kann diese mehr performant sein vorstellen:

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

, weil die Suche in der dict geschieht, was für diese Art der Sache mehr geeignet ist. Beachten Sie jedoch, dass dadurch eine neue Liste erstellt wird, bevor die alte entfernt wird. Es gibt also einen Speicher-Kompromiss. Wenn das ein Problem ist, könnte ein Überdenken Ihres Containertyps als jkp suggest in Ordnung sein.

Bearbeiten: Seien Sie vorsichtig, wenn None tatsächlich in Ihrer Liste ist - Sie müssten einen anderen "Platzhalter" verwenden.

Answer 2

Das Problem sieht für mich aus, dass Sie eine list als den Container verwenden, aus dem Sie versuchen, zu entfernen, und es ist ein völlig ungeordneter Typ. Um also jedes Element in der Liste nach einer linearen Operation zu suchen (O(n)), muss es über die gesamte Liste iterieren, bis es eine Übereinstimmung findet.

Wenn Sie die list für einen anderen Container (set?) Austauschen können, der einen jedes Artikels verwendet, um sie zu bestellen, dann könnte jede Übereinstimmung viel schneller durchgeführt werden.

Der folgende Code zeigt, wie Sie von mir und Nick auf diesem Thread angeboten dies mit einer Kombination aus Ideen tun könnten:

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

Jedes Mal, wenn Sie myList.remove nennen, hat Python über die gesamte Liste zu scannen zu suchen für diesen Artikel und entfernen Sie es. Im schlimmsten Fall würde jedes Objekt, nach dem Sie suchen, jedes Mal am Ende der Liste stehen.

Haben Sie versucht, den „inversen“ Betrieb tun:

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

Aber ich bin wirklich nicht sicher, wie gut, dass skalieren würde, entweder, weil Sie eine Kopie der ursprünglichen Liste machen würden - könnte dort viel Speicherverbrauch sein.

Wahrscheinlich ist die beste Alternative hier, auf Alex Martelli zu warten, um einen überwältigenden intuitiven, einfachen und effizienten Ansatz zu veröffentlichen.

Answer 4

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

Answer 5

versuchen, etwas wie folgt aus:

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

Dies wird myList auf einen Satz konvertieren, werden die Schlüssel/Werte in myDict tauschen und sie in eine Reihe gestellt, und dann finden Sie den Unterschied, wiederum es zurück in eine Liste und es zurück zu myList zuweisen. :)

Answer 6

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

Answer 7

Eine Liste mit einer Million 2-Tupel ist nicht groß auf den meisten Maschinen mit Python. Allerdings, wenn Sie unbedingt die Entfernung in situ tun, hier ist eine saubere Art und Weise es richtig zu tun:

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] 

aktualisieren Eigentlich jeder del kostet O (n) das Mischen der Liste Zeiger nach unten C des memmove() verwenden, Also, wenn es d dels gibt, ist es O(n*d) nicht O(n**2). Beachten Sie, dass (1) das OP vorschlägt, dass d approx == 0.01 * n und (2) die O(n*d) Anstrengung einen Zeiger auf irgendwo anders im Gedächtnis kopiert ... so könnte diese Methode in der Tat etwas schneller sein, als ein schneller Blick anzeigen würde. Benchmarks, irgendjemand?

Was werden Sie mit der Liste tun nach Sie haben die Elemente entfernt, die im dict sind? Ist es möglich, das dict-filtering auf den nächsten Schritt zu übertragen?

Answer 8

bis etwa 10.000 Tupel aus einer Liste von etwa 1.000.000, zu entfernen, wenn die Werte hashable sind, soll der schnellste Ansatz:

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

Die Herstellung des Satzes ist ein klein einmalig Kosten, weichen sparen Tupel-Entpacken und Repacking, oder Tupel-Indizierung, oft. Zuweisung an myList[:] anstelle der Zuordnung zu myList ist auch semantisch wichtig (falls es andere Verweise auf myList herum gibt, ist es nicht genug, nur den Namen neu zu binden - Sie wollen wirklich die Inhalte binden! -).

Ich habe keine Testdaten um die Zeitmessung selbst zu machen, ach !, aber lass mich wissen, wie es uns auf deinen Testdaten spielt!

Wenn die Werte nicht hashable (zB sie Unterlisten sind, zum Beispiel), schnellste wahrscheinlich ist:

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

oder vielleicht (sollte kein großer Unterschied so oder so machen, aber ich vermute, die vorherige ist besser - Indizierung billiger als das Auspacken und Umpacken ist):

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

In diesen beiden Varianten der Sentinel-Idiom benutzt wird gegen Werte von None zu abwehren (was kein Problem für die bevorzugte set-basiert Ansatz - wenn Werte sind hashable!) wie es geht billiger sein als if a not in myDict or myDict[a] != b (das erfordert zwei Indexierungen in myDict).