Strings extrem schnell speichern und laden

[Prototypjack]

Moin,

Ich habe hier mal wieder ein Problem:

Wie kann ich eine Reihe an Strings möglichst schnell aus einer Datei laden (das Speichern muss nicht ganz so schnell erfolgen)? Ist ein binäres Dateiformat der beste Weg? Für mich kommen auch keine Third-Party-Libraries bzw. Dlls und dergleichen in Frage.

Weitere Informationen:

• Die Strings müssen einen frei setzbaren Identifier besitzen können.
• Die Länge ist unbekannt.
• Datengröße der Chars ist 16bit (Unicode)
• Ich kann keine Stringlists und dergleichen benutzen, da ich die Strings immer einzeln laden muss und die Datei dann wahrscheinlich (um Arbeitsspeicher zu sparen) nicht ständig im RAM liegt. Das heißt: Ich muss extrem speichereffizient und schnell Arbeiten.

Welche Methode könnt ihr empfehlen?

Danke & Grüße,
Max

[3_of_8]

Ich würde an den Anfang der Datei eine einfache Tabelle schreiben, die jedem Stringbezeichner den Offset innerhalb der Datei und die Länge des Strings zuordnet. Daraus kannst du dann eine Hashmap erstellen, die du ständig im RAM hast. Wenn du jetzt einen String laden willst, schaust du in deiner Hashtabelle nach, suchst den passenden Offset und liest einen String der gefundenen Länge aus. Wenn du nicht "vorhersehen" kannst, ob du auch noch andere Strings aus der Gegend brauchen kannst, dürfte es nicht schneller gehen.

Bei Andorra ist glaube ich ein gepufferter Dateistream dabei, der vor allem bei großen Dateien extrem schnell ist - wie es mit Speicherverbrauch aussieht, weiß ich nicht genau.

Wie groß sind denn deine Dateien, dass du dir um Speicherverbrauch sorgen machst? Eine sinnvolle Alternative zu diesem doch recht umständlichen Vorgehen wäre eine Datenbank, die Dinger sind extrem schnell und fressen auch nicht so viel Speicher - das wäre meine Lösung, wenn es wirklich um große Datenmengen geht.

[Prototypjack]

Moin,

Die Datenmengen sind in der Regel klein (höchstens ein paar Megabyte). Ich will lediglich so schnell (!) und so schonend wie möglich arbeiten.

Das mit der Hashmap habe ich jedoch nicht wirklich verstanden, wie genau meinst du das? Achja: Habt ihr vielleicht noch weitere Literatur wie man solche Dateiformate am besten aufbaut (ich habe sowas bisher noch nie gemacht)?

Danke & Grüße,
Max

[Fridolin Walther]

Zitat von Prototypjack:

Die Datenmengen sind in der Regel klein (höchstens ein paar Megabyte). Ich will lediglich so schnell (!) und so schonend wie möglich arbeiten.

Es würde (mir zumindest) helfen, wenn Du kurz umschreiben könntest was das für Daten sind. Für mich liest sich das so als würdest Du versuchen den Unix Befehl string zu implementieren um aus einer beliebigen Binärdatei alle lesbaren Zeichen zu extrahieren. Allerdings fragst Du ja auch nach einem Dateiformat. Von daher würd das irgendwie nicht passen. Vielleicht stell ich mich auch einfach nur zu dumm an .

[himitsu]

Zitat von Prototypjack:

Das mit der Hashmap habe ich jedoch nicht wirklich verstanden, wie genau meinst du das?

Wnn man davon ausgeht, daß die Identifier Strings sind, dann wird eine Liste mit jeweils dem Hash des Identifier und der Text-Position in der Datei erstellt.

Ein Hash (z.B. als Interger) läßt sich schneller suchen/vergleichen, als ein ganzer String.

und beim Suchen in soeiner Liste wird dann sozusagen erstmal aus dem Such-Identifier ein Hash erstellt und dieser dann schön schnell gesucht.

[alzaimar]

Der Hash-Wert wird dabei jedoch als Index verwendet, um die Suche noch weiter zu optimieren. Hier von einer 'Liste' zu sprechen, ist falsch. Eine Hashmap ist eine extrem effiziente Datenstruktur zum speichern und finden von Name/Value-Paaren. Näheres hier im Wiki..

Ich würde doch RAM spendieren, um einen MRU-Cache vorzuschalten. Dann werden oft benötigte Strings im Speicher gehalten, der Zugriff geht dann noch wesentlich schneller.

[3_of_8]

Wenn es nur ein paar Megabyte sind, kannst du die Dinger problemlos komplett im Speicher ablegen.

[Sir Rufo]

Zitat von 3_of_8:

Wenn es nur ein paar Megabyte sind, kannst du die Dinger problemlos komplett im Speicher ablegen.

Ich meine aus seiner Aussage im Eröffnungsthread [nein ... ist #3] herauszulesen, dass die Größe der Dateien im Laufe der Zeit auch stark anwachsen kann, und da will er halt vorbeugend eine vernünftige Lösung haben.

Denn Vorbeugen ist besser als auf die Schuhe

cu

Oliver

[alzaimar]

@3_of_8: Das habe ich mich noch nicht mal getraut, zu erwähnen.
@Rufo: Deshalb ein Cache.

Bei der Dateistruktur ist es allerdings nicht trivial, denn wenn man 3_of_8's Vorschlag aufgreift, müsste man die komplette Datei jeweils neu schreiben, und das wäre etwas unperformant.

[Apollonius]

Wie sieht es hier eigentlich mit MMFs aus? Gibt es da Performance-Einbußen gegenüber normalem Datei-IO? Das Problem mit dem Schreiben wäre damit zumindest gelöst, wenn man sich eine vernünftige Datenstruktur ausdenkt.