Effektiver Umgang mit großen Listen

[AllesMeins]

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

Ja, das ändert ja nichts an der Tatsache dass beim iterieren durch die Liste irgendwo ein Zeiger sein muss, wo man gerade ist. Und wenn die Sprache das hergeben würde, dann könnte man das auch ausnutzen. Vollkommen egal ob die Liste als verkette Liste oder als Array implementiert ist. Aber egal, wenn es nicht geht, dann gehts halt nicht.

[Hyperion]

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

Ich hab das nicht gesagt, cofi wars!

Ja, das ändert ja nichts an der Tatsache dass beim iterieren durch die Liste irgendwo ein Zeiger sein muss, wo man gerade ist. Und wenn die Sprache das hergeben würde, dann könnte man das auch ausnutzen. Vollkommen egal ob die Liste als verkette Liste oder als Array implementiert ist. Aber egal, wenn es nicht geht, dann gehts halt nicht.

Zeiger gibt es in Python nun mal nicht. Aber was willst Du denn da ausnutzen? Kapiere ich nicht. Du schriebst ja etwas davon, dass man bei einem Element evtl. erkennt, dass man spätere Elemente nicht löschen darf. Was nützt Dir denn da der "Zeiger" auf das aktuelle Element?

[AllesMeins]

Zeiger gibt es in Python nun mal nicht. Aber was willst Du denn da ausnutzen? Kapiere ich nicht. Du schriebst ja etwas davon, dass man bei einem Element evtl. erkennt, dass man spätere Elemente nicht löschen darf. Was nützt Dir denn da der "Zeiger" auf das aktuelle Element?

Ich muss sowieso alle Elemente durchgehen und in jedem Schritt auch immer nur dieses eine derzeit gelesene Element bearbeiten. Und da wäre es halt einfach sehr effizient sich einfach die Speicherposition merken zu können und dann direkt wieder darauf zuzugreifen ohne das Python im Hintergrund mehrfach die Speicherposition suchen muss.
Das mit den späteren Elementen bezog sich nur darauf, dass ich nicht von vorneherein sagen kann "Alle Elemente mit Wert X sollen raus", sondern sich die Anforderungen mit meinen Aktionen ändern. Ich will aber nicht in der Liste "rumspringen", sondern würde mir nur (stark vereinfacht) merken: "Okay, ich habe Werte X, Y und Z" bereits gelöscht also darf ich Wert A nicht mehr löschen (falls ich an einem vorbei kommen sollte). Hätte ich X, Y und Z aber noch nicht gefunden könnte A gelöscht werden (oder soetwas).

Nachtrag:
Also wie gesagt. Unterm Strich ging es mir um eine möglichst effiziente Methode Listeneinträge einen nach dem anderen abarbeiten zu können. Wenn es da aber nichts direktes gibt, dann nehm ich einfach die existierenden methoden. Ist auch kein beinbruch, anders wäre es nur schöner gewesen.

[Defnull]

Ich muss sowieso alle Elemente durchgehen und in jedem Schritt auch immer nur dieses eine derzeit gelesene Element bearbeiten. Und da wäre es halt einfach sehr effizient sich einfach die Speicherposition merken zu können und dann direkt wieder darauf zuzugreifen ohne das Python im Hintergrund mehrfach die Speicherposition suchen muss.

Die "Speicherposition" ist der Index der Liste. Mehr brauchst du nicht. Index-Zugriff ist O(1). Was willst du mehr?

[Hyperion]

Ich muss sowieso alle Elemente durchgehen und in jedem Schritt auch immer nur dieses eine derzeit gelesene Element bearbeiten. Und da wäre es halt einfach sehr effizient sich einfach die Speicherposition merken zu können und dann direkt wieder darauf zuzugreifen ohne das Python im Hintergrund mehrfach die Speicherposition suchen muss.

Dazu muss man aber - unabhängig von Python - doch immer eine Art Suche durchführen! Denn alleine das Wort "merken" impliziert ja, dass Du die Position (bzw. allgemeiner eine Zugriffsmöglichkeit) irgend wo ablegst, um später darauf zuzugreifen. Und dieser spätere Zugriff kostet nun einmal. Das kannst Du also nicht verhindern.

Die Fragen, um die sich alles dreht, sind also doch schlicht und ergreifend, ob Du bei der gewählten Datenstruktur konstante Kosten erreichst, oder nicht und ob das ggf. von der Implementierung des verwendeten Interpreters abhängig ist?

