Große Mengen an Daten prüfen

Guten Abend zusammen,

ich sitze vor einem kleinen Problem,

Ich habe Daten im Textformat (~800MB) die ich gerne auf doppelte Zeilen überprüfen möchte, und diese gegebenenfalls löschen lasse.

Was habe ich schon versucht?
Ich lese die Datei mit einem StreamReader ein, und speichere jede Zeile in einer ArrayListe und prüfe dann mit ArrayList.Contains() ob die eingelesene Zeile schon in der Liste vorhanden ist.

Problem:

Die Ganze Geschichte wird, je größer die ArrayList wird immer langsamer, und irgendwann so langsam, dass das Programm über eine Woche laufen müsste.

(Vom RAM her sollte es kein Problem sein, da ich 3,5 Gigabyte zur Verfügung habe)

Hat jemand ne Idee oder Möglichkeit, wie ich das Ganze schneller lösen könnte?

Danke und Gruß

Guten Abend,

erstell dir von jeder Zeile einen Hashcode,diesen Speicherst du dann in einem dictionary mit <index, hashcode> lässt dir das dictionary nach den hashcodes sortieren und gehst anschliessend das selbige durch, wenn 2 mal hintereinander der leiche hash kommt weißtdu anahnd des indexes welche zeile gelöscht werden muss.

hoffe das war einigermasen verständlich, war ein langer tag.

mfg Markus

PS: bei 800MB wird es aber trotzdem eine Zeit brauchen, du könntest dich mal mit multithreading auseinander setzen. Sortieren oder auch suchen kann man beispielsweiße gut auf threads aufteilen.

oder anders.

erstell dir den hashcode und schreibe ihn in ein dictionary mit dictionary<hashcode,List<int>>.

beim einfügen prüfst du dann, ob der key vorhanden ist und wenn ja, fügst du die zeilennummer, bei der du gerade bist, dem valuewert hinzu. so kannst du im nachhinein bestimmen welche der zeilen (höhere nummern oder niedrigere) gelöscht werden sollen. das ist perfomanter wie die bereits genannte alternative.

Hallo Barbara,

den Hashcode brauchst du nicht explizit zu erstellen. Nimm statt der ArrayList ein Dictionary<string,bool>, schreibe die Zeile als Key in das Dictionary (das value ist egal, ich nehme immer true) und prüfe mit ContainsKey. Das ist um Größenordnungen schneller.

Siehe auch [Artikel] Grundlegendes zu Hashtable/Dictionary.

BTW: ArrayList gehört in die Mottenkiste und sollte wie alle untypsierten Collections aus System.Collections nicht mehr benutzt weden. Verwende stattdessen im List<T> und alle anderen typsierten Collections aus System.Collections.Generic. Im Konkreten Fall natürlich nicht List<T> sondern dass genannte Dictionary<>.

herbivore

Was habe ich schon versucht?
Ich lese die Datei mit einem StreamReader ein, und speichere jede Zeile in einer ArrayListe

Hier könnte es schneller sein, die Datei in größeren Blöcken (Stichwort: FileStream.Read) einzulesen, statt immer zeilenweise vorzugehen .
Pro gelesenem Block kannst du dann mehrere Zeilen so wie von den anderen beschrieben extrahieren und gehashed speichern.

In dem Zusammenhang wäre es auch möglich die Datei asynchron einzulesen. Dies führt laut Literatur zu einer besseren Auslastung der Festplatte, aber ob dies für deinen Fall wirklich Sinn macht, ist fraglich.

(Vom RAM her sollte es kein Problem sein, da ich 3,5 Gigabyte zur Verfügung habe)

Das ist leider nicht pauschal auslegbar. In einem 32 Bit-OS stehen dir nur 2GB für dein Anwendungsprogramm zur Verfügung. Der virtuelle Adressraum beträgt zwar 4GB, aber 2GB davon sind quasi für das Betriebssystem reserviert. Allerdings gibt es noch einen Schalter um 3GB zu nutzen (Stichwörter: PAE, /3GB)

Erst mit einem 64 Bit-OS ist diese Beschränkung sehr weit nach oben verlegt worden.

Hier könnte es schneller sein, die Datei in größeren Blöcken (Stichwort: FileStream.Read) einzulesen, statt immer zeilenweise vorzugehen .
Pro gelesenem Block kannst du dann mehrere Zeilen so wie von den anderen beschrieben extrahieren und gehashed speichern.

das halte ich nciht für sinnvoll, dam na dann splitoperationen und einige rumkopierereien auf sich nimmt.

da die datei 800mb groß ist, sollte sie im allgemeinen in dem großzügig bemessenen ram auch auf einem 32bit os problemlos einen platz finden (in form eines arrays oder dictionarys z.b.)

Hallo wdb.lizardking,

dein Vorschlag wird leider nicht viel nützen und möglicherweise sogar schaden. Es ist völlig ok, die Datei Zeilenweise einzulesen. Der Zeitfresser ist die Prüfung auf Duplikate und dafür wurden ja schon Lösungen genannt.

herbivore

Um aussagekräftige Zeiten zu erhalten, habe ich ein paar Testmethoden geschrieben um eine große Textdatei einzulesen.

Was mir dabei aufgefallen ist und mich leicht rätseln lässt, ist die schnelle Verarbeitung:

Ich habe eine 850MB große Textdatei, welche ich blockweise einlese und dann auf Zeilen aufsplitte. Als Alibifunktion merke ich mir ein bestimmtes Zeichen jeder Zeile, einfach um zu gewährleisten, dass jede Zeile einmal benutzt wurde.

Für diese Datei benötigt ein Durchlauf nun durchschnittlich 2,7 Sekunden. Ich lasse den Test 10 mal durchlaufen und schmeiße die Extremwerte weg um Initialisierungsspitzen zu vermeiden. Auch der Taskmanager mit Gelesene E/A-Bytes an, dass die Datei vollends gelesen wurde.

Einfache Rechnung 850 MB / 2,7 Sekunden = 314 MB/s.
Es handelt sich dabei um einen neuen Quad-Rechner mit SATA-Anschluß, aber sollte dies nicht über der sequentiellen Maximalleistung einer modernen (Nicht-SSD) Festplatte liegen?

Nicht dass mich das schnelle Lesen nicht freut, ich würde nur gerne verstehen, wie er zustande kommt 🙂

Sollte es bei einer Assembly zu Speicherproblemen führen, weil große Text-Dateien verarbeitet werden müssen und auf die Klasse System.String nicht verzichtet werden kann, lässt sich das String Interning (String.IsInterned-Methode) auch explizit abschalten. Man setzt dazu in der betroffenen Assembly das CompilationRelaxationsAttribute.

Hallo wdb.lizardking,

das erste Lesen der Datei müsste in der Tat deutlich länger dauern. Wenn sie einmal gelesen ist und genug Hauptspeicher zur Verfügung steht, geht es rasend schnell, weil die Datei dann schon im Dateisystemcache steht.

herbivore