MemoryError: Suche eine gute Datenstruktur

[Tyrax]

Hallo Gemeinde,

ich muss eine Reihe von Datensätzen zusammenfügen und bin dabei an die Grenzen des Speichers gelangt. Mein bisheriges Konzept war es, die Daten (Häufigkeitsverteilungen) in Listen einzulesen und diese dann elementweise aufzuaddieren. Naja, es sind viele lange Listen, der Speicher reicht nicht. Da die Verteilungen fast überall Nullen enthalten, wäre ich einer Lösung sehr nah, wenn ich nur die Einträge meiner Verteilung speichern würde, wo keine Null steht. Ich könnte das wohl mit nem dictionary machen, indem ich Paare "Index:Eintrag" aufnehme und alles weglasse, wo "Eintrag"=0 gilt.

Ich vermute allerdings, dass es für sowas bessere Methoden gibt. Meine Frage also:

Ich habe: Viele Verteilungen in Ausgabedateien.
Ich will: Eine zusammenfassende Verteilung.

Was ist die Methode, das Objekt der Wahl?

Danke und Grüße

Tyrax

[BlackJack]

@Tyrax: Brauchst Du die Listen denn? Statt die Elemente erst in Listen zu speichern und sie dann zu addieren, könntest Du ja vielleicht auch gleich die Elemente addieren!?

[Tyrax]

Hmm, natürlich kann ich die Sache anders angehen. Ich kann zum Beispiel die Dateien, deren Inhalt ich verarbeiten will, mehrfach auslesen - im Extremfall für jeden Verteilungsindex einmal. Damit würde ich mein Problem dann weniger speicherintensiv, jedoch deutlich rechenintensiver machen. Das wäre wohl eine Lösung, wenn auch in meinen Augen keine schöne.

Ich formuliere mein Problem nochmal etwas expliziter, vielleicht hat ja noch jemand einen guten Vorschlag.

Ich habe rund 100 Dateien mit Inhalt der Form:

Code: Alles auswählen

17;345;6238;99;42; ...;1

deren Länge (Anzahl der Eintäge) jeweils z.B. rund 10^6 ist. Diese will ich elementweise aufaddieren. Das Ergebnis soll also so aussehen:

Code: Alles auswählen

Summe der ersten Einträge; Summe der zweiten Einträge; ...

Beim Auslesen, Zwischenspeichern und Aufaddieren gehe ich mit Sicherheit nicht optimal vor. Da es sein kann, dass ich den selben Kram auch mit deutlich größeren Listen machen will, suche ich nun nach einer guten Strategie.

(Dass in den ursprünglichen Dateien sehr viele Nullen stehen, kann man sicher ausnutzen. Mit der eigentlichen Aufgabe hat das jedoch nichts zu tun.)

Grüße, Tyrax

[frabron]

Vielleicht verstehe ich dein Problem nicht so ganz. Du willst die Werte einer Zeile innerhalb einer Datei spaltenweise aufsummieren? Das geht doch mit dem csv.reader ganz einfach!? Nur so als Anhalt:

Aus der Dokub bez. Iterieren:

Code: Alles auswählen

>>> import csv
>>> spamReader = csv.reader(open('eggs.csv', 'rb'), delimiter=' ', quotechar='|')
>>> for row in spamReader:
...     print ', '.join(row)
Spam, Spam, Spam, Spam, Spam, Baked Beans
Spam, Lovely Spam, Wonderful Spam

Aufsummieren:

Code: Alles auswählen

>>> a = [1,2,3]
>>> sum = 0
>>> for i in a:
...     sum += i
...
>>> print sum
6
>>>

Man verzeihe mir die bescheuerten Variablennamen
Jetzt musst du nur noch beides kombinieren und fertig. Oder hakt es bei dir ganz woanders?

[BlackJack]

@Tyrax: Die Problembeschreibung ist noch nicht ausreichend. Was bedeutet "Summe der ersten Einträge; Summe der zweiten Einträge; ..."? Was *genau* wird da aufsummiert? Letztendlich hast Du ja bei `n` Dateien `n` zweidimensionale Felder. Und das Ergebnis soll was sein? Eine Liste? Oder auch ein zweidimensionales Feld? Nach welcher Formel berechnet sich ein einzelnes Element?

