Das deutsche Python-Forum

Ich überlege gerade, wie ich das folgende Problem angehen könnte: Ich arbeite hier mit (sehr) großen Listen, muss darauf aber eigentlich nur einfache Operationen ausführen. Das heisst ich muss durch die Liste gehen, mir die einzelnen Elemente anschauen und (je nach Werten) das gerade betrachtete Element verändern oder löschen. Wie mache ich das am besten? Die "üblichen" Lösungen wie "per for-Schleife durch die Liste wandern und dann zum Beispiel per remove(element) das Element entfernen" erscheinen mir nicht besonders effektiv. Immerhin weiß ich ja, an welcher Stelle der Liste ich zur Zeit bin, es ist also unnötig das derzeitige Element nochmal zu suchen um es zu entfernen etc.
Wie kann ich das möglichst effektiv angehen? Gibt es zum Beispiel soetwas wie Listen-interne Zeiger mit denen man arbeiten könnte? Oder irgendetwas anderes, womit sich Python merkt wo in der Liste man gerade ist um das "aktive" Element dann direkt ändern oder löschen zu können?

Hallo.

Erstmal vorweg: per for-Schleife über eine Liste zu iterieren und daraus Elemente zu löschen funktioniert nicht.

Am einfachsten ist es, wenn du eine neue Liste erstellst:

Am einfachsten wäre filtern, musst du gucken, wie schnell das ist: Ansonsten wird es problematisch, da du die Liste über die du iterierst, nicht verändern solltest. Also am besten das Ganze von hinten aufrollen: Ist aber vermutlich langsamer bei zu vielen gelöschen Elementen, da zu viel kopiert werden muss. Aber müsste weniger Speicher verbrauchen, wenn das wichtig ist und es is in place.

Soweit schon mal danke. Ein einfaches filtern klappt nicht. Die Berechnungen sind schon etwas komplizierter und hängen vor allem auch von den vorherigen Aktionen ab. Es geht also nicht nur darum die Werte "Hallo" und "Meier" rauszuwerfen, sondern wirklich jedes Element anzuschauen, zu testen ob es für die weitere Arbeit verwendet werden kann (und das hängt davon ab, welche Elemente ich bereits zuvor akzeptiert habe) und dementsprechend zu handeln. Ich weiß also auch vorher nicht, was alles rausgestrichen werden muss, das entwicklet sich erst im Laufe der Zeit. Also kann es zum Beispiel sein, dass wenn ich Element 17.987.111 gelöscht habe, dass ich dann danach Element 23.154.222 nicht mehr löschen darf. Ich muss also wirklich Schritt für Schritt durch die Liste und dann von Fall zu Fall entscheiden, was ich mit dem jeweiligen Listeneintrag mache.

Und da die Listen halt wirklich groß sind, will ich nicht jedesmal per Index auf die Einträge zugreifen, weil das heisst ja jedes mal, dass die Liste immer wieder durchlaufen werden muss um ein Element zu finden.

AllesMeins hat geschrieben: ändern oder löschen

Das ist natürlich zweierlei. Antworten auf den zweiten (bei großen Listen problematischeren) Fall hast du schon bekommen, das Ändern sollte in jedem Fall kein Problem sein. Wenn du z.B. mittels enumerate() iterierst, bekommst du den Index gleich mitgeliefert und kannst in-place die Liste ändern - genau wie ein array.

Je nach dem, wie deine Operationen und Listenelemente aussehen, könnte ein sinnvoller Weg auch der sein, dass du einmal komplett über die Liste iterierst und zu löschende Elemente nicht gleich entfernst, sondern zunächst mit einem bestimmten, eindeutigen und ansonsten nicht vorkommenden Wert belegst (0 wäre praktisch) und anschließend einmalig z.B. mittels filter eine neue Liste erzeugst, die die vorher als zu löschend markierten Werte dann rausfiltert.

AllesMeins hat geschrieben:Ich weiß also auch vorher nicht, was alles rausgestrichen werden muss, das entwicklet sich erst im Laufe der Zeit. Also kann es zum Beispiel sein, dass wenn ich Element 17.987.111 gelöscht habe, dass ich dann danach Element 23.154.222 nicht mehr löschen darf. Ich muss also wirklich Schritt für Schritt durch die Liste und dann von Fall zu Fall entscheiden, was ich mit dem jeweiligen Listeneintrag mache.

Evtl. Listenidices die gelöscht werden sollen in einer zweiten Liste speichern und danach löschen/filtern.

Und da die Listen halt wirklich groß sind, will ich nicht jedesmal per Index auf die Einträge zugreifen, weil das heisst ja jedes mal, dass die Liste immer wieder durchlaufen werden muss um ein Element zu finden.

Nein, für einen Indexzugriff wird die List nicht durchlaufen. Listen sind durch C-Arrays implementiert, d.h. das ist einfache Zeigeroperation.

