Sehr dynamische Speicherverwaltung

[TRBB]

Guten Tag,
ich möchte einen sehr effizienten Vokabelübersetzer programmieren und muss dazu eine SEHR große Textdatei (mit den Vokabeln einlesen).


Dies geschieht zurzeit mit einem FileStream

Delphi-Quellcode:

setLength(fBuffer^, fLen); // fBuffer ist ein zeiger auf einen ^AnsiString
fStream.ReadBuffer(PChar(fBuffer^)^, fLen);

Nun werden die Vokabeln herausgelesen (diese sind durch ' :: ' getrennt).
Ich lese nun die einzelnen zeichen aus um die Trennfelder zu bekommen und zwar über fBuffer^[i].

Habe ich eine Vokabel gefunden (ich speichere sie im Beispiel mal als einzelne Chars) muss ich sie aus dem String fBuffer herauskopieren und in einer neuen Stelle im Speicher ablegen.


--Nun die Frage--
Gibt es eine Möglichkeit, dass ich direkt den von fBuffer belegten Speicher weiterverwende und nur manche Stellen wieder frei geben?
zum Beispiel folgendermaßen:

Delphi-Quellcode:

fChar := @fBuffer^[1];
fVokabChar := @fBuffer^[2];
fVokabChar2 := @fBuffer^[3];
// jetzt alles andere (hier nur char 1) löschen und nur fVokabchar behalten:
dispose(fChar);
//und dann den nächsten buffer holen (und wieder selbiges vorgehen)
new(fBuffer);
// fVokabChar und fVokabChar2 sollen weiter verwendbar sein
showMessage(fVokabChar^);

Ich hoffe es ist einigermaßen klar geworden was ich vor habe.

Mfg
TRBB

[guidok]

Zitat:

Zitat von TRBB

Guten Tag,
ich möchte einen sehr effizienten Vokabelübersetzer programmieren und muss dazu eine SEHR große Textdatei (mit den Vokabeln einlesen).

Such mal nach "DAWG", das kommt dem sehr effizient schon recht nahe...


Alternativ könntest du die Datei in eine TStringList einlesen (LoadFromFile) und schau dir hierbei mal das Property "Delimiter" an. Ist allerdings nicht wahnsinnig effizient...

[himitsu]

Ist das Dateiformat von dir?
Wenn, dann stell es doch so zusammen, daß es besser lesbar ist (womöglich schon über Standardfunktionen)

Und was ist für dich "sehr groß"?

[stoxx]

also für eine Vokabelliste brauchst Du keine besonderen Algorithmen zum suchen.
Da reicht eine ganz einfache sortierte Liste.
Selbst wenn Du 16 Millionen Vokabeln hättest, würdest Du diese in einer Sortierten Liste mit Quicksearch mit 24 Vergleichen finden.
Und so schnell kannst Du noch nichtmal gucken. Du willst ja nur EINE Vokabel immer finden, und keine umfangreiche Mustersuche durchführen.

2 Hoch 24 = 16,7 Millionen


Um Sequenzen in Genen zu finden, nimmt man intelligente Algorithmen. Für Dich würde sich ein Suffix Tree eignen. oder der angesprochene DWAG.

edit.

wenn Du allerdings doch alle Vorkommen mit des Wortteils "gestern" anzeigen möchtest. also auch "Vorgestern" .. dann bräuchtest du doch eine intelligente Suche. Dann ist die Frage, ob sich durch Algorithmen oder duch CPU optimierte Programmierung mehr rausholen lässt.

guck mal hier:

http://www.delphipraxis.net/internal...+tree&start=50

[TRBB]

Die Datei ist etwa 26,2 Mb groß und umfasst ca. 695.000 Einträge (englische + deutsche Vokabel).

Bei meinem aktuellen Verfahren dauert das Auslesen der Rohdatei etwa 3 Sekunden was mir zu lang ist. Wenn das nicht viel schneller geht soll es mir recht sein, denn das geschieht einmalig danach kann ich es in meinem eigenen Format speichern.


@guidok & stoxx:
Etwas ähnliches wie DAWG oder Suffix-Tree hatte ich mir auch schon überlegt, bin aber nicht auf die Idee gekommen danach zu suchen^^.
Allerdings musste ich feststellen, dass sich diese Bäume (wenn ich ihre Funktionsweise denn richtig verstanden habe) nicht so gut für ein Wörterbuch eignet, da er zwar gut Wörter speichern kann, doch ich müsste zwei Bäume erstellen (einmal für die deutschen und einmal für die englischen Wörter) und diese müsste ich dann verknüpfen, was (mir zumindest) nicht so leicht erscheint denn wenn ich z.B. das deutsche Wort vollständig gefunden habe wie bekomme ich dann das komplette englische Wort wieder aus dem anderen Baum?

