Fortgeschrittenes beschreiben von Dateien - einzelne Zeilen finden und ändern bzw. löschen

Nun, ich gebs ja zu, oft bin ich ja als Grundlagenforscher unterwegs.
Diesmal geht es darum, Dateien möglichst so zu beschreiben, so daß beim Einlesen bestimmte Zeilen besonders schnell wiedergefunden werden können.

Na gut, ein Beispiel
Ich habe 1000 fortlaufende Rechnungsnummern, dazu jeweils 1000 Brief-Texte, die ich in einer Datei speichern will.
Später will ich möglichst effektiv auf jeweils beliebige Rechnungsnummern plus Brief-Texte zugreifen.

Die Datei sieht später also so aus:
1
Text
2
Text
3
Text
... usw.

Die einfachste Variante wäre die, einfach eine Datei zu öffnen, und alles sequenziell hineinzuschreiben, also zum Beispiel so:

# in @datensaetze sind alle Daten gespeichert, also Element 0 = Rechnungsnummer 0, dann der Text, dann wieder Rechnungnummer usw.

open (my $out,">","datei.txt");

foreach (@datensätze){
print $out $_."\n";
}

Das Auslesen würde dann entweder so funktionieren, daß man die gesamte Datei in ein Array einliest und dann der Reihe nach abklappert, was aber bei großen Dateien eine extreme Speicherverschwendung wäre, zudem sind die Ladezeiten auch relativ lang (wer mal ne 100MB-Datei einliest, weiß, was ich meine).

open (in,"<","datei.txt");
@daten=<in>;
close in;

for ($i=0;$i<@daten;$i+=2){
if ($daten[$i] eq $gesucht){
$brieftext=$daten[$i+1];
last;
}
}

print $brieftext;

Wie gesagt, quick und dirty, also so sollte man es nur bei kleinen Dateien machen...

Eloganter wäre da schon:

open (in,"<","datei.txt");
%daten=<in>;
close in;

if (exists $daten{$gesucht}){print "Brieftext: ".$daten{$gesucht};} else {print "Keine Daten vorhanden";}

Hier wird die Datei gleich einem Hash zugeordnet und per exists abgefragt. So spart man sich die abklapperei mit der for-Schleife.
Aber so ist's immer noch nicht so toll, weil ja wieder die ganze Datei eingelesen wird...

Variante zwei wäre, immer nur 2 Zeilen aus der Datei zu holen, und dann zu gucken, ob es die Richtigen sind.

open (in,"<","datei.txt");
my @arr=();

while (<in>){
chomp($_);
push (@arr,$_);
next if $. % 2;
($name,$brieftext)=@arr;
@arr=();
if ($name eq $gesucht){$gefunden = 1;
last;
}

}
if ($gefunden == 1){ print $brieftext;} else {print "Datensatz nicht gefunden";)

Das wäre schon eine brauchbare Lösung, aber wenn der Datensatz der Letzte in der Liste ist, muß ja trotzdem wieder alles eingelesen werden, und das wollten wir ja nicht... wegen Performance und so...
Und überhaupt funktioniert das Ganze sowwieso nur, wenn keine Zeilenumbrüche im Namen oder im Text vorkommen, diese müßte man also ausmaskieren.

Übrigens, so am Rande: Nagelt mich jetzt bloß nicht auf die Beispielscripte fest, die sind nur zur Demonstration gedacht...

Also irgendwie kommt man ständig nicht drum herum, die ganze Datei einzulesen... und das wollen wir ja nicht.

Man braucht also einen anderen Ansatz:
Erinnern Sie sich daran, wie sie früher eine Platte auf den Plattenspieler gelegt haben und zum Beispiel Lied Nummer 5 angespielt haben? Woher wußten Sie, daß Lied Nummer 5 Ihr Lieblinglied war? Klar: vom Cover, da stand nämlich ein Inhaltsverzeichnis drauf.

Gleiches wäre für Dateien ja auch möglich: Eine Art Inhaltsverzeichnis, das uns sagt, wo unser gewünschter Datensatz liegt.
Dazu bräuchte man aber 2 Dateien: Einmal das Inhaltsverzeichnis und einmal das Datenverzeichnis. Und die Krux dabei ist: Um auf die Daten zuzugreifen, muß wieder erst das Inhaltsverzeichnis eingelesen und verarbeitet werden... Zwar ist das Inhaltsverzeichnis wahrscheinlich relativ klein, aber irgendwie drehen wir uns jetzt doch im Kreis... aber die Idee ist schon gut.

