dictionary > hauptspeicher
Hallo *,
ich habe eine sehr lange Liste von Strings, die ich sequentiell durchgehen muß. In dieser Liste gibt es sehr viele Duplikate, die ich gern herausfiltern würde. Dummerweise ist jetzt die Liste so lang, daß das Dictionary zum Rausfiltern der Duplikate nicht mehr in den Hauptspeicher passt.
Tjo, also irgendwie brauche ich da wohl eine Datenstruktur, die dann eben auf die Platte schreibt, sobald kein Hauptspeicher mehr da ist. Schön wäre natürlich, wenn nur selten vorkommende Strings auf Platte ausgelagert würden. Gibt es soetwas schon? Oder sollte man da Berkely DB oder etwas ähnliches verwenden?
Die Kiste einfach swappen zu lassen, damit der Kernel das Aus- lagern übernimmt, hat nicht gut genug funktioniert :).
Gruss, Jochen
_______________________________________________ python-de maillist - python-de@python.net http://python.net/mailman/listinfo/python-de
ich habe eine sehr lange Liste von Strings, die ich sequentiell durchgehen muß. In dieser Liste gibt es sehr viele Duplikate, die ich gern herausfiltern würde. Dummerweise ist jetzt die Liste so lang, daß das Dictionary zum Rausfiltern der Duplikate nicht mehr in den Hauptspeicher passt.
Tjo, also irgendwie brauche ich da wohl eine Datenstruktur, die dann eben auf die Platte schreibt, sobald kein Hauptspeicher mehr da ist. Schön wäre natürlich, wenn nur selten vorkommende Strings auf Platte ausgelagert würden. Gibt es soetwas schon? Oder sollte man da Berkely DB oder etwas ähnliches verwenden?
Ja, sowas gibt: heisst datenbank :) Ob berkleydb dabei gut genug ist - KA. Abgesehen davon, das uU auch andere Herangehensweisen funktionieren:
Wenn deine strings laenger sind als ein MD5-hash, dann koenntest du im ersten schritt einen index aus
(hash, position_im_file)
erstellen. Der sollte noch in den Speicher passen... Die sortierst du dann nach hash - und alle gleichen hashes pruefst du dann ueber die Datei auf echte gleichheit. Wahrscheinlich ist das noch nicht mal notwendig. Als Ergebnis hast du dann eine Liste von eindeutigen Strings. Die Sortierst du nach file-postition - und dann gehst du die durch und schreibst halt die Ergebnisstrings weg.
Die Verwendung von mmap ist dabei wohl auch angezeigt - habe ich aber nicht aus dem Kopp parat.
MfG Diez
_______________________________________________ python-de maillist - python-de@python.net http://python.net/mailman/listinfo/python-de
Diez B. Roggisch wrote:
ich habe eine sehr lange Liste von Strings, die ich sequentiell durchgehen muß. In dieser Liste gibt es sehr viele Duplikate, die ich gern herausfiltern würde. Dummerweise ist jetzt die Liste so lang, daß das Dictionary zum Rausfiltern der Duplikate nicht mehr in den Hauptspeicher passt.
Tjo, also irgendwie brauche ich da wohl eine Datenstruktur, die dann eben auf die Platte schreibt, sobald kein Hauptspeicher mehr da ist. Schön wäre natürlich, wenn nur selten vorkommende Strings auf Platte ausgelagert würden. Gibt es soetwas schon? Oder sollte man da Berkely DB oder etwas ähnliches verwenden?
Ja, sowas gibt: heisst datenbank :) Ob berkleydb dabei gut genug ist - KA. [...]
Ich würde dafür SQLite nehmen. Die Dinger in eine Datenbanktabelle schreiben, dann mit einem SELECT DISTINCT zurücklesen:
... cur.execute("select distinct value from stringtable") for row in cur: ...
wobei das anschließende Iterieren über den Cursor die rows "on-demand" abholt, und nicht etwa alle auf einmal. Somit dürfte es da kein Speicherproblem geben.
-- Gerhard
_______________________________________________ python-de maillist - python-de@python.net http://python.net/mailman/listinfo/python-de
Am Donnerstag, 22. September 2005 14:06 schrieb Gerhard Häring:
Diez B. Roggisch wrote:
Tjo, also irgendwie brauche ich da wohl eine Datenstruktur, die dann eben auf die Platte schreibt, sobald kein Hauptspeicher mehr da ist. Schön wäre natürlich, wenn nur selten vorkommende Strings auf Platte ausgelagert würden. Gibt es soetwas schon? Oder sollte man da Berkely DB oder etwas ähnliches verwenden?
Ja, sowas gibt: heisst datenbank :):) Ob berkleydb dabei gut genug ist - KA. [...]
Ich würde dafür SQLite nehmen. Die Dinger in eine Datenbanktabelle schreiben, dann mit einem SELECT DISTINCT zurücklesen:
Ja, so ähnlich werde ich es machen. Einfach Feld als uniq erklären und dann alles inserten. Dann sind die Einträge automatisch distinct.
... cur.execute("select distinct value from stringtable") for row in cur: ...
wobei das anschließende Iterieren über den Cursor die rows "on-demand" abholt, und nicht etwa alle auf einmal. Somit dürfte es da kein Speicherproblem geben.
Ja, ich mache das momentan so:
def getAllRows(): con, cur = getDB("blubber") cur.execute("select * from blub") while True: rows = cur.fetchmany(1000) if not rows: break else: for row in rows: yield row
Wobei man aufpassen muß, daß man dafür einen anderen Cursor verwendet, als für die anderen Datenbankzugriffe, die man macht, während über den Generator iteriert wird. Wenn man da den gleichen nimmt, kommt da natürlich plötzlich nichts mehr zurück, weil eine andere Query ja schon fertig ist :>.
Gruss, Jochen
_______________________________________________ python-de maillist - python-de@python.net http://python.net/mailman/listinfo/python-de
Am Donnerstag, 22. September 2005 13:23 schrieb Diez B. Roggisch:
Tjo, also irgendwie brauche ich da wohl eine Datenstruktur, die dann eben auf die Platte schreibt, sobald kein Hauptspeicher mehr da ist. Schön wäre natürlich, wenn nur selten vorkommende Strings auf Platte ausgelagert würden. Gibt es soetwas schon? Oder sollte man da Berkely DB oder etwas ähnliches verwenden?
Ja, sowas gibt: heisst datenbank :) Ob berkleydb dabei gut genug ist - KA. Abgesehen davon, das uU auch andere Herangehensweisen funktionieren:
Naja, ich denke es wird eine Hash-DB sein müssen, da die doch prinzipiell schneller sein sollte als eine relationale DB, oder?
Ich bekomme die Daten schon aus einer mysqldb und schreibe sie auch wieder in eine solche, nur - wenn ich vorher feststellen will, ob es einen bestimmten Eintrag schon gibt, brauche auf diesem Feld einen Index. Wenn ich da aber einen Index drauf habe, kann ich dort nicht mehr schnell inserten :/.
Man könnte auch das Feld für den String uniq erklären und dann inserten, was das Zeug hält, und auf die Fehler pfeifen, aber dummerweise muß ich noch eine zweite, aufwändige Geschichte mit den Strings machen, bevor ich sie in die DB pumpen kann. Wenn ich das auch für alle Duplikate machen muß, würde das, ähm, ewig dauern.
Ha, ich glaub ich habs. Ich inserte erst, dann wird der Index gerechnet und dann update ich nur noch das Feld für die aufwändigere Geschichte... Danke :).
Wenn deine strings laenger sind als ein MD5-hash, dann koenntest du im ersten schritt einen index aus
(hash, position_im_file)
erstellen. Der sollte noch in den Speicher passen... Die sortierst du dann
Gute Idee, md5 dürfte nahezu ideal komprimieren... aber auch das wird leider nicht mehr in den Speicher passen, nein.
Gruss, Jochen
_______________________________________________ python-de maillist - python-de@python.net http://python.net/mailman/listinfo/python-de
Wenn dir die Anordnung der Strings egal ist, kannst du auch einfach eine Menge daraus machen. In 2.4 gibts dafür den set bzw. frozenset Typ, beide built-in. Bei 2.3 musst du dafür das sets Modul importieren.
Wegen des Speicherproblems: Ich würde einfach mal Exception Handling einbauen und zwar gibts eine Klasse 'MemoryError', die hier wahrscheinlich genau richtig wäre. Im Falle es wird ein MemoryError geworfen, kannst du ja die bis dahin analysierten Daten dann irgendwo abspeichern, entweder dann eben mit binärem dump (pickle z.B.) oder durch Abspeichern in einer Datenbank. Wobei es natürlich bei Unmengen an Datenbergen viel sinnvoller ist von Anfang an direkt Datenbanksoftware (MySQL z.B.) zu verwenden.
Am 22.09.05 schrieb Jochen Wersdörfer jochen-python@wersdoerfer.de:
Hallo *,
ich habe eine sehr lange Liste von Strings, die ich sequentiell durchgehen muß. In dieser Liste gibt es sehr viele Duplikate, die ich gern herausfiltern würde. Dummerweise ist jetzt die Liste so lang, daß das Dictionary zum Rausfiltern der Duplikate nicht mehr in den Hauptspeicher passt. [...]
-- Best Regards Christian Junker
_______________________________________________ python-de maillist - python-de@python.net http://python.net/mailman/listinfo/python-de
participants (4)
-
Christian Junker -
Diez B. Roggisch -
Gerhard Häring -
Jochen Wersdörfer