@himitsu:
Was meinst du mit Standartfunktionen? Mit eigenen Dateiformaten habe ich mich noch nicht beschäftigt (das wollte ich machen sobald das Einlesen der Rohdatei effizient ist).
Ich hab zum Testen mal die TStringList verwendet die die Wörter zeilenweise speichert was mir nicht allzu gut gefällt und mir auch nicht sonderlich schnell erscheint (hab allerdings noch keinen Gegenvergleich einer anderen Methode).

@stoxx:
Quicksearch ist schonmal ein guter Begriff vielen Dank. Es soll im Programm umschaltbar sein ob nur am Stringanfang auf Übereinstimmung überprüft werden soll oder auch innerhalb des Strings.
Habe ich jetzt richtig verstanden, dass wenn ich innerhalb des Strings suchen will eig. nicht viel an Performance durch Algorithmen rausholen kann weil es einfach nicht schnell geht?


Schonmal vielen Dank an euch.
TRBB

[stoxx]

Zitat:

Bei meinem aktuellen Verfahren dauert das Auslesen der Rohdatei etwa 3 Sekunden was mir zu lang ist. Wenn das nicht viel schneller geht soll es mir recht sein, denn das geschieht einmalig danach kann ich es in meinem eigenen Format speichern.

26 MB ist nicht viel, hast Du schonmal probiert, einfach mit Stringlist.LoadFromFile die Datei zu laden, wie lange es dauert.
Wenn 26 MB 3 sekunden dauern, dann liegt es am zu kleinen Lesebuffer der Festplatte.

Zitat:

Quicksearch ist schonmal ein guter Begriff vielen Dank.

das eignet sich nur, wenn Du exakt vergleiche möchtest. Du hängst hinter Deinem Deutschen Wort einfach einen Zeiger auf das Englische Wort.
Die Deutschen Wörter sind indiziert, und auch die englischen. Dann kannst Du auf Exaktheit sehr einfach prüfen.
Komplizierter wird es wenn Du auch alle Vorkommen innerhalb eines Strings suchen willst.
Dann wie gesagt, der DWAG. oder Assembler Optimierungen oder Boyer-Moore Algorithmus.
Wie gesagt, musst Du mal testen, was am schnellsten ist.
Nicht immer sind die theoretischen schnellsten üÜberlegungen auch in der Praxis am schnellsten.

Da aber die Vokabeldatei vorher bekannt ist, lassen sich Verfahren nutzen, die die Daten vorverarbeiten können.
Eben der DWAG :-)

[himitsu]

Die 3 Sekunden samt dem Parsen/Zerlegen der Daten?
Dann sind das locker bis zu 10-15 MB die Sekunde und das auch noch durch die WindowsFileCache durchgequetscht ... also soooo schlecht ist das doch garnicht.

26 MB selber sind auch fast nix. (sehr groß geht für mich so bei mindestens im mehreren dreistelligen MB-Bereich los)

Und was das sortieren angeht, da wurde ja schon was gesagt.


Standardfunktionen ... also das was Delphi von Haus aus schon kann (also TStringList und sogar das gute alte ReadLn) und was die Daten selber (z.B. zeilen-/parameterweise) einlesen und zerlegen kann.




PS: wenn du das Dateiformat schon von Haus aus so gestaltest, daß die Daten sortiert und Optimiert darin liegen, dann könntest du die Datei auch via MMF in den RAM laden
und falls der Index nicht schon darin eingebaut ist, dann nur noch einen Index über die dort enthaltenen Daten anlegen.

Erstmal wären dann nicht immer alle Daten im RAM ... Windows versucht "intelligent" das Benötigte (also das worauf grad zugegriffen wird) zu (ent)laden.
So könnte man auch mal locker 'ne 2 GB-Datei in den Speicher laden und das selbst bei nichma 1 GB RAM.

