Каков идеальный темп роста для динамично выделенного массива?

I remember reading many years ago why 1.5 is preferred over two, at least as applied to C++ (this probably doesn't apply to managed languages, where the runtime system can relocate objects at will).

The reasoning is this:

1. Say you start with a 16-byte allocation.
2. When you need more, you allocate 32 bytes, then free up 16 bytes. This leaves a 16-byte hole in memory.
3. When you need more, you allocate 64 bytes, freeing up the 32 bytes. This leaves a 48-byte hole (if the 16 and 32 were adjacent).
4. When you need more, you allocate 128 bytes, freeing up the 64 bytes. This leaves a 112-byte hole (assuming all previous allocations are adjacent).
5. And so and and so forth.

The idea is that, with a 2x expansion, there is no point in time that the resulting hole is ever going to be large enough to reuse for the next allocation. Using a 1.5x allocation, we have this instead:

1. Start with 16 bytes.
2. When you need more, allocate 24 bytes, then free up the 16, leaving a 16-byte hole.
3. When you need more, allocate 36 bytes, then free up the 24, leaving a 40-byte hole.
4. When you need more, allocate 54 bytes, then free up the 36, leaving a 76-byte hole.
5. When you need more, allocate 81 bytes, then free up the 54, leaving a 130-byte hole.
6. When you need more, use 122 bytes (rounding up) from the 130-byte hole.

One approach when answering questions like this is to just "cheat" and look at what popular libraries do, under the assumption that a widely used library is, at the very least, not doing something horrible.

So just checking very quickly, Ruby (1.9.1-p129) appears to use 1.5x when appending to an array, and Python (2.6.2) uses 1.125x plus a constant (in Objects/listobject.c):

/* This over-allocates proportional to the list size, making room
 * for additional growth.  The over-allocation is mild, but is
 * enough to give linear-time amortized behavior over a long
 * sequence of appends() in the presence of a poorly-performing
 * system realloc().
 * The growth pattern is:  0, 4, 8, 16, 25, 35, 46, 58, 72, 88, ...
 */
new_allocated = (newsize >> 3) + (newsize < 9 ? 3 : 6);

/* check for integer overflow */
if (new_allocated > PY_SIZE_MAX - newsize) {
    PyErr_NoMemory();
    return -1;
} else {
    new_allocated += newsize;
}

newsize above is the number of elements in the array. Note well that newsize is added to new_allocated, so the expression with the bitshifts and ternary operator is really just calculating the over-allocation.

I agree with Jon Skeet, even my theorycrafter friend insists that this can be proven to be O(1) when setting the factor to 2x.

The ratio between cpu time and memory is different on each machine, and so the factor will vary just as much. If you have a machine with gigabytes of ram, and a slow CPU, copying the elements to a new array is a lot more expensive than on a fast machine, which might in turn have less memory. It's a question that can be answered in theory, for a uniform computer, which in real scenarios doesnt help you at all.

It really depends. Some people analyze common usage cases to find the optimal number.

I've seen 1.5x 2.0x phi x, and power of 2 used before.

Если у вас есть распределение по длинам массивов, и у вас есть служебная функция, которая говорит, насколько вы любите тратить пространство против потери времени, тогда вы определенно можете выбрать оптимальную стратегию изменения размера (и начального изменения размера).

Причина, по которой используется простое постоянное кратное, очевидно, заключается в том, что каждое добавление имеет амортизированное постоянное время. Но это не означает, что вы не можете использовать другое (большее) соотношение для небольших размеров.

В Scala вы можете переопределить loadFactor для хеш-таблиц стандартной библиотеки с помощью функции, которая смотрит на текущий размер. Как ни странно, массивы с изменяемым размером просто удваиваются, что большинство людей и делает на практике.

Я не знаю ни одного массива с удвоением (или 1.5 * ing), который действительно перехватывает ошибки памяти и в этом случае становится меньше. Похоже, что если бы у вас был один огромный массив, вы бы захотели это сделать.

Я бы добавил, что если вы достаточно долго храните массивы с изменяемым размером и предпочитаете пространство с течением времени,