Optimnierungen für read-only-map
-
Hallo,
Ich brauche eine map, die einmal aufgebaut wird (zeitunkritisch), dann aber recht heftig verwendet wird (typisch 20 Instanzen x 100 Einträge, mehr immer denkbar
).Gibt es dafür bekannte Optimierungen? Geschwindigkeit und cache-Freundlichkeit sind wichtig.
Was ich mir bisher gedacht habe:
(1) statt std::map ein sortierter vector und binäre Suche. benötigt weniger Speicher (Allokationsoverhead, Struktur) und sollte die gleiche performance liefern
(2) eigene binäre Suche, die das ergebnis eines Stringvergleichs (+1/0/-1) verwendet, statt zweimal less<>, da der Stringvergleich eher aufwendig ist
Die Schlüsselstrings sind aber meist kurz (typisch 10 zeichen)(3) statt "linearer" sortierung in der reihenfolge eines balance trees: das mittlere element an die [0], das mittlere des linken teilbaums and die [1], des rechten an die [2] usw.
Ich kann mir vorstellen, daß dies cache-effizienter ist (inkrementeller Zugriff statt herumspringen), wird aber nur in den untersten leveln was bringen
Kommentare? Links? Ideen?
-
guck mal nach ternary search tree.
und bei den toll kurzen strings ist vielleicht ne hashtable angemessen.
-
um größenordnungen schneller, wenn zur compilezeit die möglichen keys bekannt sind, was überraschend oft der fall ist, wenn man sich erstmal von dem gedanken lösen kann, erst einen universellen xml-parser schreiben zu mössen, um ihn dann doch speziell zu verwenden:
http://www.eptacom.net/pubblicazioni/pub_eng/mphash.html
-
peterchen schrieb:
(3) statt "linearer" sortierung in der reihenfolge eines balance trees: das mittlere element an die [0], das mittlere des linken teilbaums and die [1], des rechten an die [2] usw.
Das kann die STL von Haus aus, wenn dein balance tree dem Heap entspricht (was nach deiner Beschreibung zutrifft).
make_heap
push_heap
pop_heap
sort_heapDie Suchfunktion musst du dann wohl selbst schreiben, das sollte aber nicht so das Problem sein.
Du kannst dir auch die Implementierung des AssocVector aus Loki anschauen, der ist afaik genau dafür da.
-
Cool! Heaps sind immer unter meinem Radar langgeflogen. Danke für die Info.
-
Ein heap ist aber nicht zum Suchen geeignet.
Man kann aber natürlich auch einen sortierten Baum so im Array ablegen. Wirste allerdings vermutlich selber implementieren müssen.
-
wenn schon dichte packung, dann einfach sortiertes array und binary_search.