Nach Klärung dieser Fragen kann man sich dann ggf. immer noch Gedanken darüber machen, ob eine andere Datenstruktur bessere Bedingungen für Dein Problem bietet.

[numerix]

von Jython weiss ich, dass sie `ArrayList` nutzen.

Habe meinen Code oben gerade mit Jython 2.5 ausgeführt:

Code: Alles auswählen

Traceback (most recent call last):
  File "largelist.py", line 5, in <module>
    data = [int(random()*500000) for k in xrange(3*10**7)]
java.lang.OutOfMemoryError: Java heap space

[lunar]

@Hyperion: Die „Referenzimplementierung“ CPython hat konstante Komplexität, und insofern werden sich die anderen Implementierungen wohl daran orientieren. Eine verkettete Liste ist in imperativen Sprachen auch ein eher unnatürliches Konstrukt, und findet eher in funktionalen Sprachen Anwendung.

@AllesMeins: Was genau willst Du an einem „Zeiger“ denn ausnutzen?! Bei einem Feld sind Indexzugriff und Zugriff über einen Zeiger auf das aktuelle Element faktisch identisch. In C bedeutet "a[10]" nichts anderes als "*(a + 10)", also ein direkter Speicherzugriff. Genau deswegen geschieht der Index-Zugriff auf Felder ja in konstanter Zeit.

In Python werden beim Index-Zugriff natürlich noch Attributzugriff und diverse andere Dinge durchgeführt werden. Das aber sind inhärente Operationen des Python-Interpreters, die sich aus dem Objekt- und Ausführungsmodell von Python ergeben. Wenn Dir das zu „ineffizient“ ist, dann darfst Du nicht Python programmieren.

@numerix: Das ist eine künstliche Grenze, der der JVM zur Verfügung stehende Speicher lässt sich über Kommandozeilenoptionen erhöhen.

[Hyperion]

von Jython weiss ich, dass sie `ArrayList` nutzen.

Habe meinen Code oben gerade mit Jython 2.5 ausgeführt:

Code: Alles auswählen

Traceback (most recent call last):
  File "largelist.py", line 5, in <module>
    data = [int(random()*500000) for k in xrange(3*10**7)]
java.lang.OutOfMemoryError: Java heap space

Das liegt afair an der JVM, die per Default meist nur mit einer relativ geringen Speichermenge gestartet wird. Die kann dann keinen Speiche mehr dynamisch dazu allozieren (Oder darf?). Daher muss man diese Speichergröße beim Start einer JVm Instanz einstellen.

Code: Alles auswählen

java -X

liefert Dir da hilfreiche Parameter.

[numerix]

Danke für die Hinweise zum Heap der JVM. Ein Aufruf der Art

Code: Alles auswählen

jython -DXms=4000000000 largelist.py

sollte nach meinem Verständnis bewirken, dass der Heap eine Ausgangsgröße von rund 4 GB erhält. Richtig?
Falls ja, war auch das noch nicht genug ...

Interessant auch pypy (Version 1.3.0, entspricht Python 2.5.2). Laufzeiten für den Code oben:

Code: Alles auswählen

402.39693594
110.075237036
5.70352101326

Die Zeiten von CPython 2.6 waren (s.o.):

Code: Alles auswählen

18.1248118877
7.88669085503
1.17805695534

Außerdem noch CPython 3.1:

Code: Alles auswählen

16.6592679024
8.52411317825
1.23679995537

Und ganz frisch CPython 3.2:

Code: Alles auswählen

16.38372302055359
8.843859910964966
1.2578709125518799

[sparrow]

Danke für die Hinweise zum Heap der JVM. Ein Aufruf der Art

Code: Alles auswählen

jython -DXms=4000000000 largelist.py

sollte nach meinem Verständnis bewirken, dass der Heap eine Ausgangsgröße von rund 4 GB erhält. Richtig?
Falls ja, war auch das noch nicht genug ...

Nee, das ist doch keine System-Property die du das setzt.

Code: Alles auswählen

java -Xms512m -Xmx4096m

zumindest an der Windows-Kiste mit Java 1.6 an der ich gerade sitze.

[numerix]

Da jython selbst die Parameter -X... nicht kennt, dachte ich, über -DX... könnte ich das erreichen.
Auf die Idee, jython selbst explizit über einen Aufruf von java zu starten, bin ich zunächst nicht gekommen. So funktioniert es:

