Datenstrukturen effizient speichern und abrufen
-
Hallo,
habe eine sehr allgemeine Frage:
Ich bin dabei, ein sehr einfaches Wörterbuch (Übersetzung) in C zu schreiben. Die Abfragen sollen möglichst schnell beantwortet werden, daher wird ein sortiertes File, dass die Übersetzungen enthält, in ein struct-array eingelesen und hinterher bei jeder Abfrage eine binäre Suche bei diesem array durchgeführt. Das führt jedoch zu dem Problem, dass tausende von Vokabeln im virtuellen Speicher landen, obwohl das Programm (je nach Benutzerverhalten) vermutlich bis zur Terminierung nur Zugriff auf max. einige Dutzend Vokabeln benötigt. Daher braucht dieses recht simple Tool bereits über 100MB RAM, außerdem verzögert sich die Startzeit.
Gibt es eine Möglichkeit, die benötigten Daten auf der Festplatte zu speichern, aber trotzdem die binäre Suche zu ermöglichen?
Ich dachte ja an Datenbanken, aber die bieten m.E. viel, viel mehr als ich brauche und blähen das Programm nur unnötig auf.
Irgendwelche Ideen?
-
Dein Problem nennt sich externes Suchen. Vielleicht kannst du mit einem B-Baum etwas anfangen.
-
ja, es geht.
benutzt Du fopen?
dann fseek() http://www.cplusplus.com/reference/clibrary/cstdio/fseek/oder mach doch auf der platte im file eine hastable, der hashwert bestimmt den 4k großen sektor und innerhalb der sektoren liegen sie sortiert. das ist doch DIE anwendung fürs hashen. und es kommt denkbar einfacher code heraus.
-
Wie soll mir den fseek() alleine weiterhelfen? Die Datei ist in Zeilen unterteilt, die Streuung der Zeilenlänge ist sehr groß. fseek() bietet mir ja nicht die Möglichkeit, zur Zeile X zu springen, jedenfalls nicht, bevor ich die Datei umstrukturiere.
Mit der Kombination eines hashtables lässt sich da natürlich was machen, daran hatte ich noch garnicht gedacht.
Das mit dem B-Baum werde ich mir ebenfalls ansehen. Danke für die Vorschläge.
-
default user schrieb:
Wie soll mir den fseek() alleine weiterhelfen? Die Datei ist in Zeilen unterteilt, die Streuung der Zeilenlänge ist sehr groß.
Das müßtest Du für binäre Suche ändern.
default user schrieb:
fseek() bietet mir ja nicht die Möglichkeit, zur Zeile X zu springen, jedenfalls nicht, bevor ich die Datei umstrukturiere.
Oder einmal einlesen und sich die Dateipositionen der Stringanfänge merken in einem Array im RAM. Oder einer Indexdatei auf Platte.
-
default user schrieb:
Wie soll mir den fseek() alleine weiterhelfen? Die Datei ist in Zeilen unterteilt, die Streuung der Zeilenlänge ist sehr groß. fseek() bietet mir ja nicht die Möglichkeit, zur Zeile X zu springen, jedenfalls nicht, bevor ich die Datei umstrukturiere.
Das Zeilenende ist mit '\n' markiert. Insofern könntest du schon direkt mit binärer Suche arbeiten, wobei du bei jedem Halbier-Schritt noch eine kleine lineare Suche dranhängst um das nächste oder vorige '\n' zu finden. Dann wäre das nicht binäre Suche über die Zeilen, sondern eher über die Bytes der Datei, aber das ist ja egal.
Das wäre eine sehr simple Lösung. Das Dateiformat zu ändern wär komplizierter, aber möglicherweise effizienter und sauberer.
Wenn ich so drüber nachdenke, wäre das Dateiformat zu ändern vermutlich auch einfacher zu implementieren. Wenn man die Zeilenenden nach jedem Binäre-Suche-Sprung linear raussucht und dabei nicht sehr genau aufpasst, landet man schnell in einer Endlosschleife. Datensätze mit identischer Länge sind einfacher zu handhaben.
default user schrieb:
Daher braucht dieses recht simple Tool bereits über 100MB RAM, außerdem verzögert sich die Startzeit.
100MB erscheint mir zu viel für ein Wörterbuch, das nur Vokabeln enthält. Oder sind da für jede Vokabel einige Seiten Erklärungen drin?
Wegen Startzeit kannst du dich übrigens auch darauf verlassen, dass das Betriebssystem die benötigten Teile der Wörterbuch-Datei im Cache halten wird. Die erste Startzeit verkürzt das natürlich nicht, aber vielleicht entspricht das ja deinem Anwendungsfall.
Nur als Beispiel, für einen sehr speziellen Anwendungsfall brauchte ich mit möglichst geringem Programmieraufwand ein Skript, das ein Wort in einer gegebenen 10MB-Wörterbuchdatei findet und für jede Anfrage neu gestartet wird. Das einfachste was mit einfiel war das Programm grep zu nutzen, d.h. lineare Suche. Ist nicht schön und auch nicht effizient, aber dank Caching des Betriebssystems und sehr effizienter String-Suche von grep liefert sogar so eine furchtbare Lösung im Bruchteil einer Sekunde die Antwort. 10MB im RAM linear zu durchsuchen geht heutzutage einfach unglaublich schnell; die Wörterbuch-Datei mit einem richtigen Index zu versehen hätte den Programmieraufwand um ein Vielfaches erhöht. Deswegen würde ich versuchen nicht zu viel neu zu erfinden.
Wenn du genug Interesse an deinem Programm hast, würde ich aber keine lineare Suche nehmen, das ist klar.
default user schrieb:
Ich dachte ja an Datenbanken, aber die bieten m.E. viel, viel mehr als ich brauche und blähen das Programm nur unnötig auf.
Zum Beispiel sqlite bläht kaum.