Warum nicht das Inhaltsverzeichnis ins Datenverzeichnis einbauen?
So, und nun komme ich nach all dem Geschreibe endlich zum Punkt:
Möglich wäre es, am Dateianfang eine Art Inhaltsverzeichnis anzulegen, nach dem dann die Daten auszulesen sind.
Das ist aber programmtechnisch relativ kompliziert.

Deswegen nun die von mir auserkorene Möglichkeit, vor jeden Datensatz einen Offset zu schreiben, der jeweils die Länge des aktuellen Datensatzes angibt.

Äh, ... wie???
Also:
Ein Datensatz ist ja aufgebaut in der Form
Name
Text
Name
Text
usw.

Ich schreibe jetzt also die Daten in der Form
Länge_des_Namens -Name-Länge_des_ Textes_Text _Länge_des_ nächsten_Namens-Name- Länge_des_nächsten_Textes _Text
usw. usf.

Warum das?
Also, fangen wir mal an, die Datei einzulesen, nicht in Perl, sondern in Worten:
Lese die Länge das Namens, danach den Namen. Ist der Name der Gesuchte? Ja, dann lese die Länge des Textes, danach den Text. Aufhören weiter einzulesen, da das Gesuchte gefunden wurde.
Wenn der Name nicht der gesuchte Name, dann ÜBERSPRINGE den Text, und mache beim nächsten Namen weiter, bis der Name der Gesuchte ist.

Hört sich einfach an, ist es auch!

#################
# Daten schreiben
#################
@inhalt=('1','Das ist ein Text, der idealerweise sehr lang wäre','2','Das wäre auch besser ein sehr langer Text','3','Und das wäre auch besser ein langer Text');

open (my $out,'>','test.txt') || die "Da gabs wohl nen Fehler: $!";
binmode $out;
foreach (@inhalt){
print $out pack("N",length($_)).$_;
}

close $out;

################
# Daten einlesen
################

$gesucht = '3';

open (my $in,'<','test.txt') || die "Da gabs wohl nen Fehler: $!";
binmode ($in);

{
read($in,my $laenge,4);
last if (!$laenge); # Dateiende erreicht
$laenge=unpack ("N",$laenge);
read ($in,$name,$laenge);

if ($name eq $gesucht){
read($in, $laenge,4);

$laenge=unpack ("N",$laenge);
read ($in,$text,$laenge);
$ergebnis=$text;
$gefunden = 1;
last;
}
else
{
read($in,$laenge,4);
$laenge=unpack ("N",$laenge);
# "Vorspulen"
seek ($in,$laenge,1);
}
redo;
}
close $in;

if ($gefunden == 1){ print "Text: ".$ergebnis;} else { print "Nicht gefunden";}

So, das Script schreibt 3 Datensätze und sucht danach nach Datensatz 3 (worst case).

Und was hier so ein bißchen abgedreht aussieht, bringt Geschwindigkeitsvorteile um den Faktor 10 und mehr, je länger die Datei wird! Zudem wird der Speicher nicht vollgeschrieben, da der Inhalt nur dann eingelesen wird, wenn es auch der Gesuchte ist (da kommt man wohl nicht dran vorbei...)!

Und wie geht das nun???
Datei schreiben:
Wie man sieht, wird die Datei schonmal als binäre Datei geöffnet. Danach schreibt das Script die einzelnen Elemente des Arrays in die Datei, und zwar erst die Länge des Elements, gepackt mit "N", was einem Integerwert im 4-Byte-Format entspricht, und dann das Element selbst. So "weiss" das Script später, daß erst 4 Byte eingelesen werden müssen, aus denen sich dann die Länge des Elements ergibt.

Datei einlesen:
Das Script beginnt ab Position 0 der Datei, also vor dem ersten Zeichen. 4 Bytes werden per read eingelesen, ge-unpack-ed, was der länge des Namens entspricht, und schließlich der Name selbst eingelesen.
Das zweite read ($in,$name,$laenge) ist dafür zuständig. Es liest aus dem Dateihandle $in in die Variable $name $laenge Bytes ein.

Ist der Name der Gesuchte, werden wieder 4 Bytes eingelesen, was der Länge des Inhaltes entspricht, danach der Inhalt selbst. Der Wert wird gespeichert, ein Flag gesetzt ($gefunden = 1) und das Einlesen der Datei beendet.

Ist der Name NICHT der Gesuchte, wird die Länge des Inhaltes eingelesen und über den Inhalt hinweggesprungen. Also wirklich vorgespult, ohne auch nur ein Byte einzulesen!
Dies passiert per seek ($in,$laenge,1), was eben bedeutet, gehe von der aktuellen Leseposition $laenge Bytes nach vorne und mache da weiter.

