Problem mit Laufzeit wegen sehr großen Dateien

[x1334]

Hallo.

Ich habe mir ein Programm geschrieben, das folgendes macht:

Textdatei1 ist so formatiert, Zeile für Zeile: sagen Satz
Textdatei2 sieht so aus, Zeile für Zeile: Satz Ausdruck

Nun will ich eine 3. Textdatei erstellen, die danach so aussieht: sagen Ausdruck

Ich ersetze also "Satz", falls das Wort in der 2. Textdatei gefunden wird, mit Ausdruck und speichere diese Zeile in eine neue Textdatei.

Bisher habe ich dies über Listen gelöst, doch das scheint mir nicht optimal.
Ich gehe Zeile für Zeile in Textdatei 1 durch und lasse das Quellwort durch die komplette Zielliste laufen.

Da meine Dateien _SEHR_ groß sind, dauert dies aber viel zu lang (1M Zeilen etwa 50 Stunden). Gibt es eine bessere Methode? Das Problem ist ja an sich nicht sehr schwierig, aber irgendwie komm ich nicht ganz damit zurecht.

Gruß,
x1334

[/me]

Bisher habe ich dies über Listen gelöst, doch das scheint mir nicht optimal.

Wenn die Daten noch klein genug sind, dass sie in den Hauptspeicher passen, dann solltest du Datei 2 in ein Dictionary packen mit Satz als Schlüssel und Ausdruck als Wert. Eine Liste ist da in der Tat der falsche Ansatz.

Anschließend kannst du Datei 1 durchlaufen und im Dictionary für jeden Eintrag nachsehen ob ein Element mit einem passenden Schlüssel vorhanden ist.

[snafu]

Vielleicht noch der Grund, wieso ein Dictionary hier die bessere Datenstruktur ist: Das hängt mit der Zugriffszeit zusammen. Eine Liste muss zum Finden eines Elementes zwangsläufig solange durchlaufen werden bis ein Vergleich passt. Insbesondere bei nichtvorhandenen Elementen kann dies erst sicher gesagt werden (also, dass sie nicht in der Liste existieren), wenn die *komplette* Liste durchlaufen wurde. Wenn du das wieder und wieder machst und die Liste dazu noch entsprechend groß ist, dann kommt es zu diesen miesen Laufzeiten. Ein Dictionary wiederum (auch: Hashmap genannt), versieht das abzulegende Element mit einer Art "Stempel" (dem Hashwert). Aus diesem Stempel kann *direkt* die Position des abgelegten Objekts errechnet werden. Die Zugriffszeit auf das erste abgelegte Element ist damit (annähernd) genau so schnell wie auf das 10 Millionste Element, weil alle davorliegenden Objekte nicht beachtet werden müssen. Das verschafft einem in entsprechenden Anwendungsfällen (z.B. in deinem) erhebliche Geschwindigkeitsvorteile.

Vielleicht sollte man mal eine Liste implementieren, die für "Contain-Abfragen" intern auf eine Hashmap zugreift. Oder vielleicht gibt es sowas schon. In Pythons Builtin-Listen wird jedenfalls nicht so vorgegangen.

[deets]

@snafu

Das ist dann keine Liste mehr, und loest vor allem auch dein Problem nicht: was passiert denn, wenn ich denselben hash-wert mehrfach in der Liste habe? Verwaltest du dann hinter jedem hash-wert eine Liste mit Positionen, an denen sie vorkommt? Und was sagt einem das denn dann semantisch?

So eine Datenstruktur braucht man nicht wirklich. Mengen oder Maps loesen das aktuelle Problem.

Und noch ein Nachtrag zu deinen Ausfuehrungen: Hashmaps stellen ueblicherweise eine geeignete Datenstruktur dar, weil die Chance fuer Kollisionen gering sind. Aber natuerlich degeneriert das Laufzeitverhalten im Falle von hash-Kollisionen.

[EyDu]

Vielleicht sollte man mal eine Liste implementieren, die für Include-Abfragen intern auf eine Hashmap zugreift. Oder vielleicht gibt es sowas schon. In Pythons Builtin-Listen wird jedenfalls nicht so vorgegangen.

Um das effizient machen zu können, müssten alle Elemente in der Liste unveränderlich sein, sonst hat man nicht viel gewonnen. In den meisten Fällen reicht wohl ein OrderedDict.

[snafu]

@EyDu: Naja, für Strings gilt das ja durchaus. Für Zahlen ebenso. Ich spreche nicht unbedingt von der Modifikation der bestehenen Implementation von `list`, sondern durchaus auch von einem abgeleiteten Typen. Dieser könnte nur unveränderliche Objekte erlauben. Dieses Forum ist aber sicherlich der falsche Ort für solche Diskussionen. Das ist mir bewusst. Wäre eigentlich mal ne tolle Projekt-Idee (falls sie noch keiner hatte).

[snafu]

@deets: Dass es zu theoretisch sehr vielen Hash-Kollisionen kommen kann, ist kein wirklich neues Problem. Ich wollte auch nicht anregen, dass der OP irgendwas in dieser Art in Python implementieren soll. Der Gedanke kam mir einfach nur so in den Sinn. Daher auch der abgetrennte Absatz - offenbar habe ich das nicht ausreichend verdeutlicht. Die Programmierung eines solchen optimierten Listentyps sollte sinnvollerweise direkt in C unter Nutzung der Python-API erfolgen. Zum Verwalten dient natürlich ein `PyDictObject`. Wozu sollte man das Rad neu erfinden wollen?

[snafu]

Ich hab mir mal den Spass gemacht, die Idee in Python umzusetzen: https://gist.github.com/3359890

Ich bin mir übrigens über den Mehrverbrauch an Speicher wegen den ganzen Item-Referenzen im Klaren. Da müsste man mal in der Praxis gucken, bis zu welchem Punkt das akzeptabel ist. Ich werde jetzt mal ein paar Messungen/Vergleiche machen, hinsichtlich der Zugriffszeit...

//edit: Okay, ist erwartungsgemäß deutlich schneller, wenn man z.B. mal ein `timeit` auf alle "Wörter" (`split()`) des Quellextes von `python-forum.de` macht.

[noisefloor]

Hallo,

ich würde bei sowas wohl (wahrscheinlich) zu einer DB greifen. Entweder SQL oder KV-Store.

Gruß, noisefloor

[BlackJack]

KISS… Wenn ein Wörterbuch im Speicher nicht geht weil Wörterbuch zu gross oder Speicher zu klein, könnte man auch erst einmal das Wörterbuch durch `anydbm` ersetzen.