Code: Alles auswählen

java -Xms512m -Xmx4096m -jar jython.jar largelist.py

Laufzeiten sind dann:

Code: Alles auswählen

39.0980000496
34.8320000172
4.34000015259

[Darii]

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

Das schrieb ich schon…

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

[...]

Ich muss sowieso alle Elemente durchgehen und in jedem Schritt auch immer nur dieses eine derzeit gelesene Element bearbeiten. Und da wäre es halt einfach sehr effizient sich einfach die Speicherposition merken zu können und dann direkt wieder darauf zuzugreifen ohne das Python im Hintergrund mehrfach die Speicherposition suchen muss.

Wie oft muss ich eigentlich noch schreiben, dass das ein C-Array und der Integer der Index des Eintrags? Da muss nichts gesucht werden, der Index *ist* die Speicheradresse minus eine Konstante.

List comprehension ist bei sehr großen Listen eine eher schlechte Idee, schließlich wird dadurch eine Kopie erzeugt.

Habe ich doch geschrieben…und der Generator bringt dort auch nicht sehr viel, wenn AllesMeins hinterher wieder eine Liste braucht.

[snafu]

Python speichert also folglich die Speicheradresse des jeweils ersten Elements von einer Liste ab. Diese Information ist dann meinetwegen erreichbar über den vom Benutzer festgelegten Namen `mylist`. Wenn `mylist` einen Verweis auf die Speicheradresse 1240 enthält, dann bedeutet `mylist[3]` nichts anderes als den Inhalt von Speicheradresse 1243 zu holen, und zwar ohne, dass man dafür irgendwas über die Vorgänger-Elemente wissen muss. Ist doch richtig, oder?

Aber wenn dem so ist, dann verstehe ich die (nicht zitierten) Einwände von AllesMeins durchaus: Sobald der Speicher für die Liste nicht mehr zusammenhängend ist, klappt dieser "Trick" nicht mehr. Dies ist ja bei sehr großen Listen nicht unwahrscheinlich. Wie wird denn dann verfahren, um möglichst effizient zu bleiben? Ich könnte mir ja vorstellen, dass die Listen in Teil-Listen umgewandelt werden, so dass zusätzlich "nur" die Informationen aus dem letzten Element der Teil-Liste geholt werden müssen, um zu wissen, wo es weitergeht. Aber das ist erstmal geraten.

Bei einem Feld sind Indexzugriff und Zugriff über einen Zeiger auf das aktuelle Element faktisch identisch. In C bedeutet "a[10]" nichts anderes als "*(a + 10)", also ein direkter Speicherzugriff. Genau deswegen geschieht der Index-Zugriff auf Felder ja in konstanter Zeit. In Python werden beim Index-Zugriff natürlich noch Attributzugriff und diverse andere Dinge durchgeführt werden. Das aber sind inhärente Operationen des Python-Interpreters, die sich aus dem Objekt- und Ausführungsmodell von Python ergeben.

Das heißt also, dass Python die konkrete Ablage der Werte und den späteren Zugriff komplett dem C-Array überlässt? Keine schlechte Idee, da das Rad ja hier kaum neu erfunden werden muss. Python greift also nur noch vor dem eigentlichen Zugriff mit seiner eigenen "Interpretation" ein, d.h. unter Beachtung einer möglichen alternativen `__index__()`-Implementierung seitens des Python-Programmierers, wenn ich das richtig sehe.

[snafu]

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

Ja, das ändert ja nichts an der Tatsache dass beim iterieren durch die Liste irgendwo ein Zeiger sein muss, wo man gerade ist. Und wenn die Sprache das hergeben würde, dann könnte man das auch ausnutzen. Vollkommen egal ob die Liste als verkette Liste oder als Array implementiert ist. Aber egal, wenn es nicht geht, dann gehts halt nicht.

Finde dich damit ab: Der "Zeiger" ist der Index. Und den bekommst du mit `enumerate()`. Was hälst du eigentlich genau von dem genannten Vorschlag, die zu löschenden Elemente zu markieren und dann in bestimmten Abständen in einem Rutsch zu löschen?

