Alternative zu langen Listen

[HMweb]

Ich arbeite seit ein paar Monaten mit Python und stehe gerade vor einem Problem durch lange Listen, weshalb ich euch um Rat fragen möchte:

Mein Programm fragt Daten aus einer Log-Datei, berechnet eine Kennzahl und legt diese mit Zusatzinformationen in einer Liste ab. Diese Liste wird anschließend chronologisch sortiert und für eine statistische Untersuchung genutzt. Das Format der Liste ist im Prinzip so:

Code: Alles auswählen

[[Kennzahl 1, Verursacher 1, Zeitstempel 1], [Kennzahl 2, Verursacher 2, Zeitstempel 2], .... , [Kennzahl n, Verursacher n, Zeitstempel n]]

Beim Testen mit einem großen Datensatz, ist nach einiger Zeit ein OurOfMemoryError aufgetreten. Mir scheint, die Liste ist schlicht zu lang. Als Krücke hatte ich überlegt, einfach nach einer festen Anzahl von Elemente eine weitere Liste anzulegen, aber dann wäre keine chronologische Sortierung aller Daten nach Zeitstempel mehr möglich.

Daher ist meine Frage, was eine geeignete Alternative zu der (langen) Liste wäre?
Als kleine Randfrage wäre noch interessant, wie lang eigentlich eine Liste in Python sein darf? Abhängig vom RAM?

Im Voraus vielen Dank!

[Hyperion]

Daher ist meine Frage, was eine geeignete Alternative zu der (langen) Liste wäre?

Wie wäre es mir einer Datenbank? Da könnte man sowohl SQLite als auch Redis ins Auge fassen. (Neben zig anderen Lösungen )

Grundsätzlich wäre es auch noch interessant, wie die Auswertung erfolgt? Evtl. kann man dafür die Daten noch stärker aggregieren oder aber in geeignete Stücke teilen und diese dann weiter verarbeiten.

Über welche Größe von Daten reden wir denn überhaupt?

[HMweb]

Danke für die schnelle Antwort.

Die Auswertung erfolgt durch SPC. Grob gesagt werden die Kennzahlen zu Batchen zusammengefasst und deren Mittelwert gebildet. Dabei wird so lange die Batchgröße erhöht, bis die Mittelwerte einer Normalverteilung entsprechen und keine Autokorrelation aufweisen. Nun wird ein Normalniveau und Schwankungsgrenzen definiert. Im Ergebnis werden die Mittelwerte herausgepickt, die außerhalb der Schwankungsgrenzen liegen und die ursprünglichen Einzelwerte zu den gewälten Mittelwerten ausgegeben.

Das Ganze ist soweit in Python auch schon realisiert, wurde aber nur mit kleinen Test-Datensätzen (<10.000 Elemente) getestet, weil während des Skriptens nur überprüft wurde, ob das Programm überhaupt das tut, was es soll. Mit Echtdaten, die ein paar Mio Ereignisse haben kommt die Programmierung nun ins Straucheln. Ich komme nicht von der Programmier-Schiene, sondern nutze das als Tool für die eigentlichen Untersuchungen der Daten. Deswegen war vielleicht der Ansatz mit Listen schon eher unklug.

Daher war als erste Idee auch die Krücke mit mehreren Listen naheliegend, weil der ganze Rest des Programms eben für Listen erstellt wurde.

[BlackJack]

@HMweb: Wie schon von Hyperion vorgeschlagen: Wenn die Datenmenge den Hauptspeicher sprengt, dann greift man üblicherweise zur Datenbank.

Zur Randfrage: Das ist normalerweise durch den Speicher begrenzt, den ein Prozess addressieren kann.

Bei ein paar Millionen Datensätzen kann der Hauptspeicher auch knapp werden, wenn man sorgfältig darauf achtet keine grösseren Datenmengen unnötig anzuhäufen, aber gerade bei Gelegenheitsprogrammierern könnte es vielleicht dort noch Verbesserungspotential geben. Solche Auswertungsskripte neigen manchmal dazu alles auf Modulebene, also ohne Funktionen, zu machen und jedes Zwischenergebnis an einen anderen Namen zu binden, so dass am Ende ganz viele Daten im Speicher gehalten werden, die eigentlich gar nicht mehr benötigt werden.

Typisches Beispiel wäre das Laden aller Zeilen aus der Eingabedatei in eine Liste um dann in einer Schleife eine Liste mit den extrahierten Daten zu erzeugen.

Wieso muss eigentlich nach Zeitsstempeln sortiert werden? Die meisten Logdateien sind doch schon von Haus aus chronologisch sortiert.

`numpy`-Arrays statt Python-Listen wären vielleicht noch eine Möglichkeit. Und falls das dann auch nicht in den Speicher passt vielleicht `PyTables` als Datenbank.

[snafu]

Versuchsweise könntest du dein Programm auch mal mit PyPy (gibt's in vielen Linux-Distributionen als Paket) laufen lassen. Gerade in Version 1.8 wurden einige Verbesserungen hinsichtlich Performance und Speicherverbrauch von Listen mit homogenen Datentypen gemacht (s. http://morepypy.blogspot.de/2012/02/pyp ... usual.html). Eventuell kannst du deinen Nutzen daraus ziehen.

[HMweb]

Vielen Dank für die hilfreichen Tipps.

Leider ist mir die eingesetzte Python-Umgebung vorgegeben, weshalb der Griff zu PyPy wohl nicht klappt. Die Log-Daten ordnen für jeden Ort die Ereignisse chronologisch. Für die SPC braucht es aber chronologisch alle Ereignisse im Gesamtsystem unabhängig vom Ort. Deshalb komme ich um das Umsortieren nicht herum.

Ich bin mir ziemlich sicher, dass das Programm noch Effizienzpotenzial hat. Gelegenheitsprogrammierer trifft es da ganz gut aber Listen scheinen mir nach euren Aussagen nicht die beste Lösung sein. Dann werde ich mir mal die vorgeschlagenen Arrays und PyTables anschauen.

[Sirius3]

Hallo HMweb,
um auf Deine ursprüngliche Frage zurück zu kommen: es hilft normalerweise nichts eine
sehr lange Liste in viele kürzere aufzuteilen um Speicher zu sparen.
Dagegen kennt Python list und tuple. Tuple können im nachhinein nicht mehr verändert
werden, sparen aber einiges an Speicher ein. Bei Deiner doppelten Liste solltest Du also
die inneren 4er-Pakete als Tuple schreiben (mit runden statt eckigen Klammern):

Code: Alles auswählen

[(Kennzahl 1, Verursacher 1, Zeitstempel 1), (Kennzahl 2, Verursacher 2, Zeitstempel 2), .... , (Kennzahl n, Verursacher n, Zeitstempel n)]

Bei der von Dir beschriebenen Datenmenge bietet sich aber eine Datenbank definitiv an,
da sie unabhängig vom RAM beliebig viele Einträge aufnehmen kann, sehr effizient sortieren
kann und auch komplexere Operationen auf die Werte anwendbar sind.

Grüße
Sirius

[HMweb]

Das Tupel sparsamer als Listen sind wusste ich nicht. Für das aktuelle Problem wird es eine andere Datenhaltung werden, aber für das zukünftige Programmieren werde ich das benutzen. Danke!