Welche Aussagen kannst Du über die Zahlen und die Felder treffen? Ganze Zahlen die auch aufaddiert nie grösser als 2^x werden? Ist die Anzahl der Zeilen einer Datei vorher bekannt? Dann könnte man vielleicht `numpy` einsetzen, oder zumindest das `array`-Modul aus der Standardbibliothek um Speicher zu sparen.

[Tyrax]

@BlackJack: Ich hatte versucht, mein Problem so kurz wie möglich zu schildern, aber Du hast wohl recht: ich habe nicht alle relevanten Infos zum Besten gegeben. Hier ein neuer Versuch:

Input:
- etwa 100 plaintext-Dateien, die meine Daten enthalten. Es handelt sich um Sequenzen von integers, etwa

Code: Alles auswählen

342;97;75; ...;4

und

Code: Alles auswählen

764;68:3; ...; 1

Die einzelnen Einträge sind nicht größer als 2^13, die Längen der Sequenzen ist unterschiedlich, 2^25 ist als maximale Länge durchaus möglich. Für das obige Bsp will ich eine Sequenz

Code: Alles auswählen

1006;165;78; ...; 4

ermitteln(hoffentlich nicht verrechnet^^).
berechnen, sofern die erste Liste länger ist, als die zweite. Dieses Ergebnis soll wieder in eine Ausgabedatei.

Ich will also aus all meinen Listen jeweils die i-ten Elemente aufaddieren und das Ergebnis als i-tes Element in meine Ergebnisliste der Länge max(len(Liste1, len(Liste2),...)) aufnehmen.

Danke schonmal fürs feedback, Tyrax

edit: Ich hatte mich bei der Größenangabe der Einträge vertippt.

[BlackJack]

@Tyrax: Eine erste "naive" Implementierung musste ich abbrechen, weil klar wurde, dass mein Speicher dafür nicht ausreicht. Mit `numpy` ging es dann aber:

Code: Alles auswählen

def algo_b(n=100, path=PATH, dtype=np.uint32):
    result = np.zeros(0, dtype)
    for i in xrange(n):
        print >>sys.stderr, 'Load...', i
        data = np.fromfile(
            os.path.join(path, '%05d.txt' % i),
            dtype=dtype,
            sep=DELIMITER
        )
        
        if len(result) < len(data):
            data, result = result, data
        
        print >>sys.stderr, 'Add...', i
        result[:len(data)] += data

    return result

Ich habe vorher in dem `PATH`-Verzeichnis Textdateien mit einer Zeile und 2^25 ganzen Zufallszahlen zwischen 0 und 2^13 erzeugt, die durch Semikolons getrennt sind. Da haben alle Dateien sozusagen die "worst case"-Länge.

[Tyrax]

Hallo BlackJack,

ich habe Deinen Code noch nicht im Detail verstanden, will mich aber gerne durcharbeiten. numpy stand sowieso schon länger auf meiner will-ich-können-Liste. Besten Dank für die Hilfe,

Tyrax

[Tyrax]

Hallo BlackJack,

ich hab' mir Deinen Code jetzt angesehen und erlaube mir mal, die einzelnen Dinge so zu kommentieren, wie ich sie glaube verstanden zu haben:

Code: Alles auswählen

import numpy as np                             # Wir importieren numpy und kuerzen es mit np ab.

