Was ist die ideale Wachstumsrate für ein dynamisch zugewiesenes Array?

C ++ hat std :: vector und Java hat ArrayList, und viele andere Sprachen haben ihre eigene Form eines dynamisch zugewiesenen Arrays. Wenn einem dynamischen Array der Speicherplatz ausgeht, wird er in einem größeren Bereich neu zugeordnet und die alten Werte werden in das neue Array kopiert. Eine zentrale Frage für die Leistung eines solchen Arrays ist, wie schnell die Größe des Arrays zunimmt. Wenn Sie immer nur groß genug werden, um dem aktuellen Push gerecht zu werden, werden Sie sich jedes Mal neu zuteilen. Es ist also sinnvoll, die Array-Größe zu verdoppeln oder sie beispielsweise mit dem 1,5-fachen zu multiplizieren.

Gibt es einen idealen Wachstumsfaktor? 2x? 1,5x? Mit Ideal meine ich mathematisch gerechtfertigte, optimale Balance zwischen Leistung und verschwendetem Speicher. Mir ist klar, dass Ihre Anwendung theoretisch von der möglichen Verteilung der Pushs abhängig ist. Aber ich bin neugierig zu wissen, ob es einen Wert gibt, der "normalerweise" am besten ist oder unter gewissen strengen Bedingungen als am besten angesehen wird.

Ich habe gehört, es gibt irgendwo eine Zeitung darüber, aber ich konnte sie nicht finden.

Antworten auf die Frage(10)

Ihre Antwort auf die Frage