std::map - key austauschen

[Shade Of Mine]

Optimizer schrieb:

Für die map sollte so ein Allokator ohnehin nicht funktionieren, weil was die map allokiert ist nicht sizeof(pair), sondern sizeof(node).

Deshalb gibt es rebind...
Sonst waeren allokatoren ja komplett sinnlos.

Die Allokation und Deallokation, die du umgehen willst, ist O(1), das finden und einfügen O(log n). Wenn die Allokation trotzdem deine Laufzeit dominiert, hast du wahrscheinlich nicht viele Einträge. In diesem Fall ist es vielleicht besser, gleich einen sortierten vector<pair> zu verwenden. Bei wenigen Elementen ist das einfügen mit verschieben nicht teuer, finden geht in O(log n) und Allokationen hast du keine.

Das Problem ist, dass die lookup table einmal 5 und einmal 500000 eintraege hat. Und ich das vorher nie sagen kann. Ich kann jetzt natuerlich 2 oder 3 implementierungen liefern - aber das hier ist ein super Beispiel warum man nicht die O-Notation als alles bestimmendes kriterium nehmen darf.

Denn allokation ist zwar O(1) aber mit einer sehr hohen konstanten. Solche Probleme wie cache lokalitaet lassen wir mal komplett aussen vor - das kommt naemlich eigentlich auch noch dazu.

Die lookups ansich sind schon enorm schnell - vorallem da ich da auch sehr viel cache. eine hashmap koennte uU etwas speed bringen, aber das haengt dann eben von der hash funktion ab und da ist mir aktuell ein binaerer baum wegen dem besseren worst case lieber.

aktuell laeuft es ja auch mit der sinnlosen allokation und die performance ist tragbar, aber es gefaellt mir dennoch nicht. es waere viel sinnvoller wenn alle nodes in der selben page liegen wuerden, dann gaebe es deutlich weniger page faults.

@vlad_tepesch:
genau das ist aber nicht erlaubt. sobald ein allokator member variablen hat, ist es praktisch unmoeglich ihn portabel zu verwenden.

denn:

allocator_type alloc;

//folgendes muss aequivalent sein:
allocator_type().allocate(1);
alloc.allocate(1);

und das ist nicht garantierbar wenn alloc intern speicher verwaltet. man muss den speicher statisch machen und dann muss man synchronisieren und dann wird es teuer.

@filmor:
mhm, *_heap habe ich nicht bedacht. Mal ansehen. Mir ist aktuell unklar wie push_heap in O(log n) laufen kann - aber das laesst sich ja bald heraus finden. uU ist das genau die richtige loesung. mal sehen.

[Shade Of Mine]

ah, *_heap ist ziemlich genial - aber leider fuer mich nicht verwendbar da ich iteratoren auf die map brauche die nicht invalidieren.

[Gast]

Heap würde auch nicht sortieren - du bräuchtest aber eine Sortierung, um ein bestimmtes Element schnell zu finden. Damit die Iteratoren nicht invalidieren brauchst du aber tatsächlich Node-Container. Sieh dir mal Boost.Intrusive an, dass sind Container, die die Elemente selber manipulieren um die Verkettung zu realisieren. Das gibt dir eine gute Kontrolle darüber, wie der Speicher verwaltet wird. Vielleicht ist da was brauchbares dabei.

[.filmor]

Optimizer schrieb:

Heap würde auch nicht sortieren - du bräuchtest aber eine Sortierung, um ein bestimmtes Element schnell zu finden.

Element finden geht auch in Heaps in O(log n) (weil's ja im Prinzip ein Binärbaum in linearem Speicher ist).

Shade Of Mine schrieb:

ah, *_heap ist ziemlich genial - aber leider fuer mich nicht verwendbar da ich iteratoren auf die map brauche die nicht invalidieren.

Das hamwa gern, wichtige Voraussetzungen zurückhalten
Aber wenn du eh sehr kleine Objekte da rumschiebst, kannst du dann statt der Iteratoren nicht einfach Kopien von denen halten?
Oder du könntest dir (da du den Heap ja sicher eh anständig kapseln willst) einen Heapiterator schreiben, der sich selbst schön valide hält (wenn Heap geändert, guckstu neu) oder einfach jedesmal das durchsteppen in Kauf nimmt.

[life]

.filmor schrieb:

Optimizer schrieb:

Heap würde auch nicht sortieren - du bräuchtest aber eine Sortierung, um ein bestimmtes Element schnell zu finden.

Element finden geht auch in Heaps in O(log n) (weil's ja im Prinzip ein Binärbaum in linearem Speicher ist).

Nein, denn es ist zwar im Prinzip ein Binärbaum (zumindest der Binäre Heap), aber eben kein Suchbaum.

[life]

*doppelpost*

[Gast]

life schrieb:

.filmor schrieb:

Optimizer schrieb:

Heap würde auch nicht sortieren - du bräuchtest aber eine Sortierung, um ein bestimmtes Element schnell zu finden.

Element finden geht auch in Heaps in O(log n) (weil's ja im Prinzip ein Binärbaum in linearem Speicher ist).

Nein, denn es ist zwar im Prinzip ein Binärbaum (zumindest der Binäre Heap), aber eben kein Suchbaum.

[Gast]

http://www.boost.org/doc/libs/1_36_0/doc/html/intrusive/avl_set_multiset.html
Ich sehe keine map, aber man könnte hier ein pair reintun und nur nach dem key vergleichen.

[Shade Of Mine]

Optimizer schrieb:

http://www.boost.org/doc/libs/1_36_0/doc/html/intrusive/avl_set_multiset.html
Ich sehe keine map, aber man könnte hier ein pair reintun und nur nach dem key vergleichen.

rbtree ist ein binaerer suchbaum

aber boost::intrusive ist hier ein genialer ansatz, da ich die nodes ploetzlich in der liste und im baum halten kann - ich habe dadurch eine enorm gute cache lokalitaet und kann alle nodes im voraus allokieren... muss nur die zeit finden es zu implementieren - aber auf der todo liste steht es schonmal oben

[Gast]

Und, hat's gerockt? Vielleicht brauche ich sowas auch mal...

[Shade Of Mine]

Optimizer schrieb:

Und, hat's gerockt? Vielleicht brauche ich sowas auch mal...

wie koennte es anders sein: ich haenge am design fest.

ich will es moeglichst generisch machen, denn hardcoded rbtree und list zu vereinen waere uncool. und das wirft eine menge design entscheidungen auf und ich habe noch keinen schoenen weg gefunden.

das ist das privileg wenn man das als hobby projekt macht ich wuenschte den luxus haette ich immer. aber dafuer dauert sowas triviales halt auch ein monat oder mehr