Listenkomprehension in Python: effiziente Auswahl in einer Liste

StackOverflow https://stackoverflow.com/questions/1222677

  •  10-07-2019
  •  | 
  •  

Frage

Nehmen wir an, dass ich eine Liste von Elementen haben, und ich möchte einige von ihnen wählen nur nach einer bestimmten Funktion (zum Beispiel eine Abstand zu einem anderen Element).

Ich möchte als Ergebnis eine Liste von Tupel haben, mit dem Abstand und dem Element. So schrieb ich den folgenden Code 

result = [ ( myFunction(C), C) for C in originalList if myFunction(C) < limit ]

Aber myFunction ist eine sehr zeitaufwendige Funktion und die originalList ziemlich groß. So wie das zu tun, wird myFunction zweimal für jedes ausgewählte Element nennen werden.

Also, gibt es eine Möglichkeit, dies zu vermeiden ??

Ich habe zwei andere Möglichkeiten, aber sie sind nicht so gut:

  1. die erste, die erstellen ungefilterte Liste 

    unfiltered = [ (myFunction(C),C) for C in originalList ]

    und dann sortieren 

    result = [ (dist,C) for dist,C in unfiltered if dist < limit ]

    aber in diesem Fall habe ich mein Duplikat originalList und etwas Speicher verschwenden (Die Liste könnte ziemlich groß sein - mehr als 10.000 Elemente)

  2. das zweite ist heikel und nicht sehr pythonic, aber effizient (das Beste, was wir tun können, da die Funktion pro Element einmal ausgewertet werden soll). myFunction speichert sie zuletzt
    resultiert in einer globalen Variablen (lastResult zum Beispiel), und dieser Wert wird wieder verwendet, in dem Liste Verständnis 

    result = [ (lastResult,C) for C in originalList if myFunction(C) < limit ]

Haben Sie eine bessere Idee, um das zu erreichen, in einem effizienten und pythonic Weg ??

Vielen Dank für Ihre Antworten.

War es hilfreich?

Lösung

Sicher, der Unterschied zwischen den beiden folgenden: 

[f(x) for x in list]

und folgt aus: 

(f(x) for x in list)

ist, dass die erste, die Liste im Speicher erzeugen wird, während die zweiten ein neuer Generator, mit lazy evaluation ist.

Also, schreiben Sie einfach die „ungefiltert“ -Liste als Generator statt. Hier ist der Code, mit dem Generator inline: 

def myFunction(x):
    print("called for: " + str(x))
    return x * x

originalList = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
limit = 10
result =   [C2 for C2 in ((myFunction(C), C) for C in originalList) if C2[0] < limit]
# result = [C2 for C2 in [(myFunction(C), C) for C in originalList] if C2[0] < limit]

Beachten Sie, dass Sie keinen Unterschied im Ausdruck von den beiden sehen werden, aber wenn Sie waren auf der Speichernutzung suchen, die zweite Aussage, die wird auf Kommentar gesetzt ist mehr Speicherplatz.

eine einfache Änderung in Ihrer Frage, um Ihren Code zu tun, umschreiben ungefiltert wie folgt aus: 

unfiltered = [ (myFunction(C),C) for C in originalList ]
             ^                                         ^
             +---------- change these to (..) ---------+
                                 |
                                 v
unfiltered = ( (myFunction(C),C) for C in originalList )

Andere Tipps

Sie keine Liste Verständnis verwenden; ein normaler for-Schleife ist hier in Ordnung.

berechnen Sie die Abstände vorher und dann die Ergebnisse filtern: 

with_distances = ((myFunction(C), C) for C in originalList)
result = [C for C in with_distances if C[0] < limit]

Hinweis: anstatt eine neue Liste zu bauen, verwende ich einen Generator Ausdruck der Abstand / Elementpaare zu bauen

.

Einige Optionen:

  • Verwenden Sie memoization
  • Verwenden Sie einen normalen for-Schleife
  • Erstellen Sie eine ungefilterte Liste, dann filtern Sie (Ihre Option 1). Der ‚verschwendete‘ Speicher wird von der GC sehr schnell zurückgewonnen werden. - es ist nicht etwas, das man sich Sorgen machen muß

Lasse V. Karlsen hat eine ausgezeichnete Antwort auf Ihre Frage.

Wenn die Entfernungsberechnung langsam ist, ich denke, Ihre Elemente sind Polylinien, oder so ähnlich, nicht wahr?

Es gibt viele Möglichkeiten, um es schneller:

  • Wenn der Abstand zwischen Begrenzungsbox von Objekten> X, dann folgt daraus, dass der Abstand zwischen diesen Objekten ist> X. Sie müssen also nur Abstand zwischen Begrenzungsrahmen berechnen.

  • Wenn Sie alle Objekte wollen, die weniger als X von Objekt A in einem Abstand sind, werden nur Objekte, deren Begrenzungsrahmen Feld schneiden, um eine der Begrenzungs von X vergrößert sind mögliche Übereinstimmungen.

den zweiten Punkt Verwenden Sie wahrscheinlich viele Kandidaten Matches fallen kann und nur die langsame Berechnung tun, wenn nötig.

Bounding Box müssen vorher im Cache gespeichert werden.

Wenn Sie wirklich eine Menge von Objekten haben Sie auch Partitionierung Raum könnte ...

oder konvex umschließenden Polys, wenn Sie sind in 3D

Rather eine globale Variable wie in Ihrer Option 2 als verwenden, können Sie sich darauf verlassen können, dass in Python Parameter Objekt übergeben werden - das heißt, das Objekt, das in Ihre myFunction Funktion übergeben wird, ist die gleiche Objekt als ein in der Liste (dies ist nicht genau die gleiche wie call by reference, aber es ist nah genug).

Also, wenn Ihr myFunction ein Attribut auf das Objekt festgelegt - etwa _result - Sie von diesem Attribut filtern können: 

result = [(_result, C) for C in originalList if myFunction(C) < limit]

und Ihre myFunction könnte wie folgt aussehen: 

def myFunction(obj):
    obj._result = ... calculation ....
    return obj._result

Was ist los mit der Option 1?

„meine Originalliste kopieren und etwas Speicher verschwenden (die Liste könnte ziemlich groß sein - mehr als 10.000 Elemente)“

10.000 Elemente ist nur 10.000 Zeiger auf Tupel, die vorhandenen Objekte zeigen. Denken Sie 160K oder so die Erinnerung. Kaum der Rede wert.

Lizenziert unter: CC-BY-SA mit Zuschreibung
Nicht verbunden mit StackOverflow
scroll top