Python: Erstellen einer Funktion zum Ändern einer Liste nach Referenz nicht Wert

Question

Ich mache einige Performance-kritische Python-Arbeit und möchte eine Funktion erstellen, die ein paar Elemente aus einer Liste entfernt, wenn sie bestimmte Kriterien erfüllen. Ich würde lieber keine Kopien der Liste erstellen, weil sie mit vielen wirklich großen Objekten gefüllt ist.

Funktionalität Ich möchte implementieren:

def listCleanup(listOfElements): 
    i = 0 
    for element in listOfElements: 
     if(element.meetsCriteria()): 
      del(listOfElements[i]) 
     i += 1 
    return listOfElements 

myList = range(10000) 
myList = listCleanup(listOfElements) 

ich mit den Low-Level-Arbeiten von Python nicht vertraut bin. Wird myList nach Wert oder Verweis übergeben?

Wie kann ich das schneller machen?

Ist es möglich, die List-Klasse irgendwie zu erweitern und listCleanup() darin zu implementieren?

myList = range(10000) 
myList.listCleanup() 

Thanks-

Jonathan

Answer 1

Python alles genauso passiert, aber es „nach Wert“ oder „by reference“ wird nicht klar, alles auf, da Python Semantik sind anders als die anruf Sprachen, für die diese Begriffe normalerweise gelten. Wenn ich es beschreiben würde, würde ich sagen, dass alle Weitergabe nach Wert war und dass der Wert eine Objektreferenz war. (Dies ist, warum ich es nicht sagen wollte!)

Wenn Sie ein paar Sachen aus einer Liste herausfiltern möchten, bauen Sie eine neue Liste

foo = range(100000) 
new_foo = [] 
for item in foo: 
    if item % 3 != 0: # Things divisble by 3 don't get through 
     new_foo.append(item) 

oder mit Hilfe der Liste Verständnis Syntax

new_foo = [item for item in foo if item % 3 != 0] 

Python werden die Objekte in der Liste nicht kopieren, sondern beide foo und new_foo die gleichen Objekte verweisen. (Python kopiert niemals implizit Objekte.)

---

Sie haben vorgeschlagen, dass Sie Bedenken hinsichtlich der Leistung bei diesem Vorgang haben.Die Verwendung von wiederholten del Anweisungen aus der alten Liste wird nicht zu einem Code führen, der weniger idiomatisch und verwirrender ist, aber es wird eine quadratische Leistung einführen, da die gesamte Liste jedes Mal neu gemischt werden muss.

Leistung zu adressieren:

• holen und läuft. Sie können nicht herausfinden, wie Ihre Leistung aussieht, es sei denn, Sie arbeiten mit Code. Dies wird Ihnen auch sagen, ob es Geschwindigkeit oder Platz ist, für den Sie optimieren müssen; Sie erwähnen Bedenken in Bezug auf beide in Ihrem Code, aber oft beinhaltet Optimierung eine auf Kosten der anderen zu erhalten.

• Profil. Sie können the stdlib tools für die Leistung in der Zeit verwenden. Es gibt verschiedene Speicher-Profiler von Drittanbietern, die etwas nützlich sein können, aber nicht so schön sind, mit zu arbeiten.

• Messen.Time oder Reprofile Speicher, wenn Sie eine Änderung vornehmen, um zu sehen, ob eine Änderung eine Verbesserung darstellt und wenn ja, was diese Verbesserung ist.

• Um Ihren Code speichersensitiver zu machen, werden Sie oft einen Paradigmenwechsel in der Art und Weise, wie Sie Ihre Daten speichern, verwenden, nicht Microoptimizations wie das Erstellen einer zweiten Liste zum Filtern. (Das gleiche gilt für die Zeit, wirklich: Wechsel zu einem besseren Algorithmus wird fast immer die beste Beschleunigung geben. Es ist jedoch schwieriger, über Geschwindigkeitsoptimierungen zu verallgemeinern).

  Einige gemeinsamen Paradigmenwechsel Speicherverbrauch in Python ist

  1. Mit Generatoren zu optimieren. Generatoren sind faule Iteratoren: Sie laden nicht sofort eine ganze Liste in den Speicher, sie finden heraus, was ihre nächsten Objekte im laufenden Betrieb sind. Generatoren zu verwenden, würden die Schnipsel oben aussehen

     foo = xrange(100000) # Like generators, xrange is lazy 
     def filter_divisible_by_three(iterable): 
         for item in foo: 
          if item % 3 != 0: 
           yield item 
     
     new_foo = filter_divisible_by_three(foo) 
     

     oder der Generator Ausdruck Syntax,

     new_foo = (item for item in foo if item % 3 != 0) 
     

  2. numpy für homogene Sequenzen, insbesondere diejenigen, die numerische-mathy sind. Dies kann auch Code beschleunigen, der viele Vektoroperationen ausführt.

  3. Speichern von Daten auf der Festplatte, z. B. in einer Datenbank.