Und wenn der Index schon in der Datei eingebaut ist, dann wäre das Laden in wenigen Millisekunden geschehen (falls man nochmal auf 'ne aufwendige Verifizierung der enthaltenen Daten verzichtet).

[TRBB]

Zu allererst würde ich gerne nochmal genau wissen was ein Index bzw. Indexierung bedeutet.

Ich verstehe darunter nur, dass die Daten entweder in alphabetischer Reihenfolge vorliegen oder in z.B. einem array die Zeiger auf die jeweiligen Wörter in alphabetischer Reihenfolge (bezogen auf das Wort auf das er zeigt) besteht mit dem dann z.B. Quicksearch durchgeführt werden kann.

Zitat:

Zitat von stoxx

26 MB ist nicht viel, hast Du schonmal probiert, einfach mit Stringlist.LoadFromFile die Datei zu laden, wie lange es dauert.
Wenn 26 MB 3 sekunden dauern, dann liegt es am zu kleinen Lesebuffer der Festplatte.

Leider hat die Datei am Anfang noch Kommentare die nicht ausgelesen werden sollen und bei der StringList kann man als Delimiter nur einen Char angeben bei mir sind es aber vier Chars: ' :: ' (Leerstelle, 2 Doppelpunkte, Leerzeichen).

Eine Zeile sieht z.B. so aus (dahinter steht dann ein zeilenumbruch #13):
akutes Problem {n} :: pressing problem

Die Daten liegen bereits vorsortiert darin ich müsste nur eine Seite (also englische oder deutsche Wörter) sortieren was aber kein Problem ist.

DWAG werde ich mir mal Ansehen sobald ich mit dem Abi durch bin ich glaube dazu braucht man etwas mehr Zeit nehme ich an^^

Zitat:

Zitat von himitsu

PS: wenn du das Dateiformat schon von Haus aus so gestaltest, daß die Daten sortiert und Optimiert darin liegen, dann könntest du die Datei auch via MMF in den RAM laden
und falls der Index nicht schon darin eingebaut ist, dann nur noch einen Index über die dort enthaltenen Daten anlegen.

Erstmal wären dann nicht immer alle Daten im RAM ... Windows versucht "intelligent" das Benötigte (also das worauf grad zugegriffen wird) zu (ent)laden.
So könnte man auch mal locker 'ne 2 GB-Datei in den Speicher laden und das selbst bei nichma 1 GB RAM.

Und wenn der Index schon in der Datei eingebaut ist, dann wäre das Laden in wenigen Millisekunden geschehen (falls man nochmal auf 'ne aufwendige Verifizierung der enthaltenen Daten verzichtet).

Verstehe ich das richtig, dass bei MMF die Daten in die Auslagerungsdatei von Windows geschrieben werden?


-----------------
Noch eine generelle Frage:
TStringList speichert seine Strings zeilenweise in eine Datei (bei saveToFile) und lädt sie so auch wieder in den Speicher.
Kann ich irgendwo nachlesen wie es das genau macht, damit ich weis/verstehe wie man effizient Datenformate in den Speicher lesen kann?

[himitsu]

Ein Index ist sozusagen eine Liste oft mit Zeigern auf die entsprechenden Daten
weöche dann selber sortiert werden und und wo man eventuell noch weitere Daten drin speichern/erstellen kann, welche zur Optimierung des Suchen bzw. Verwaltung dienen.

die Kommentage kann man ja nach dem Laden wieder löschen

und was die Delimiter angeht
- entweder nach dem Laden dein " :: " durch nur ein Zeichen ersetzen
- oder eine extra Funktion erstellen, welche dieses dann beim Auslesen eines Wertepaares trennt

MMF = Memory Mapped File
es wird parktisch ein Speicherbereich innerhalb des Virtuellen Prozessspeichers deines Programms reserviert und mit de Datei verknüpft.
Also es wird erstmal kein "echter" RAM damit belegt
beim Zugriff auf diesen Speicherbereich läd Windows den nötigen Teil der Datei in die WindowsFileCache und und erstellt einen Link zwischen dem Speicherbereich und dem Speicher (im RAM) der WindowsFileCache ... diese bereiche werden nun dynamisch (wenn nötig) in die WFC geladen, oder wieder freigegeben und notfalls zurück in die Datei gespeichert (wenn man in diese, Speicherbereich rumschreibt)

in der Auslagerungsdatei landet davon nix.
je mehr physischer RAM frei ist, desto mehr kann in die WFC geladen werden und ist so schneller verfügbar.

Zitat:

Kann ich irgendwo nachlesen wie es das genau macht, damit ich weis/verstehe wie man effizient Datenformate in den Speicher lesen kann?

da du eine Professional hast und somit die Delphi-SourceCodes bei liegen ... schau doch einfach direkt nach

LoadFromFile liegt im TStringList-Vorfahr TStrings (siehe Unit Classes.pas)
dort wird die Datei über einen TFileStream in einen String geladen und an TStrings.SetTextStr übergeben
und SetTextStr zerlegt dann den String und übergibt die einzelnen Zeilen dann an die Funktion .Add.

[alzaimar]

Zitat:

Zitat von stoxx

...sortierten Liste mit Quicksearch...

Früher hieß das mal 'binary search' oder 'Binärsuche'. Ich kenne 'Quicksearch' nur in Verbindung mit Sunday's Stringmatching Algorithmus.