Какова идеальная скорость роста для динамически размещаемого массива?

C ++ имеет std :: vector, а Java имеет ArrayList, и многие другие языки имеют свою собственную форму динамически размещаемого массива. Когда динамическому массиву не хватает места, он перераспределяется в большую область, а старые значения копируются в новый массив. Главный вопрос производительности такого массива заключается в том, насколько быстро увеличивается размер массива. Если вы всегда становитесь достаточно большими, чтобы соответствовать текущему толчку, вы будете в конечном итоге перераспределяться каждый раз. Поэтому имеет смысл удвоить размер массива или умножить его, скажем, в 1,5 раза.

Есть ли идеальный фактор роста? 2x? 1.5x? Под идеалом я подразумеваю математически обоснованную, лучшую производительность балансировки и потерянную память. Я понимаю, что теоретически, учитывая, что ваше приложение может иметь какое-либо потенциальное распределение толчков, это зависит от приложения. Но мне любопытно знать, существует ли значение, которое обычно является "значительным". лучше или считается лучшим в рамках строгих ограничений.

Я слышал, что где-то есть статья по этому вопросу, но я не смог ее найти.

Ответы на вопрос(10)

Ваш ответ на вопрос