C ++ tiene std :: vector y Java tiene ArrayList, y muchos otros lenguajes tienen su propia forma de matriz asignada dinámicamente. Cuando una matriz dinámica se queda sin espacio, se reasigna a un área más grande y los valores antiguos se copian en la nueva matriz. Una pregunta central para el rendimiento de una matriz de este tipo es qué tan rápido la matriz crece en tamaño. Si siempre creces lo suficiente para adaptarse al empuje actual, terminarás reasignando cada vez. Por lo tanto, tiene sentido duplicar el tamaño del arreglo o multiplicarlo por, por ejemplo, 1.5x.

¿Hay un factor de crecimiento ideal? 2x? 1.5x? Por ideal me refiero a matemáticamente justificado, mejor rendimiento de equilibrio y pérdida de memoria. Me doy cuenta de que, en teoría, dado que su aplicación podría tener cualquier distribución potencial de impulsos, esto depende en parte de la aplicación. Pero tengo curiosidad por saber si hay un valor que sea "generalmente" el mejor, o que se considere mejor dentro de alguna restricción rigurosa.

He oído que hay un documento sobre esto en alguna parte, pero no he podido encontrarlo.