in riesigen ASCII-Dateien effizient bestimmte Zeilen finden

Onkel Schuppig

Erfahrenes Mitglied
Hallo allerseits,
ich habe mit riesigen ASCII-Dateien zu tun (z.B. 14 GB groß), die von vorn bis hinten mit Datenblöcken gefüllt sind nach diesem Schema:
Code:
    -1
    ... datensatz1  ...
    -1
    -1
    ... datensatz2 ..
    -1
Also immer -1, Datensatz, -1. "Datensatz" kann riesig sein, ist von Satz zu Satz in der Regel verschieden groß.
Es wäre nett gewesen, wenn die Programmierer dieses Dateiformats einen Offset zum nächsten Datensatz untergebracht hätten, dann könnte man ruckzuck von einem zum nächsten Datensatz hangeln. Haben sie aber nicht.
Um die Anfänge jedes Satzes zu finden, muss ich also jede Zeile einlesen und prüfen ob sie " -1" ist. Das dauert natürlich.
Nun die Frage: Gibt es in der Informatik einen schnelleren Algorithmus, um alle -1 zu finden?

Grüße OS
 

MCoder

Erfahrenes Mitglied
Hallo,

um das Durchhangeln wirst du, denke ich, nicht herumkommen.
Eine Idee wäre, die Datei innerhalb von Threads mehrfach zu öffnen und dann jeweils nur bestimmte Abschnitte der Datei parallel zu durchsuchen.

Gruß
MCoder
 

Onkel Schuppig

Erfahrenes Mitglied
Hi, danke für die Antwort.
2 x 10 Mio Zeilen durchsuchen soll schneller gehen als 1 x 20 Mio.?
Ich denke eher umgekehrt. Es sei denn, die Suchvorgänge werden auf 2 Prozessoren verteilt. Aber dann muss der Lesekopf extrem oft bewegt werden.
 

Nico Graichen

Erfahrenes Mitglied
Da sind schon Datenmengen bei denen es schwierig wird, etwas zu finden, dass "schnell" geht.
Ich finde den Ansatz mit mehreren Threads gar nicht so schlecht. Das größere Problem, dass dabei jedoch auftritt ist, dass du nicht weißt, wo der 2 Thread starten soll, da dafür der Einstiegspunkt fehlt.
Ich glaube fast, dass du um das zeichen- oder zeilenweiße Einlesen auf dem Stream nicht drum rum kommst.
 

MCoder

Erfahrenes Mitglied
Hi, danke für die Antwort.
2 x 10 Mio Zeilen durchsuchen soll schneller gehen als 1 x 20 Mio.?
Ich denke eher umgekehrt. Es sei denn, die Suchvorgänge werden auf 2 Prozessoren verteilt. Aber dann muss der Lesekopf extrem oft bewegt werden.
Ich glaube schon, dass sich da geschwindigkeitsmäßig was herausholen ließe, habe aber zugegebenermaßen mit so einem Thema noch nichts zu tun gehabt. Was den Lesekopf betrifft: Das Problem dürfte vermutlich durch das Caching beim Festplattenzugriff entschärft werden.

Das größere Problem, dass dabei jedoch auftritt ist, dass du nicht weißt, wo der 2 Thread starten soll, da dafür der Einstiegspunkt fehlt.
Ich glaube fast, dass du um das zeichen- oder zeilenweiße Einlesen auf dem Stream nicht drum rum kommst.
Das sehe ich auch so: Zeichen- bzw. zeilenweises Einlesen muss man auf jeden Fall. Der genaue Startpunkt für verschiedene Threads dürfte meiner Meinung nach nicht so problematisch sein, da der Beginn eines Datensatzes eindeutig gekennzeichnet ist.

Gruß
MCoder
 

RenderWilli

Mitglied
Wie wäre es, wenn du daraus einen neuen Datensatz erstellst, der die "-1" nicht enthält?
Oder du läßt die Datei einmal durchlaufen, speicherst die Positionen der Datensätze in eine extra Datei mit der du dann eine Art Index hast, um so zukünftig schneller die Datensätze durchsuchen zu können.
 

Thomas Darimont

Erfahrenes Mitglied
Hallo,

du könntest dir einfach zusätzlich eine entsprechende Index Datei aufbauen und dann diesen für zukünftige Suchen verwenden.

Gruß Tom
 

Onkel Schuppig

Erfahrenes Mitglied
Hallo alle,
danke für die vielen Beiträge. Die Datei wird nur einmal durchlaufen, deshalb sind Indices erst bei weiderholtem Durchlauf effektiv.
Wenn mal Zeit ist, werde ich was mit 2 Threads ausprobieren.
Schaumer mal. :)