map auch schnell bei kleiner Anzahl?
-
Hallo,
ich will int,int Tupel speichern. Der 1. Wert ist eine Art Schlüssel und der 2. das Attribut. Jetzt bietet sich dafür natürlich eine map<int,int> an.
Der Punkt ist nur: Es werden zu 99% sehr wenige Paare sein (so 3 oder 4 Stück meistens).Die Frage: Wenn ich so wenige Werte in der map habe, ist dann map überhaupt noch effizient? Bei myMap[key] = value; wird ja mit O(logn) gesucht und wenn ich einen vector< pair<int,int> > hätte, könnte ich linear O(n) nach dem Key suchen. Nur bei so wenigen Werten, könnte die lineare Suche ja effektiv schneller sein.
Kurz: Ist auch bei wenigen Werten map schneller beim einfügen und überschreiben oder ist dann ein vector besser?
-
Hört sich so an, als ob du die 99% in die map stecken solltest und nicht die Paare.
-
terraformer schrieb:
Hört sich so an, als ob du die 99% in die map stecken solltest und nicht die Paare.
Versteh ich nicht. Ein Key hat einen Value. Es sind eben immer Paare. Und ganz ganz selten ändert sich der Value eines Keys.
-
Im Zweifelsfall immer Ausprobieren (und zwar am echten Programm, nicht an einem Testprogramm nur für diesen einen Vergleich), da immer viele Faktoren eine Rolle spielen. Wenn du wissen willst, welches Ergebnis ich erwarte: Ich schätze der Vektor wird deutlich schneller sein.
-
SeppJ schrieb:
Im Zweifelsfall immer Ausprobieren (und zwar am echten Programm, nicht an einem Testprogramm nur für diesen einen Vergleich), da immer viele Faktoren eine Rolle spielen. Wenn du wissen willst, welches Ergebnis ich erwarte: Ich schätze der Vektor wird deutlich schneller sein.
Habs befürchtet. Zeitmessungen sind halt immer recht aufwändig (um wirklich verlässliche Daten zu haben und nicht nur Stichproben).
Tippe aber auch, dass der Vektor schneller ist.
-
Das sollte die lineare Suche im vector gewinnen. Aber das kann man ja ganz einfach ausprobieren.
Edit: ausprobiert, 4 Elemente: vector<pair<int,int>> : map<int,int> = 31 ms : 39 ms
-
performer2 schrieb:
Der Punkt ist nur: Es werden zu 99% sehr wenige Paare sein (so 3 oder 4 Stück meistens).
Und bei 1% sehr viele Paare, so 1000000 Stück?
performer2 schrieb:
Die Frage: Wenn ich so wenige Werte in der map habe, ist dann map überhaupt noch effizient? Bei myMap[key] = value; wird ja mit O(logn) gesucht und wenn ich einen vector< pair<int,int> > hätte, könnte ich linear O(n) nach dem Key suchen. Nur bei so wenigen Werten, könnte die lineare Suche ja effektiv schneller sein.
Unbedeutend. Die map könnte 4 Speicherzugriffe brauchen, wo der vector einen braucht. Das bißchen Vergleichen und Zeigerentlanghangeln, dorfte nichtz schlimm sein. Ich tippe mal unte ungünstigen Bedingungen Faktor 5 für den vector.
Beim Lesen. Und beim Ändern der Werte, wenn die keys sich nicht ändern.Beim Einfügen ist das ganz anders, da kackt die map völlig ab. Aber Du sagtest ja, daß Du sehr selten was änderst.
Ich würde dem vector bis 20 keys durchaus trauen und bis 50 würde ich ohne schlechtes Gewissen ausnahmsweise in Kauf nehmen.
-
performer2 schrieb:
terraformer schrieb:
Hört sich so an, als ob du die 99% in die map stecken solltest und nicht die Paare.
Versteh ich nicht. Ein Key hat einen Value. Es sind eben immer Paare. Und ganz ganz selten ändert sich der Value eines Keys.
Na, ich dachte du hast 100000 solche Paare.
