C
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.