def algo_b(n=100, path=PATH, dtype=np.uint32): # Das ist die Funktionsdefinition.
    result = np.zeros(0, dtype)                # Wir legen ein Null-array für die Ausgabe an.
    for i in xrange(n):                        # n ist die Anzahl der Daten-Dateien.
        print >>sys.stderr, 'Load...', i       # Schreibe 'Load... i' in die stderr.
        data = np.fromfile(                    # fromfile() liest aus der angegebenen Datei aus.
            os.path.join(path, '%05d.txt' % i),# Wenn zB sep=',' angegben ist, liest fromfile() die Datei
            dtype=dtype,                       # im Textmodus und schreibt die von ',' getrennten Einträge
            sep=DELIMITER                      # im ang. Datentyp in das array 'data'
        )
       
        if len(result) < len(data):            # Hier vertauschen wir die Namen, falls result kürzer als 
            data, result = result, data        # data ist.
       
        print >>sys.stderr, 'Add...', i        # Schreibe in sterr, dass die Daten der i-te Datei
                                               # hinzuaddiert werden.
        result[:len(data)] += data             # Da wir oben die Namen ggf. vertauscht haben, koennen wir
                                               # die arrays jetzt bequem elementweise addieren.

    return result                              # result ist die gewünschte elementweise Summe der einzelnen
                                               # arrays.

Leider bleibe ich bis jetzt bei zwei Dingen hängen:

• Ich weiß nicht, wie numpy.fromfile() im Detail funktioniert und konnte das bis jetzt auch nicht in Erfahrung bringen. Da meine Daten-Dateien neben Kommentarzeilen jeweils eine ganze Reihe von Verteilungen zu verschiedenen Anfangsdaten enthalten, muss ich zumindest zeilenweise auslesen und auf die ersten Einträge der Zeilen zugreifen können.
• Ähnliches gilt für os.path.join(...). Was genau passiert da?

Ich versuche weiter, diese beiden Dinge hinzubekommen. Falls sich zwischenzeitlich jemand findet, der mit einem Tipp aufwarten kann (Wo kann man das gut nachlesen? Habe ich etwas falsch verstanden?) wär das natürlich prima.

Beste Grüße, Tyrax

[BlackJack]

@Tyrax: Ähm, ich dachte Deine Dateien enthalten jeweils eine Zeile nur mit den Daten. Wenn da anderes als Daten und Trennzeichen drin sind, dann geht das laden so natürlich nicht. Bei mehreren Zeilen mit Daten weiss ich dann ja auch schon wieder nicht mehr wie die genau aussehen von der "Form" her, Du hast ja bisher nur den Wertebereich und die Länge einer Zeile beschrieben, aber nicht wie viele Datenzeilen es gibt. Womit sich dann auch wieder die Frage stellt, wie genau das Ergebnis aussehen soll und wie es zustande kommen soll.

`os.path.join()` setzt Pfade zusammen. Das hätte man zwar aus dem Namen schon erraten können, aber es sollte auch dokumentiert sein.

[Tyrax]

@BlackJack: Hmm, sorry. Ich hatte nur den in meinen Augen relevanten Teil einer exemplarische Zeile beschrieben. Ich hatte vorher mit readlines() gearbeitet. Da konnte ich dann bequem Kommentarzeilen aussortieren und in den einzelnen Datenzeilen die Daten von dem entsprechenden Label trennen (dazwischen steht ein '\t').

os.path.join(...) produziert also die Dateinamen der Dateien, aus denen dann ausgelesen wird? Für diesem Fall hatte ich bisher mit glob.glob() eine Liste der .txt-Dateinamen angelegt und über diese iteriert. Das klappte ganz gut, da ich meine Daten sowieso in einem eigenen Ordner versammelt habe.

Naja, Deine Tipps haben mich jedenfalls schon deutlich weiter gebracht, beste Grüße, Tyrax

[sma]

Solange ich wenigstens eine Zeile in den Hauptspeicher bekomme, sollte doch dies hier reichen, oder?

Code: Alles auswählen

result = []

for name in names:
    with open(name) as f:
        for line in f:
            nums = map(int, line.split(";"))
            l = len(nums)
            while len(result) < l:
                result.append(0)
            for i in range(l):
                result[i] += nums[i]

print result

Und wenn die einzelnen Zeilen zu lang sind, dann liest man eben nur bis zum nächsten ; und verarbeitet jede Zahl einzeln.

Stefan

[BlackJack]

@sma: Das ist der naive Ansatz von dem ich schrieb, dass das meinen Arbeitsspeicher wirklich hoffnungslos gesprengt hat. Das Programm endete hart weil der Swap auch voll war.

[sma]