Darii hat geschrieben:Nein, für einen Indexzugriff wird die List nicht durchlaufen. Listen sind durch C-Arrays implementiert, d.h. das ist einfache Zeigeroperation.

Ich denke, seine Annahme kommt daher, dass er die Lösch-Operationen mittels remove() vornehmen wollte (siehe Ausgangsposting) - in dem Fall hätte er ja Recht.

@AllesMeins: Die Komplexität der Operationen beim betrachten von Elementen und Entscheiden ob sie gelöscht werden sollen, spricht nicht gegen `filter()` oder `itertools.ifilter()`, denn das aufrufbare Objekt muss ja keine zustandslose Funktion sein, sondern kann auch eine Methode sein, oder ein Objekt das `__call__()` implementiert. Auf die Weise kann man durchaus auch Informationen von früheren Aufrufen berücksichtigen.

`remove()` wiederholt auf grosse Listen anwenden ist keine gute Idee. Du solltest schon den üblichen Weg gehen und eine neue Liste anlegen mit den gefilterten und veränderten Objekten.

Randbemerkung: Immer wenn Du "effektiv" geschrieben hast, meintest Du wahrscheinlich "effizient".

Deine Problemstellung ist eigentlich zu unklar beschrieben, so dass Dich die Hinweise vermutlich nicht so richtig weiterbringen. Slicing ist immer eine gute Idee, so fern es Sinn macht. Ebenso könnest Du mit der index() Methode arbeiten. Hier kannst Du auch optional Startindex und Endeindex angeben. Je nach dem kann es sogar Sinn machen eine ganz andere Datenstruktur zu verwenden. dict oder set. Hängt aber tatsächlich von Deinem Anwendungsfall ab.

Hmm, soweit schon mal Danke für die Anregungen. Auch wenn ich mit allen nicht so ganz glücklich bin. Irgendwie scheint mir das alles trotzdem recht ineffizient (effektiv ist in der Tat das falsche Wort, danke BlackJack). Denn beim Durchlaufen der Liste sind ja theoretisch alle Informationen da (also sprich vor allem: An welcher Stelle der Liste bin ich gerade und wo liegt das im Speicher). Da ist es mir irgendwie zuwider diese Information wegzuschmeißen und in einer neuen Operation nochmal suchen zu müssen. Und das müsste ja auch für den Zugriff per Index gelten. Wenn ich aus "heiterem Himmel" sage "ändere Listenindex 1234567", dann muss dies ja trotzdem erst mal gesucht werden - egal wie es implementiert ist. Und da es mir um den Vergleich verschiedener Methoden geht, wäre es wirklich schön das ganze möglichst "low-level" und ohne störende Einflüsse wie unnötige Mehrfach-Suchen etc. erledigen zu können.

AllesMeins hat geschrieben:Wenn ich aus "heiterem Himmel" sage "ändere Listenindex 1234567", dann muss dies ja trotzdem erst mal gesucht werden - egal wie es implementiert ist.

Das ist Bloedsinn. Die Python `list` ist ein Array und Indexzugriffe erfolgen in konstanter Zeit, die Liste muss nicht durchgegangen werden. Und das ist sehr wohl von der Implementierung abhaengig.

AllesMeins hat geschrieben:Denn beim Durchlaufen der Liste sind ja theoretisch alle Informationen da (also sprich vor allem: An welcher Stelle der Liste bin ich gerade und wo liegt das im Speicher). Da ist es mir irgendwie zuwider diese Information wegzuschmeißen und in einer neuen Operation nochmal suchen zu müssen. Und das müsste ja auch für den Zugriff per Index gelten. Wenn ich aus "heiterem Himmel" sage "ändere Listenindex 1234567", dann muss dies ja trotzdem erst mal gesucht werden - egal wie es implementiert ist.

Nein, der Listenindex *ist* die Information wo der Eintrag im Speicher liegt und zwar *weil* die Liste als C-Array implementiert ist. Glaub es mir oder nicht. Das einzige was dich das kostet, ist eine Addition, aber wenn du dir darum sorgen machst, solltest du nicht Python nehmen. Wirklich nicht. list.remove hingegen ist wirklich ineffektiv wie du richtig erkannt hast.

Sofern das etwas (natur-)wissenschaftliches ist und es sich um kein zu spezielles Problem handelt, würde ich an deiner Stelle ja mal schauen, ob es keine passende Funktionalität in einer externen Bibliothek dafür gibt. Wer weiß, ob du die Aufgabenstellung richtig angehst. Außer natürlich, du hast diesen Punkt bereits überprüft und nichts gefunden.

Schau dir doch mal numpy an. Vielleicht ist es das was du suchst?

OT: @EyDu @Darii

List comprehension ist bei sehr großen Listen eine eher schlechte Idee, schließlich wird dadurch eine Kopie erzeugt. Wenn, dann solltet ihr wenigstens auf Generatoren hinweisen:

Ausgehend von den von dir angedeuteten Größenordnungen habe ich mal eine Liste mit 30 Mio. Einträgen erzeugt.
Der Prozess des Änderns/Löschens von Elementen könnte dann etwa so aussehen: Output: Die teure Listenerzeugung ist nicht relevant, ob die anderen Zeiten für dich im Rahmen liegen, müsstest du selbst beurteilen.

cofi hat geschrieben:

AllesMeins hat geschrieben:Wenn ich aus "heiterem Himmel" sage "ändere Listenindex 1234567", dann muss dies ja trotzdem erst mal gesucht werden - egal wie es implementiert ist.

Das ist Bloedsinn. Die Python `list` ist ein Array und Indexzugriffe erfolgen in konstanter Zeit, die Liste muss nicht durchgegangen werden. Und das ist sehr wohl von der Implementierung abhaengig.

Das ist doch wesentlicher Aspekt: Ist ein Indexzugriff per Sprachdefinition immer O(1)? Oder kann es auch O(n) sein? Für einen Algorithmus ist das ja entscheidend - CPython ist ja nicht alles! Ich habe in der Doku nichts genaues dazu gefunden; dazu muss es aber doch etwas geben. Ich fände es schön, wenn einer dazu mal Referenzen posten könnte.

Hyperion hat geschrieben:Das ist doch wesentlicher Aspekt: Ist ein Indexzugriff per Sprachdefinition immer O(1)? Oder kann es auch O(n) sein?

Ja, da wird es interessant
Wenn ich so drüber nachdenke - man könnte eine Liste in der Tat so implementieren, dass ein Zugriff über die Indexnummer in O(1) funktioniert. Soweit ich das sehe geht das aber nur, indem man im Speicher die Liste komplett zusammenhängend ablegt und dann direkt addressiert "Listenbeginn + Indexnummer" und so in die entsprechende Speicherzelle springt (bzw. indirekt adressiert um mit unterschiedlich großen Listeneinträgen fertig zu werden). Solch eine Implementierung dürfte aber schon dann problematisch werden, wenn nicht genug zusammenhängender Speicher vorhanden ist. Außerdem wird an der Stelle auch das löschen sehr aufwendig, denn ich müsste ja wenn ich in der Mitte irgendetwas rauslösche den kompletten Listenblock wieder zusammenschieben, damit das direkte anspringen klappt (also sprich bis zu n/2 Verschiebeoperationen pro Löschvorgang). Da mir das als nicht besonders praktikabel erscheint bleibe ich erst mal dabei: Auch ein Indexzugriff bedeutet normalerweise, dass der entsprechende Eintrag erst mal gesucht werden muss (auch wenn man das deutlich effektiver gestalten kann, als die Suche nach einem bestimmten Wert). Da wären, aus rein wissenschaftlichem Interesse, Implementierungsdetails wirklich mal interessant.
Aber ich denke das führt zu weit. Ich hatte halt gehofft das es bei Python irgend eine Möglichkeit gibt an interne Listenzeiger heranzukommen, denn das wäre wohl das effizienteste gewesen. Aber da es das scheinbar nicht gibt, probiere ich jetzt einfach die von euch vorgeschlagenen Methoden mal durch. Auf jeden Fall schon mal vielen Dank für die zahlreichen beiträge und Ideen.

Hyperion hat geschrieben:Das ist doch wesentlicher Aspekt: Ist ein Indexzugriff per Sprachdefinition immer O(1)? Oder kann es auch O(n) sein? Für einen Algorithmus ist das ja entscheidend - CPython ist ja nicht alles!

Guter Einwand. In der Sprachreferenz wird das leider nicht erwaehnt, von Jython weiss ich, dass sie `ArrayList` nutzen. Bei PyPy werd ich aus dem Code (https://bitbucket.org/pypy/pypy/src/403 ... tobject.py) leider nicht schlau, bei IronPython hab ich jetzt nicht geschaut. IMO macht das von der Dokumentation geforderte Interface aber nicht sonderlich viel Sinn als verkettete Liste.

@OP: Wir reden von CPython? Dann ist `list` keine verkettete Liste von der du scheinbar ausgehst und nicht abruecken willst, auch wenn dir jetzt schon mehrmals gesagt wurde, dass du falsch liegst, sondern ein Array. Und ja, die Probleme existieren.

cofi hat geschrieben:IMO macht das von der Dokumentation geforderte Interface aber nicht sonderlich viel Sinn als verkettete Liste.

Da hast Du natürlich recht. Ich hätte es halt schön gefunden, etwas ähnliches wie in der Java Dokumentation zu finden:

public interface RandomAccess
Marker interface used by List implementations to indicate that they support fast (generally constant time) random access. The primary purpose of this interface is to allow generic algorithms to alter their behavior to provide good performance when applied to either random or sequential access lists.

Link

Denn dann kann ich Plattform unabhängig Algorithmen entwickeln und muss nicht auf Implementierungsdetails achten, die bei solchen Dingen ja große Auswirkungen haben können.

Irgend wo muss es dazu doch auch etwas in der Python-Doku geben!