mmap-ladbare Datenstrukturbibliothek für C ++ (oder C)

9

Ich habe eine große Datenstruktur (N & gt; 10.000), die normalerweise nur einmal (zur Laufzeit) erstellt werden muss und danach viele Male wiederverwendet werden kann, aber sie muss sehr schnell geladen werden. (Es wird für die Verarbeitung von Benutzereingaben auf iPhoneOS verwendet.)% Co_de% -ing eine Datei scheint die beste Wahl zu sein.

Gibt es Datenstrukturbibliotheken für C ++ (oder C)? Etwas auf der Linie

%Vor%

Danke!

Details:

Ich habe selbst eine ähnliche Klasse für die Hashtabelle geschrieben, aber ich finde es ziemlich schwierig, sie zu pflegen, also würde ich gerne sehen, ob es bereits Lösungen gibt. Die Bibliothek sollte

  • Enthält eine creation -Routine, die die Datenstruktur in eine Datei serialisiert. Dieser Teil muss nicht schnell sein.
  • Enthält eine loading -Routine, die eine Datei in eine schreibgeschützte (oder schreibgeschützte) Datenstruktur kopiert, die innerhalb von O (1) Verarbeitungsschritten verwendet werden kann.
  • Verwenden Sie O (N) Menge an Speicherplatz / Speicherplatz mit einem kleinen konstanten Faktor. (Das Gerät hat schwerwiegende Speicherbeschränkungen.)
  • Kleiner Zeitaufwand für Accessoren. (d. h. die Komplexität wird nicht modifiziert.)

Annahmen:

  • Bit-Darstellung von Daten (z. B. Endianess, Kodierung von mmap usw.) spielt keine Rolle, da sie nur lokal verwendet wird.
  • Bisher sind die möglichen Arten von Daten, die ich brauche, Ganzzahlen, Strings und float von ihnen. Zeiger erscheinen nicht.

P.S. Kann Boost.Intrusive helfen?

    
kennytm 20.02.2010, 09:28
quelle

6 Antworten

3

Sie könnten versuchen, eine Speicherabbilddatei zu erstellen und dann die STL-Kartenstruktur mit einem Kundenzuordner zu erstellen. Ihr Kundenzuordner nimmt dann einfach den Anfang des Speichers der Speicherabbilddatei und erhöht dann den Zeiger entsprechend der angeforderten Größe. Am Ende sollte der gesamte zugewiesene Speicher im Speicher der Memory-Mapped-Datei sein und später wieder geladen werden können.

Sie müssen prüfen, ob der Speicher von der STL-Map frei ist. Wenn dies der Fall ist, verliert Ihr Kundenzuordner etwas Speicher der im Speicher abgelegten Datei, aber wenn dies begrenzt ist, können Sie wahrscheinlich damit leben.

    
Patrick 20.02.2010 09:48
quelle
1

Klingt wie vielleicht Sie könnten einen der "perfekten Hash" Dienstprogramme dort draußen verwenden. Diese verbringen einige Zeit damit, die Hash-Funktion für die bestimmten Daten zu optimieren, so dass es keine Hash-Kollisionen und (für minimale perfekte Hash-Funktionen) gibt, so dass es keine (oder zumindest wenige) leere Lücken in der Hash-Tabelle gibt. Offensichtlich soll dies selten erzeugt werden, aber häufig verwendet werden.

CMPH behauptet, mit einer großen Anzahl von Schlüsseln fertig zu werden. Allerdings habe ich es nie benutzt.

Es besteht eine gute Chance, dass nur die Hash-Funktion generiert wird und Sie damit die Datenstruktur generieren können. Das sollte nicht besonders schwierig sein, aber es lässt dich möglicherweise immer noch dort, wo du jetzt bist - zumindest einen Teil des Codes selbst behalten.

    
Steve314 20.02.2010 09:44
quelle
0

Ich dachte nur an eine andere Option - Datadraw . Auch hier habe ich das nicht benutzt, also keine Garantien, aber es behauptet, ein schneller, persistenter Datenbankcodegenerator zu sein.

    
Steve314 20.02.2010 10:02
quelle
0

WRT boost.Intrusive, ich habe gerade einen Blick geworfen. Es ist interessant. Und ärgerlich, da es eine meiner eigenen Bibliotheken ein wenig sinnlos macht.

Ich dachte dieser Abschnitt sah besonders relevant aus.

>

Wenn Sie "Smart Pointer" für Links verwenden können, kann vermutlich der Smart-Pointer-Typ mit einer einfachen Offset-from-Base-Adresse-Ganzzahl implementiert werden (und ich denke, das ist der Punkt des Beispiels). Ein Array-Index könnte ebenso gültig sein.

Es gibt sicherlich eine ungeordnete Menge / Multiset-Unterstützung (C ++ - Code für Hash-Tabellen).

    
Steve314 20.02.2010 10:38
quelle
0

Die Verwendung von cmph würde funktionieren. Es hat die Serialisierungsmaschinerie für die Hash-Funktion selbst, aber Sie müssen immer noch die Schlüssel und die Daten serialisieren und darüber hinaus eine Schicht der Kollisionsauflösung hinzufügen, wenn Ihr Abfrageset-Universum vorher nicht bekannt ist. Wenn Sie alle Schlüssel vor der Hand kennen, dann ist es der Weg zu gehen, da Sie die Schlüssel nicht speichern müssen und viel Platz sparen. Wenn nicht, würde ich für so eine kleine Menge sagen, dass es zu viel ist.

Wahrscheinlich ist die beste Option, die sparse_hash_map von Google zu verwenden. Es hat sehr geringen Overhead und hat auch die Serialisierungs-Hooks, die Sie brauchen.

Zypern

    
Davi 10.07.2010 22:38
quelle
0

GVDB (GVariant Database), der Kern von Dconf ist genau das.

Siehe git.gnome.org/browse/gvdb , dconf und bv
und developer.gnome.org/glib/2.30/glib-GVariant.html

    
Rob Taylor 10.05.2012 10:37
quelle