Wie ich schon angedeutet habe, ist dies besonders bei großen Dateien wesentlich schneller als das Einlesen aller Daten, bis der richtige Datensatz gefunden wurde. Unter Umständen spart man sich so das megabyteweise Einlesen von sinnlosen Daten.
Das Schreiben der Daten ist im Vergleich nur unwesentlich langsamer durch das pack und length, meine Messungen ergaben ca. 5% Geschwindigkeitseinbußen.

Einziger Nachteil
Einzelne Datensätze dürfen nicht länger sein als durch 4 Byte dargestellt werden können, was einer Länge von ca. 4.2 Gigabyte entspricht... aber das sollte wohl reichen...
Und pro Zeile werden 4 Byte Plattenspeicher verschleudert... aber ich glaub, die schenk ich mir...

Das Ganze geht übrigens noch weiter
Wie kann ich Daten anhängen? Nun, bei herkömmlichen Dateien ginge das ja per

open (my $out,'>>','test.txt') || die "Da ging was nicht $!";
print $out "neue Rechnungsnummer\n";
print $out "neuer Brieftext\n";
close $out;

Mit der neuen Methode gehts ähnlich:

open (my $out,'>>','test.txt') || die "Da ging was nicht $!";
binmode $out;
print $out pack("N",length("neue Rechnungsnummer"))."neue Rechnungsnummer";
print $out pack("N",length("neuer Brieftext"))."neuer Brieftext";
close $out;

So, und nun wirds wieder kompliziert: Daten ersetzen bzw. löschen
Das war ja bei der herkömmlichen Methode schon umständlich: Datei einlesen, Datensatz suchen, alle Daten bis dahin speichern oder in eine temporäre Datei schreiben, dann den gesuchten Datensatz einfügen, und den Rest der Datei hinzufügen, dann alles zusammen schreiben... Sehr langsam...

Man muß sich ja mal klarmachen, wann ein Dateizugriff besonders schnell bzw. langsam ist
Sehr schnell: 1 Byte am Stück
Schnell: 1 MB am Stück
Langsam: 1 MB in 10 Zugriffen
Sehr langsam: 1 MB in 1000 Zugriffen

Ein Zugriff ist also umso schneller, je weniger Daten mit möglichst wenigen Zugriffen gelesen werden. Für das Schreiben gilt übrigens das Selbe.

Das im Hinterkopf, wieder zum Problem, wieder mit Worten:
Suche erst nach dem richtigen Datensatz.
Wenn er gefunden ist, lese alle Daten davor in einem Rutsch ein, schreibe sie bei Bedarf in eine temporäre Datei, füge dann die neuen Daten ein bzw. lösche den Datensatz, und lese dann in einem Rutsch den Rest ein und schreibe ihn.

######################
# Datensatz löschen
######################
$gesucht = '2';

my $filesize= (-s "test.txt");
open (my $in,'<','test.txt') || die "Da gabs wohl nen Fehler: $!";
binmode ($in);

{
my $pos=tell($in);

read($in,my $laenge,4);
last if (!$laenge); # Dateiende erreicht
$laenge=unpack ("N",$laenge);
read ($in,$name,$laenge);

if ($name eq $gesucht){
my $akpos=tell($in);
# alle Daten vorher einlesen
seek ($in,0,0);
read ($in,$datendavor,$pos);

# Dateizeiger auf alles nach dem gesuchten Datensatz legen
seek ($in,$akpos,0);
read($in, $laenge,4);
$laenge=unpack ("N",$laenge);
seek ($in,$laenge,1);

my $restlaenge = $filesize - tell ($in);
read ($in,my $rest,$restlaenge);

close $in;

open (my $out,'>','test.txt');
binmode $out;
print $out $datendavor;
# falls man Daten ersetzen will, dann hier
# print $out pack("N",length($name)).$name;
# print $out pack("N",length($inahlt)).$inhalt;
#
#

print $out $rest;
close $out;
last;
}
else
{
# weiter nach "dem Richtigen" suchen
read($in,$laenge,4);
$laenge=unpack ("N",$laenge);
# "Vorspulen"
seek ($in,$laenge,1);
}
redo;
}
close $in;

Der Datensatz 2 wird gelöscht.

Bingo, das war's.

Was noch zu sagen wäre
Beim Ändern oder Löschen sollte man bei großen Dateigrößen die Daten vor dem Datensatz und die Daten danach in mehreren Blöcken einlesen, da man sich sonst wieder den Systemspeicher vollschreibt. Möglicherweise wäre auch der Ausweg über eine temporäre Datei sinnvoll.

So, das war das, was ich unter "fortgeschrittenes beschreiben von Dateien" nenne.