Answer 2

In Python werden Listen immer als Referenz übergeben.

Die Größe der Objekte in der Liste wirkt sich nicht auf die Listenleistung aus, da die Listen nur Verweise auf die Objekte speichern. Die Anzahl der Elemente in der Liste wirkt sich jedoch auf die Leistung einiger Operationen aus - z. B. das Entfernen eines Elements, das O (n) ist.

Wie geschrieben, ist ListCleanup Worst-Case-O (n ** 2), da Sie die O (n) Del-Operation innerhalb einer Schleife haben, die potenziell O (n) ist. Wenn die Reihenfolge der Elemente nicht wichtig ist, können Sie möglicherweise den integrierten set-Typ anstelle einer Liste verwenden. Die set hat O (1) Deletionen und Insertionen. Sie müssen jedoch sicherstellen, dass Ihre Objekte unveränderlich und abwaschbar sind.

Andernfalls ist es besser, die Liste neu zu erstellen. Das ist O (n), und Ihr Algorithmus muss mindestens O (n) sein, da Sie jedes Element untersuchen müssen. Sie können die Liste in einer Zeile wie folgt filtern:

listOfElements[:] = [el for el in listOfElements if el.MeetsCriteria()] 

Answer 3

Nur klar sein:

def listCleanup(listOfElements): 
    i = 0 
    for element in listOfElements: 
     if(element.meetsCriteria()): 
      del(listOfElements[i]) 
     i += 1 
    return listOfElements 

myList = range(10000) 
myList = listCleanup(listOfElements) 

die gleiche

def listCleanup(listOfElements): 
    i = 0 
    for element in listOfElements: 
     if(element.meetsCriteria()): 
      del(listOfElements[i]) 
     i += 1 

myList = range(10000) 
listCleanup(listOfElements) 

als

ist?

Answer 4

Sieht wie vorzeitige Optimierung aus. Sie sollten versuchen, besser zu verstehen, wie Python funktioniert, bevor Sie versuchen, zu optimieren.

In diesem speziellen Fall müssen Sie sich keine Gedanken über die Objektgröße machen.Das Kopieren einer Liste mit Listenverstehen oder Slice führt nur eine Oberflächenkopie durch (Kopieren von Verweisen auf Objekte, auch wenn der Begriff nicht wirklich gut auf Python zutrifft). Die Anzahl der Elemente in der Liste kann jedoch von Bedeutung sein, da del O (n) ist. Es kann andere Lösungen geben, wie das Ersetzen eines Elements durch None oder ein konventionelles Null-Objekt oder das Verwenden einer anderen Datenstruktur wie einem Satz oder einem Wörterbuch, wo die Kosten für das Löschen eines Elements viel niedriger sind.

Answer 5

Ihre Datenstruktur zu modifizieren, während Sie darüber iterieren, ist wie sich selbst in den Fuß schießen ... Iteration schlägt fehl. Sie könnte genauso gut beraten andere nehmen und nur eine neue Liste machen:

myList = [element for element in listOfElements if not element.meetsCriteria()] 

die alte Liste - wenn es keine anderen Verweise auf sie sind - freigegeben und der Speicher freigegeben wird. besser noch, machen Sie nicht einmal eine Kopie der Liste. Ändern Sie die oben auf einen Generator Ausdruck für eine speicherVersion:

myList = (element for element in listOfElements if not element.meetsCriteria()) 

alle Python-Objekt Zugriff durch Referenz. Objekte werden erstellt und Variablen sind nur Verweise auf diese Objekte. Wenn jedoch jemand die puristische Frage stellen wollte: "Welche Art von Aufrufsemantik verwendet Python, Call-by-Reference oder Call-by-Value?" Die Antwort muss lauten: "Weder ... und beide." Der Grund dafür ist, dass Aufrufkonventionen für Python weniger wichtig sind als der Objekttyp.

