C++ Container

[Fragesteller123]

rüdiger schrieb:

Neeee, lieber http://en.cppreference.com/w/

Warum?

[daddy_felix]

Shade Of Mine schrieb:

Doch, müssen sie. Weil die Größe ist für beide Container ein Template Parameter.

Achso, ok. Danke

[Nexus]

Fragesteller123 schrieb:

Warum?

Weil cppreference im Gegensatz zu cplusplus auch C++11 enthält.

[C++ Container]

Danke euch.
Noch eine Frage: Bei z.B. std::set::find steht unten: Logarithmic in the size of the container. Auf welche Basis bezieht sich das? e? 10?

Danke nochmals.

[Achso]

Auf Basis 2

[KMT]

Prinzipiell ist die Basis da eigentlich egal, diese Aussage soll eher die grundsätzliche Komplexität angeben - die mit der Anzahl der Elemente eben logarithmisch, d.h. "langsam" wächst. D.h. mutlipliziert man die Anzahl der Elemente mit einem Wert x, steigt der Aufwand nur um einen (immer festen) Wert y.
set verwendet ein binäre Suche, also wenn du eine spezielle Basis wissen willst wärs wohl die 2.

[C++ Container]

KMT schrieb:

set verwendet ein binäre Suche, also wenn du eine spezielle Basis wissen willst wärs wohl die 2.

omg, darauf hätte ich selbst kommen können, danke dir trotzdem.

[Bashar]

Die Basis spielt keine Rolle, weil sie im konstanten Vorfaktor untergeht: $\log\_a x = \frac{\log\_b x}{\log_b a}$

[STL Container]

Bashar schrieb:

Die Basis spielt keine Rolle, weil sie im konstanten Vorfaktor untergeht: $\log\_a x = \frac{\log\_b x}{\log_b a}$

Kannst du mir das näher erklären, bitte?

Angenommen ich habe ein vector mit 4 Mrd. Elementen und suche das letzte Elemente. Dafür brauche ich z.B. 3 Sekunden.
Angenommen ich nehme dann ein set mit 4 Mrd. Elementen und suche das unterste Blatt im Binärbaum. Dafür brauche ich z.B. 500 ms.

Dann mache ich das Ganze mit 2 Mrd. Elementen.
Dann brauche ich z.B. mit vector noch 1,5 Sekunden und mit set noch 250 ms.

Ahhh, ich glaube ich hab Gerade ein AHA-EFFEKT. Wenn ich nun bei set logb(4mrd.) / logb(2mrd.) rechne, spielt die Basis keine Roll mehr. Wolltest du mir das sagen, Bashar?

[STL Container]

ich meinte natürlich: logb(500) / logb(250)

[hustbaer]

Naja, ne, du brauchst ja gerade nicht 250ms statt 500ms sondern eher ca. 484ms.
(Wobei 500ms unrealistisch lange ist)

Und ne, log(4Mrd.)/log(2Mrd.) wäre schon richtig gewesen.

[Bashar]

STL Container schrieb:

Bashar schrieb:

Die Basis spielt keine Rolle, weil sie im konstanten Vorfaktor untergeht: $\log\_a x = \frac{\log\_b x}{\log_b a}$

Kannst du mir das näher erklären, bitte?

Kennst du die O-Notation? Ohne das jetzt genauer (und richtiger) zu erklären, heißt "Elementzugriff bei std::set hat eine Laufzeit von O(log n)", dass der tatsächliche Laufzeitbedarf eher sowas wie K*log(n) + Kleinkram ist. Die O-Notation abstrahiert den Vorfaktor K sowie die anderen Terme, die in dem Fall vom Logarithmus dominiert werden, weg. (Und jetzt lies es nochmal bei Wikipedia oder in einem Algorithmenlehrbuch nach.)

Das ist schon deshalb sinnvoll, weil ein Algorithmus nicht besser wird, bloß weil du einen doppelt so schnellen Rechner kaufst. Da ist dann der konstante Vorfaktor nur noch halb so groß, aber an der Aussage O(log n) ändert sich nichts.

Wenn du jetzt die Basis des Logarithmus änderst, dann kommt ein zusätzlicher Faktor dazu (siehe mein obiges Zitat), der mit dem schon vorhandenen Faktor zu einem verschmilzt und bei der O-Notation sowieso wegfällt. Das heißt alle Klassen $O(\log_b n)$ sind gleich, und deshalb kann man das b auch weglassen.

Ahhh, ich glaube ich hab Gerade ein AHA-EFFEKT. Wenn ich nun bei set logb(4mrd.) / logb(2mrd.) rechne, spielt die Basis keine Roll mehr. Wolltest du mir das sagen, Bashar?

Nicht direkt, aber das kommt ungefähr auf das gleiche raus.