Das verstehe ich nicht, warum das den Hauptspeicher sprengen sollte? Selbst wenn ich die Aussage " die Längen der Sequenzen ist unterschiedlich, 2^25 ist als maximale Länge durchaus möglich" als so eine Zeile kann schon mal 33554432 Zeichen lang sein interpretiere, dann sollte das doch kein größeres Problem sein, diese 32 MB einzulesen. Auch wenn ich annehme, es sind nicht Zeichen sondern Zahlen gemeint, ist das bei Zahlen, die nicht größer als 8192 (2 ^ 13) sind, nur 4 Zeichen, plus Semikolon also 5 * 32 MB = 160 MB. Auch das muss noch in jeden Hauptspeicher passen. Will ich dann 32 Mio Elemente in einem Array ablegen, sollte das auch in unter 1 GB passen.

Ein `len(range(1 << 25))` lässt meinen Python-Prozess kurz auf um 1 GB anschwellen und dann reagiert er wieder. Kein Absturz. Kein Swapen.

Stefan

[BlackJack]

@sma: Die Zeile muss in den Speicher passen. Dann die gesplittete Zeile. Dann die Liste der gesplitteten Zeile umgewandelt in Zahlen. Dann das Ergebnis. Bei den Vorgängen ist immer die Frage wie die Listen aufgebaut werden, also wie oft eine neue Liste angelegt wird, die grösser als nötig ist um das asymptotische O(1) für das `append()` zu ermöglichen. Frag mich nicht warum im Detail, aber es geht halt nicht. ``len(range(2**25))`` ist bei mir auch im Bruchteil einer Sekunde fertig -- aber das ist ja nicht das Problem was gelöst werden soll.

``len([1000] * 2**25)`` geht auch noch, aber wandel die Liste jetzt mal mit `map()` in eine Liste mit Zeichenketten um. Mein Rechner packt das jedenfalls nicht. Und die Gegenrichtung -- Zeichenketten in `int` -- auch nicht.

[Tyrax]

Hallo BlackJack, hallo sma,

danke für die weiteren Beiträge, die kommen meinem Verständnis zugute. Bei der Gelegenheit habe ich noch 'ne vermeintlich kurze Frage zur Speicherauslastung:
Wie kann ich die aktuelle Speicherauslastung von Python aus sehen? Ich würde zur Kontrolle gerne nach dem Einlesen von langen Datenzeilen die aktuelle Speicherauslastung über die Konsole ausgeben.

Grüße, Tyrax

[BlackJack]

Die Speicherbelegung aus Betriebssystem-Sicht kann man mit dem psutil-Modul ermitteln. Sowohl gesamt, als auch für einzelne Prozesse (und damit auch für den, in dem man das macht).

[sma]

Nach wie vor bin ich der Meinung, ich bekomme (problemlos) ein Array mit 32 Mio Einträge in den Hauptspeicher. Ich habe allerdings nicht probiert, was ein `map(int, arr)` anrichtet. Ich hätte vermutet, CPython ist schau genug, ein zweites Array mit 32 Mio Datensätzen anzulegen und nicht zu versuchen, dieses inkrementell zu vergrößern, was bei dem üblichen Algorithmus, die Größe immer zu verdoppelt, zu 64 Mio Einträgen a 8 Bytes führen könnte.

Ich kann's gerade nicht ausprobieren, da mein System schon jetzt im Swap ist und ich nicht 2 GB oder so über habe. Aber ich sagte ja, es wäre nicht weiter schwer, die Zeile nicht komplett sondern nur bis jeweils zum ";" bzw. Zeilende zu lesen:

Code: Alles auswählen

    with open(name) as f:
        c = f.read(1)
        b = ""
        i = 0
        while True:
            if c == '' or c == '\n' or c == ';':
                nums[i] += int(b)
                b = ""
                if c == '\n':
                    i = 0
                else:
                    i += 1
            else:
                b += c
            if not c:
                break
            c = f.read(1)

Stefan

[BlackJack]

@sma: Theoretisch müsste der Speicher ausreichen und theoretisch könnte man für jedes Byte einer >100 MiB grossen Datei auch einen `read()`-Aufruf absetzen. Praktisch ist beides nicht ernsthaft brauchbar.