Wenn ein Objekt veränderbar ist, kann es geändert werden, unabhängig davon, in welchem ​​Bereich Sie sich befinden ... Solange Sie einen gültigen Objektverweis haben, kann das Objekt geändert werden. Wenn das Objekt unveränderlich ist, dann kann dieses Objekt nicht geändert werden, egal wo Sie sind oder welche Referenz Sie haben.

Answer 6

Das Löschen von Listenelementen in-situ ist möglich, aber nicht durch Vorwärtsgehen der Liste. Ihr Code funktioniert einfach nicht - wenn die Liste schrumpft, können Sie Elemente übersehen. Du musst rückwärts gehen, so dass der schrumpfende Teil hinter dir ist, mit ziemlich schrecklichem Code. Bevor ich Ihnen das zeige, gibt es einige Vorüberlegungen:

Erstens, wie ist dieser Müll in die Liste gekommen? Vorbeugung ist besser als Heilung.

Zweitens, wie viele Elemente in der Liste und wie viel Prozent müssen wahrscheinlich gelöscht werden? Je höher der Prozentsatz, desto größer die Wahrscheinlichkeit, dass es besser ist, eine neue Liste zu erstellen.

OK, wenn Sie es noch in-situ tun wollen, betrachten dies:

def list_cleanup_fail(alist, is_bad): 
    i = 0 
    for element in alist: 
     print "i=%d alist=%r alist[i]=%d element=%d" % (i, alist, alist[i], element) 
     if is_bad(element): 
      del alist[i] 
     i += 1 

def list_cleanup_ok(alist, is_bad): 
    for i in xrange(len(alist) - 1, -1, -1): 
     print "i=%d alist=%r alist[i]=%d" % (i, alist, alist[i]) 
     if is_bad(alist[i]): 
      del alist[i] 

def is_not_mult_of_3(x): 
    return x % 3 != 0 

for func in (list_cleanup_fail, list_cleanup_ok): 
    print 
    print func.__name__ 
    mylist = range(11) 
    func(mylist, is_not_mult_of_3) 
    print "result", mylist 

und hier ist die Ausgabe:

list_cleanup_fail 
i=0 alist=[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10] alist[i]=0 element=0 
i=1 alist=[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10] alist[i]=1 element=1 
i=2 alist=[0, 2, 3, 4, 5, 6, 7, 8, 9, 10] alist[i]=3 element=3 
i=3 alist=[0, 2, 3, 4, 5, 6, 7, 8, 9, 10] alist[i]=4 element=4 
i=4 alist=[0, 2, 3, 5, 6, 7, 8, 9, 10] alist[i]=6 element=6 
i=5 alist=[0, 2, 3, 5, 6, 7, 8, 9, 10] alist[i]=7 element=7 
i=6 alist=[0, 2, 3, 5, 6, 8, 9, 10] alist[i]=9 element=9 
i=7 alist=[0, 2, 3, 5, 6, 8, 9, 10] alist[i]=10 element=10 
result [0, 2, 3, 5, 6, 8, 9] 

list_cleanup_ok 
i=10 alist=[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10] alist[i]=10 
i=9 alist=[0, 1, 2, 3, 4, 5, 6, 7, 8, 9] alist[i]=9 
i=8 alist=[0, 1, 2, 3, 4, 5, 6, 7, 8, 9] alist[i]=8 
i=7 alist=[0, 1, 2, 3, 4, 5, 6, 7, 9] alist[i]=7 
i=6 alist=[0, 1, 2, 3, 4, 5, 6, 9] alist[i]=6 
i=5 alist=[0, 1, 2, 3, 4, 5, 6, 9] alist[i]=5 
i=4 alist=[0, 1, 2, 3, 4, 6, 9] alist[i]=4 
i=3 alist=[0, 1, 2, 3, 6, 9] alist[i]=3 
i=2 alist=[0, 1, 2, 3, 6, 9] alist[i]=2 
i=1 alist=[0, 1, 3, 6, 9] alist[i]=1 
i=0 alist=[0, 3, 6, 9] alist[i]=0 
result [0, 3, 6, 9] 

Answer 7

Ich glaube nicht, dass jemand erwähnt tatsächlich Filter . Da viele der Antworten von angesehenen Leuten stammen, bin ich mir sicher, dass ich derjenige bin, dem etwas fehlt. Könnte jemand erklären, was mit diesem falsch wäre:

new_list = filter(lambda o: o.meetsCriteria(), myList)