Ich habe übrigens auch
das Modul Tie::File versucht. Das Modul bindet eine Datei an ein Array, so daß die Datei wie ein Array behandelt werden kann. Und obwohl ich mehrmals gelesen habe, daß die Datei nicht komplett eingelesen wird und das System nicht ausgebremst wird, war Tie::File ziemlich langsam...

Und zum Schluß noch
So manch einer wird nun sagen: Was macht der da, warum nimmt er keine MySQL-Datenbank, da geht sowieso alles schneller...

Richtig!

Aber: Ich habe immer so meine Probleme, mal eben schnell meine MySQL-Datenbank auf USB-Stick zu schreiben, weil ich die Daten gerade auf 'nem anderen PC brauche...
Und außerdem: Dann hätte ich hier ja nix zu schreiben!

In diesem Sinne

Nachtrag
Ich habe die "neue" Methode jetzt auch in mein Cache-Modul eingebaut und war über die Leistung doch ziemlich erstaunt.

Das Neuanlegen von 5000 Datensätzen mit insgesamt 152 MB dauert 15 Sekunden, das Ändern aller bestehenden Datensätze mit wiederum 152 MB dauert 43 Sekunden. Das Lesen eines beliebigen Datensatzes dauert < 1 Sekunde, eine Millisekundenmessung spar ich mir...

Zum Vergleich mit dem "alten" (inzwischen weiterentwickelten) Modul:
Das Neuanlegen dauert 14 Sekunden, das Ändern dauert 175 Sekunden.

Wie erwartet dauert das Schreiben also etwas länger, das Einlesen ist aber superschnell geworden.

Das neue Cache-Modul werde ich in den nächsten Tagen dann hochladen, da gibt es doch einiges anzupassen und zu testen...

Kommentare zum Beitrag "Fortgeschrittenes beschreiben von Dateien"

Kommentar von Manfred

Alter Schwede!!
Ich habe das gerade ausprobiert und bin ebenfalls überrascht.

Was man aus so einer alten Textdatei doch noch herausholen kann ist schon grandios. Vielleicht möchte der Autor noch ein Modul schreiben, mit dem man einfach per read und write und so seine Dateien einfacher beschreiben und lesen kann??? Nur so als Wunsch...

Ansonsten: Top-Beitrag! Gratulation!

Kommentar von Admin

Yo, die Idee ist nicht schlecht!
Vielleicht mach' ich wirklich ein Modul, und je länger ich darüber nachdenke, desto besser gefällt mir die Idee... Aber nicht gleich, bin noch anderweitig beschäftigt.

Danke jedenfalls, freut mich, daß mein Artikel gut ankommt!

Kommentar von f.p.1

Ich will ja nicht rumschleimen, aber es wird hier nicht so viel kommentiert, daher möchte ich es mal es mal schreiben: Ich lese dieses blog immer mit grossem Interesse und Vergnügen. Ich perle für den Job auch rum, ohne Informatiker zu sein, und finde gerade die 'Grundlagenforschung' häufig interessant. Ganz herzlichen Dank!

Kommentar von Admin

Das ist Balsam für die Scripter-Seele...
Danke!

Kommentar von Markus

immer, wenn ich vor so einem Suchproblem stehe, erinnere ich mich an meine Algorithmen-Vorlesung.

Dort haben wir den Quicksort-Algorithmus (http://de.wikipedia.org/wiki/Quicksort) besprochen, der recht einfach funktioniert.

Für seine Einfachheit ist er aber irre schnell, da die Anzahl der Suchvorgänge = Logarithmus Naturalis( Anzahl der Datensätze ) sind.

Bei 100.000 Datensätzen benötige ich im schlimmsten Fall ln 100.000 = 12 Suchvorgänge.

Kommentar von Marco

Dies ist ein wirklich interessanter Beitrag. HERZLICHEN DANK.

Einzige Anregung/Frage: Kann das anfänglich gezeigte Auslesen der Werte aus dem Hash-Array tatsächlich funktionieren? Wenn die Daten in der Datei nach dem Muster
1
Text 1
2
Text 2
3
Text 3
geordnet sind, werden "1", "Text 1", "2", "Text 2" u.s.w. als einzelne Hashelemente abgelegt. Oder irre ich mich? Eine Zuordnung der Texte (also "Text 1" zu "1" und "Text 2" zu "2" u.s.w.) ist dann in einem Hash nicht mehr möglich.

Thema: System Perl Script Leistungsoptimiert Dateien

Der Beitrag "Fortgeschrittenes beschreiben von Dateien" wurde 7225 mal gelesen.

Es wurde 9 x über diesen Beitrag abgestimmt.
Die durchschnittliche Beurteilung liegt bei
1.5 (1 = sehr gut - 6 = grottenschlecht).