Heap statt std::set<int> ?

[rean]

Hi

Ein std::set ist ja typischerweise als Baum implementiert. D.h. dass jeder Knoten drei zusätzliche Pointer abspeichern muss: Vater, linker Sohn, rechter Sohn. Das würde doch bedeuten dass im Fall von std::set<int> 3/4 des verwendeten Speichers (ich gehe mal davon aus dass sizeof(int) = sizeof(void*) ist) nur für Verweise verwendet wird. Wäre es da nicht sinnvoller für diesen Anwendungsfall einen Heap zu nehmen?

mfg

[SideWinder]

Wie implementierst du denn die Datenstruktur Heap?

MfG SideWinder

[rean]

Beispielsweise als min-Heap in einem std::vector.
Der einzige Nachteil wäre eben dass ein neues Element in einen vollen vector nicht mehr mit logarithmischem sondern linearem Aufwand (Umkopieren der Elemente) eingefügt werden könnte.
Dem könnte man zumindest ein wenig entgegenwirken indem man den vector beim Anwachsen gleich mal doppelt so groß macht, man hätte dann im Worst Case immernoch 50% weniger Speicher verwendet als ein set.

[SideWinder]

Naja du musst schon dein Ziel kennen. Ist es in deiner Anwendung wirklich der Speicherverbrauch der dich neckt? Meistens ist es imho besser die Geschwindigkeit im Auge zu behalten.

Wenn du aber dringend wenig Speicher brauchst dann speichert man x Elemente wohl am Besten in einem Array mit x Plätzen. Wenn du dann gleich 2*x reservieren willst fragt man sich ob nicht auch 4*x möglich gewesen wäre und du aber viel Geschwindigkeit dafür haben könntest....

MfG SideWinder

[rean]

War auch eher eine theoretische Frage.
Hab mir schon gedacht dass das nur in sehr speziellen Anwendungsfällen etwas bringen würde.
Wobei der einzige der mir direkt einfallen würde der wäre dass man schon im voraus weiß wieviele Elemente man ungefähr haben wird.

Danke für den Input.

mfg
rean

[SeppJ]

rean schrieb:

Der einzige Nachteil wäre eben dass ein neues Element in einen vollen vector nicht mehr mit logarithmischem sondern linearem Aufwand (Umkopieren der Elemente) eingefügt werden könnte.

Wenn das kein Problem für dich ist, dann war std::set vielleicht von Anfang an die falsche Wahl für deine Anwendung.

[rüdiger]

Wenn man auf die Ordnung verzichten kannst und du große Mengen hast, dann kannst du vielleicht mit unordered_set eine kleine Ersparnis rausholen.

[krümelkacker]

rean schrieb:

Beispielsweise als min-Heap in einem std::vector.
Der einzige Nachteil wäre eben dass ein neues Element in einen vollen vector nicht mehr mit logarithmischem sondern linearem Aufwand (Umkopieren der Elemente) eingefügt werden könnte.

Da der Aufwand für das Umkopieren beim Vergrößern der Kapazität des Vektors aber umgekehrt proportional zur Häufigkeit der Kapazitätserhöhung steht, wächst ein Vektor im Durchschnitt mit konstantem Aufwand.

[volkard]

rean schrieb:

Hi
Ein std::set ist ja typischerweise als Baum implementiert.

Ja.

rean schrieb:

D.h. dass jeder Knoten drei zusätzliche Pointer abspeichern muss: Vater, linker Sohn, rechter Sohn.

Der Vater-Zeiger ist bei vielen Bäumen gar nicht nötig, und wird nur gemacht, damit man auch Iteratoren anbieten kann.

rean schrieb:

Das würde doch bedeuten dass im Fall von std::set<int> 3/4 des verwendeten Speichers (ich gehe mal davon aus dass sizeof(int) = sizeof(void*) ist) nur für Verweise verwendet wird.

Jup.

rean schrieb:

Wäre es da nicht sinnvoller für diesen Anwendungsfall einen Heap zu nehmen?

Das hängt davon ab, was Du machen willst.

Brauchst Du einen Binärbaum mit Löschen an beliebiger Stelle und teuren Elementkopierungen, mußt Du auch mal sehen, daß die allocation granularity von new bei Dir vermutlich 32 Bytes ist. Weil bei Nutzdaten(4)+Verwaltungsdaten(3*4)=16 und 16+{uns unbekannte Verwaltungszeiger}(2*4)=24 und nu {immernochfrei}=8 man durch das Einsparen des Aufwärtszeigers keinen Speicher spart, ist die Diskussion schon recht wirr. Nicht unnötig und nicht schlecht, aber so voller Annahmen über Prozessoren und Standardsbibliotheksimplementierungen, daß es einem ganz schwummrig wird.

Brauchst Du nur einen Heap (PriorityQueue), kannst Du die Daten als Array ablegen und hast 0 Speicheroverhead.

Ich benutze praktisch nie std::set oder std::map. Fast immr brauche ich eigentlich einen Heap oder eine HashTable. Deswegen habe ich so zwei Klassen auf der Platte liegen, in bestimmt asig schlechter Implementierung, aber naja, man muß sich keine Mühe beim Implementieren geben, um eine nicht angemessene Datenstruktur zu outperformen, indem man eine angemessene nimmt.

Heap-Dinge hat die stl dabei. http://www.cplusplus.com/reference/algorithm/pop_heap/ Spaßigeweise nicht als Klasse, aber sich ne Klasse drumzuschrauben kostet da nur Minuten.

Hashtables sind als unordered_* bei Deinem Compiler dabei. Sie sind riskant. Ist Die Hashfunktion (, die Du ja normalerweise selber angibst,) doof, verfuckt die Hashtable und wird langsam wie Popo. Oder noch langsamer.

[life]

Da es anscheinend noch keiner erwähnt hat:

In einem Heap kann man nicht effizient suchen (O(n)). In einem std::set schon (O(log n)).