Seite 2 von 2
Re: Effektiver Umgang mit großen Listen
Verfasst: Mittwoch 23. Februar 2011, 15:43
von AllesMeins
cofi hat geschrieben:Hyperion hat geschrieben:@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.
Re: Effektiver Umgang mit großen Listen
Verfasst: Mittwoch 23. Februar 2011, 15:49
von Hyperion
AllesMeins hat geschrieben:cofi hat geschrieben:Hyperion hat geschrieben:@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?
Re: Effektiver Umgang mit großen Listen
Verfasst: Mittwoch 23. Februar 2011, 16:01
von AllesMeins
Hyperion hat geschrieben: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.
Re: Effektiver Umgang mit großen Listen
Verfasst: Mittwoch 23. Februar 2011, 16:07
von Defnull
AllesMeins hat geschrieben:
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?
Re: Effektiver Umgang mit großen Listen
Verfasst: Mittwoch 23. Februar 2011, 16:10
von Hyperion
AllesMeins hat geschrieben:
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.
Re: Effektiver Umgang mit großen Listen
Verfasst: Mittwoch 23. Februar 2011, 16:12
von numerix
cofi hat geschrieben: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
Re: Effektiver Umgang mit großen Listen
Verfasst: Mittwoch 23. Februar 2011, 16:13
von 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.
Re: Effektiver Umgang mit großen Listen
Verfasst: Mittwoch 23. Februar 2011, 16:16
von Hyperion
numerix hat geschrieben:cofi hat geschrieben: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.
liefert Dir da hilfreiche Parameter.
Re: Effektiver Umgang mit großen Listen
Verfasst: Mittwoch 23. Februar 2011, 16:53
von numerix
Danke für die Hinweise zum Heap der JVM. Ein Aufruf der Art
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:
Die Zeiten von CPython 2.6 waren (s.o.):
Außerdem noch CPython 3.1:
Und ganz frisch CPython 3.2:
Code: Alles auswählen
16.38372302055359
8.843859910964966
1.2578709125518799
Re: Effektiver Umgang mit großen Listen
Verfasst: Mittwoch 23. Februar 2011, 17:11
von sparrow
numerix hat geschrieben:Danke für die Hinweise zum Heap der JVM. Ein Aufruf der Art
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.
zumindest an der Windows-Kiste mit Java 1.6 an der ich gerade sitze.
Re: Effektiver Umgang mit großen Listen
Verfasst: Mittwoch 23. Februar 2011, 17:42
von 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:
Laufzeiten sind dann:
Re: Effektiver Umgang mit großen Listen
Verfasst: Donnerstag 24. Februar 2011, 08:15
von Darii
AllesMeins hat geschrieben: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.
Defnull hat geschrieben: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.
Re: Effektiver Umgang mit großen Listen
Verfasst: Donnerstag 24. Februar 2011, 08:41
von 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.
lunar hat geschrieben: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.
Re: Effektiver Umgang mit großen Listen
Verfasst: Donnerstag 24. Februar 2011, 09:02
von snafu
AllesMeins hat geschrieben:cofi hat geschrieben:Hyperion hat geschrieben:@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?
AllesMeins hat geschrieben: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.
Re: Effektiver Umgang mit großen Listen
Verfasst: Donnerstag 24. Februar 2011, 09:21
von 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.
snafu hat geschrieben: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).
snafu hat geschrieben:Sobald der Speicher für die Liste nicht mehr zusammenhängend ist...
Ein Array in C respräsentiert einen zusammenhängenden Speicherbereich.
Re: Effektiver Umgang mit großen Listen
Verfasst: Donnerstag 24. Februar 2011, 09:23
von BlackJack
snafu hat geschrieben: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.
Re: Effektiver Umgang mit großen Listen
Verfasst: Donnerstag 24. Februar 2011, 09:30
von snafu
jerch hat geschrieben:snafu hat geschrieben: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?
Re: Effektiver Umgang mit großen Listen
Verfasst: Donnerstag 24. Februar 2011, 10:06
von 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“).