Das mit den späteren Elementen bezog sich nur darauf, dass ich nicht von vorneherein sagen kann "Alle Elemente mit Wert X sollen raus", sondern sich die Anforderungen mit meinen Aktionen ändern. Ich will aber nicht in der Liste "rumspringen", sondern würde mir nur (stark vereinfacht) merken: "Okay, ich habe Werte X, Y und Z" bereits gelöscht also darf ich Wert A nicht mehr löschen (falls ich an einem vorbei kommen sollte). Hätte ich X, Y und Z aber noch nicht gefunden könnte A gelöscht werden (oder soetwas).

Speichere die zu löschenden Indizes halt irgendwo ab. Du wirst, so wie sich das anhört, einfach nicht um die Verwendung des Tupels `(index, value)`, wie er von `enumerate()` zurückgeliefert wird, herumkommen. Falls das für dich nicht akzeptabel ist, dann dürfte Python in dieser Hinsicht nichts für dich sein.

[jerch]

Ich muss an dieser Stelle doch mal die Bitte loswerden, sich mal kurz mit C-Arrays auseinanderzusetzen. Dann erübrigen sich die Mutmaßungen ziemlich schnell.

Wenn `mylist` einen Verweis auf die Speicheradresse 1240 enthält, dann bedeutet `mylist[3]` nichts anderes als den Inhalt von Speicheradresse 1243 zu holen, und zwar ohne, dass man dafür irgendwas über die Vorgänger-Elemente wissen muss. Ist doch richtig, oder?

Im Prinzip ja, wobei die Größe der Speicherzelle von Typen des C-Arrays abhängt. Auf Bytes runtergebrochen, ist die die Speicherstelle von mylist[3]: (mylist + 3 * Größe eines Elementes in Bytes)
Für typisierte Arrays übernimmt aber der Compiler die Einbeziehung der Elementgröße in die Pointerarithmetik und es verkürzt sich auf (mylist + 3).

Sobald der Speicher für die Liste nicht mehr zusammenhängend ist...

Ein Array in C respräsentiert einen zusammenhängenden Speicherbereich.

[BlackJack]

Sobald der Speicher für die Liste nicht mehr zusammenhängend ist, klappt dieser "Trick" nicht mehr. Dies ist ja bei sehr großen Listen nicht unwahrscheinlich. Wie wird denn dann verfahren, um möglichst effizient zu bleiben?

Der Speicher für eine Liste [1]_ ist immer zusammenhängend. Wie sollte der Speicher für eine bestehende Liste denn "unzusammenhängend" werden!?

Wenn nicht mehr genügend zusammenhängender Speicher für die Neuanlage einer Liste mit einer bestimmten internen Kapazität vorhanden ist, dann gibt es ganz einfach einen `MemoryError`. Und beim dynamischen Aufbau einer Liste sollte man auch damit rechnen, dass mindestens doppelt so viel Speicher benötigt wird, wie für die endgültige Liste. Wenn es dumm läuft, auch gerne mal dreimal so viel.


.. [1] Ich gehe hier von den "dynamischen Arrays" aus, die im Grunde bei allen gängigen Python-Implementierungen gleich sind.

[snafu]

Sobald der Speicher für die Liste nicht mehr zusammenhängend ist...

Ein Array in C respräsentiert einen zusammenhängenden Speicherbereich.

Ich bezog mich auf eine 500MB große Liste, die nicht als zusammenhängender Speicherbereich repräsentiert werden kann. Aber vermutlich ist mein Verständnis von "Speicherbereich" auch einfach falsch. Ich stelle mir den Begriff so vor, dass tatsächlich (physisch) hintereinanderliegende Bereiche des Arbeitsspeichers genutzt werden. Aber damit ist eher eine abstrakte Sache gemeint, oder?

[lunar]

@snafu: Speicheranforderungen eines Prozesses, welche die Seitengröße übersteigen, liegen in den seltensten Fällen (oder zumindest nicht unter Garantie) kontinuierlich im physikalischen Speicher, da es der Speicherverwaltung des Systems freisteht, wie virtuelle Speicherseiten auf physikalische Speicherseiten abzubilden sind.

Der Prozess selbst aber sieht in seinem virtuellen Speicher natürlich 500 MB zusammenhängenden Speicher, egal wie dieser im physikalischen Speicher gestückelt ist. Dafür sorgen das System und die MMU des Prozessors, die auf Speicheranforderungen des Prozesses reagieren, und die Adressen aus dem virtuellen Speicher auf physikalische Adresse umbilden (und die nötigen Seiten eventuell noch in den Arbeitsspeicher „einlagern“).