Effektiver Umgang mit großen Listen

Wenn du dir nicht sicher bist, in welchem der anderen Foren du die Frage stellen sollst, dann bist du hier im Forum für allgemeine Fragen sicher richtig.
AllesMeins
User
Beiträge: 63
Registriert: Donnerstag 20. November 2003, 13:45
Wohnort: Frankfurt/M.

Dienstag 22. Februar 2011, 17:48

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?
EyDu
User
Beiträge: 4877
Registriert: Donnerstag 20. Juli 2006, 23:06
Wohnort: Berlin

Dienstag 22. Februar 2011, 17:53

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:

Code: Alles auswählen

>>> [x for x in range(10) if x%2]
[1, 3, 5, 7, 9]
>>> filter(lambda x: x%2, range(10))
[1, 3, 5, 7, 9]
Das Leben ist wie ein Tennisball.
Darii
User
Beiträge: 1177
Registriert: Donnerstag 29. November 2007, 17:02

Dienstag 22. Februar 2011, 17:55

Am einfachsten wäre filtern, musst du gucken, wie schnell das ist:

Code: Alles auswählen

[element for element in a_list if not should_be_deleted(element)]
Ansonsten wird es problematisch, da du die Liste über die du iterierst, nicht verändern solltest. Also am besten das Ganze von hinten aufrollen:

Code: Alles auswählen

for i in xrange(len(a_liste)-1, -1, -1):
    if should_be_deleted(a_liste[i]): del a_liste[i]
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.
AllesMeins
User
Beiträge: 63
Registriert: Donnerstag 20. November 2003, 13:45
Wohnort: Frankfurt/M.

Dienstag 22. Februar 2011, 18:17

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.
Zuletzt geändert von AllesMeins am Dienstag 22. Februar 2011, 18:21, insgesamt 1-mal geändert.
Benutzeravatar
numerix
User
Beiträge: 2696
Registriert: Montag 11. Juni 2007, 15:09

Dienstag 22. Februar 2011, 18:20

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.
Darii
User
Beiträge: 1177
Registriert: Donnerstag 29. November 2007, 17:02

Dienstag 22. Februar 2011, 18:48

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.
Benutzeravatar
numerix
User
Beiträge: 2696
Registriert: Montag 11. Juni 2007, 15:09

Dienstag 22. Februar 2011, 19:29

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.
BlackJack

Dienstag 22. Februar 2011, 19:31

@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".
Benutzeravatar
hendrikS
User
Beiträge: 420
Registriert: Mittwoch 24. Dezember 2008, 22:44
Wohnort: Leipzig

Dienstag 22. Februar 2011, 19:59

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.
AllesMeins
User
Beiträge: 63
Registriert: Donnerstag 20. November 2003, 13:45
Wohnort: Frankfurt/M.

Mittwoch 23. Februar 2011, 01:10

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.
Benutzeravatar
cofi
Python-Forum Veteran
Beiträge: 4432
Registriert: Sonntag 30. März 2008, 04:16
Wohnort: RGFybXN0YWR0

Mittwoch 23. Februar 2011, 01:55

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.
Darii
User
Beiträge: 1177
Registriert: Donnerstag 29. November 2007, 17:02

Mittwoch 23. Februar 2011, 07:53

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.
Benutzeravatar
snafu
User
Beiträge: 6353
Registriert: Donnerstag 21. Februar 2008, 17:31
Wohnort: Gelsenkirchen

Mittwoch 23. Februar 2011, 08:29

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.
Rekrul
User
Beiträge: 78
Registriert: Dienstag 7. Dezember 2010, 16:23

Mittwoch 23. Februar 2011, 09:17

Schau dir doch mal numpy an. Vielleicht ist es das was du suchst?
Benutzeravatar
Defnull
User
Beiträge: 778
Registriert: Donnerstag 18. Juni 2009, 22:09
Wohnort: Göttingen
Kontaktdaten:

Mittwoch 23. Februar 2011, 11:37

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:

Code: Alles auswählen

>>> (x for x in xrange(sys.maxint) if x%2)
<generator object <genexpr> at 0xb76bb57c>
Bottle: Micro Web Framework + Development Blog
Antworten