Arrayoperationen beschleunigen

[alzaimar]

Zitat von Der_Unwissende:

Nicht dass das noch ansatzweise zum eigentlichen Topic gehört, aber optimal in Bezug auf was? Laufzeit oder Speicherausnuztung? Und für Letzteres wäre sicherlich mehr reservieren suboptimal. Aber ich glaube, dass keiner behauptet hatte, dass die 172/176% optimal sind, oder?

Aber mal interesse halber, mit welcher Größe startest du denn? Da hast du doch sicherlich auch einen Erfahrungswert, denke nicht dass du erst 1 Element hast und dann immer verdoppelst.

Doch, ich finde, das gehört zum Topic "Arrayoperationen beschleunigen". Und da es um "Beschleunigen" geht, ist logischerweise das "optimal" auf die Geschwindigkeit bezogen, insofern ist deine Frage überflüssig. Und es wird behauptet, die 172/176% seien irgendwie 'besser' als andere Faktoren, nicht unbedingt in diesem Thread, aber allgemein. Ich halte diese "magische Zahl" übrigens für einen Hoax, aber das nur am Rande.

Ich habe eine TStringDictionary , die arbeitet mit einer Hashmap, und die ist als ein Array implementiert. Wenn die Hashmap voll ist, muss ich das Array vergrößern. Ich habe mit 1.72 2/3, Fibbionacci etc. experimentiert und bin schlussendlich bei der 2 geblieben (als Vergrößerungsfaktor). 4 ist noch besser, aber so marginal, das mir da die 2 lieber ist.

Meine Anfangsgröße ist 997 (Primzahl, ist so bei Hashmaps), wobei es wirklich egal ist ob man mit 1 oder 997 anfängt. Jedenfalls bei meinen Versuchen, die 1-10 Millionen Strings in die Liste eingefügt haben.

Bis 2^31 Einträge in der Liste sind, wird diese bei einer Anfangsgröße von 997 Elementen 20x vergrößert. Ob ich beim Einfügen von 2^31 Elementen nun 30 (Anfangsgröße = 1) oder 20x vergrößere ist völlig egal: Das Laufzeitverhalten bleibt gleich, denn die 10 anfänglichen Vergrößerungen (Anfangsgröße=1, bis auf 1000 Elemente) geht einfach zu schnell und gehen in der Messung über die 1.000.000 Elemente unter.

Damit die StringDictionary auch für kleinere Mengen praktikabel ist, habe ich die Anfangsgröße doch auf 997 gesetzt. Damit kommen normale Anwendungen gänzlich ohne dynamische Vergrößerung aus.

Wenn ich dagegen mit kleineren Faktoren spiele, wird das Teil doch etwas langsamer. Also habe ich mich für 200% entschieden, was im Code auch irgendwie cooler aussieht, also (*1.72), obwohl das Geschmackssache ist.

Übrigens ist es entgegen meiner anfänglichen Meinung nicht so, das es umso schneller ist, je höher der Vergrößerungsfaktor ist. Ich hab mal die Kurve der zu Gesamtanzahl der zu verschiebenden Elemente ggü dem Vergrößerungsfaktor aufgezeichnet und das lokale Minimum liegt irgendwo bei 4-5 (sofern meine Formel stimmt).