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

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

рассуждение таково:

1. скажем, вы начинаете с 16-байтового распределения.
2. когда вам нужно больше, вы выделяете 32 байта, а затем освобождаете 16 байт. Это оставляет 16-байтовое отверстие в памяти.
3. когда вам нужно больше, вы выделяете 64 байта, освобождение 32 байт. Это оставляет 48-байтовое отверстие (если 16 и 32 были смежными).
4. когда вам нужно больше, вы выделяете 128 байт, освобождая 64 байта. Это оставляет 112-байтовое отверстие (предполагая, что все предыдущие распределения смежны).
5. и так далее и тому подобное.

идея заключается в том, что при расширении 2x нет момента времени, когда полученное отверстие когда-либо будет достаточно большим для повторного использования для следующего распределения. Использование выделения 1.5 x, у нас есть это вместо:

1. начните с 16 байт.
2. когда вам нужно больше, выделите 24 байта, а затем освободите 16, оставив 16-байтовое отверстие.
3. когда вам нужно больше, выделите 36 байт, а затем освободите 24, оставив 40-байтовое отверстие.
4. когда вам нужно больше, выделите 54 байта, а затем освободите 36, оставив 76-байтовое отверстие.
5. когда вам нужно больше, выделите 81 байт, а затем освободите 54, оставив 130-байтовое отверстие.
6. когда вы нужно больше, использовать 122 байта (округление) из 130-байтового отверстия.

в идеале (в пределе n→ ∞),это золотой пропорции: ϕ = 1.618...

на практике, вы хотите что-то близко, как 1.5.

причина в том, что вы хотите иметь возможность повторно использовать старые блоки памяти, чтобы воспользоваться кэшированием и избежать постоянно делать ОС дать вам больше страниц памяти. Уравнение, которое вы решите, чтобы убедиться, что это сводится к x^{n - 1} - 1 = x^{n + 1} -xⁿ, чье решение приближается x = ϕ для больших n.

так что просто проверка очень быстро, Ruby (1.9.1-p129), по-видимому, использует 1.5 x при добавлении к массиву, а Python (2.6.2) использует 1.125 x плюс константа (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 выше-количество элементов в массиве. Отмечать Ну что newsize добавляется new_allocated, поэтому выражение с битовым сдвигом и тернарным оператором действительно просто вычисляет избыточное распределение.

допустим, вы увеличиваете размер массива на x. Поэтому предположим, что вы начинаете с размера T. В следующий раз, когда вы вырастите массив его размер будет T*x. Тогда это будет T*x^2 и так далее.

если ваша цель состоит в том, чтобы иметь возможность повторно использовать память, которая была создана ранее, то вы хотите, чтобы убедиться, что новая память вы выделяете меньше, чем сумма предыдущей памяти вы освободили. Поэтому мы имеем такое неравенство:

T*x^n <= T + T*x + T*x^2 + ... + T*x^(n-2)

мы можем удалить T из обоих стороны. Итак, мы получаем следующее:

x^n <= 1 + x + x^2 + ... + x^(n-2)

неофициально мы говорим, что в nth выделение, мы хотим, чтобы наша вся ранее освобожденная память была больше или равна потребности в памяти при N-М выделении, чтобы мы могли повторно использовать ранее освобожденную память.

например, если мы хотим быть в состоянии сделать это на 3-м шаге (т. е. n=3), то есть

x^3 <= 1 + x 

это уравнение верно для всех x таких, что 0 < x <= 1.3 (грубо)

смотрите, что x мы получаем для разных n ниже:

n  maximum-x (roughly)

3  1.3

4  1.4

5  1.53

6  1.57

7  1.59

22 1.61

обратите внимание, что фактор роста должен быть меньше, чем 2 С x^n > x^(n-2) + ... + x^2 + x + 1 for all x>=2.

Это действительно зависит. Некоторые люди анализируют общие случаи использования, чтобы найти оптимальное количество.

Я видел 1.5 x 2.0 x phi x, и мощность 2 используется раньше.

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

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

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

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

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

Я согласен с Джоном скитом, даже мой друг-теоретик настаивает на том, что это может быть доказано O(1) при установке коэффициента в 2x.

соотношение между временем процессора и памятью отличается на каждой машине, и поэтому фактор будет меняться так же сильно. Если у вас есть машина с гигабайтами оперативной памяти и медленным процессором, копирование элементов в новый массив намного дороже, чем на быстрой машине, которая, в свою очередь, может иметь меньше памяти. Это вопрос, на который можно ответить теоретически, ибо единый компьютер, который в реальных сценариях вам совсем не поможет.

Я знаю, это старый вопрос, но есть несколько вещей, которые все, кажется, отсутствует.

во-первых, это умножение на 2: Размер что-нибудь между 1 и 2: int(float(size) * x), где x-число, * - математика с плавающей запятой, и процессор должен запускать дополнительные инструкции для приведения между float и int. Другими словами, на машинном уровне удвоение занимает одну очень быструю инструкцию, чтобы найти новый размер. Умножение на что-то между 1 и 2 требует по крайней мере одна инструкция для приведения размера к поплавку, одна инструкция для умножения (которая является умножением с плавающей точкой, поэтому, вероятно, требуется по крайней мере в два раза больше циклов, если не в 4 или даже в 8 раз больше) и одна инструкция для возврата к int, и это предполагает, что ваша платформа может выполнять математику с плавающей точкой на регистрах общего назначения, вместо того, чтобы требовать использования специальных регистров. Короче говоря, вы должны ожидать математику для каждого распределения потребуется как минимум в 10 раз больше времени, чем простой сдвиг влево. Если вы копируете много данных во время перераспределения, это может не иметь большого значения.

во-вторых, и, вероятно, большой кикер: все, кажется, предполагают, что освобождаемая память является как смежной с самой собой, так и смежной с вновь выделенной памятью. Если вы не предварительно выделяете всю память самостоятельно, а затем используете ее в качестве пула, это почти конечно, не тот случай. ОС иногда в конечном итоге это делается, но большую часть времени будет достаточно фрагментации свободного пространства, чтобы любая половина достойной системы управления памятью смогла найти небольшое отверстие, где ваша память просто поместится. Как только вы доберетесь до действительно битных кусков, вы, скорее всего, получите непрерывные куски, но к тому времени ваши распределения достаточно велики, чтобы вы не делали их достаточно часто, чтобы это имело значение. Короче, это забавно представить, что использование некоторого идеального числа позволит наиболее эффективно использовать свободное пространство памяти, но на самом деле это не произойдет, если ваша программа не работает на голом металле (как и в том, что под ней нет ОС, принимающей все решения).

мой ответ на вопрос? Нет, идеального числа не существует. Это настолько специфическое приложение, что никто даже не пытается. Если ваша цель-идеальное использование памяти, вам в значительной степени не повезло. Для представления, более менее частый распределения лучше, но если бы мы пошли только с этим, мы могли бы умножить на 4 или даже 8! Конечно, когда Firefox переходит от использования 1GB к 8GB в одном кадре, люди будут жаловаться, так что это даже не имеет смысла. Вот некоторые эмпирические правила, по которым я бы пошел:

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

Не переусердствуйте. Если вы просто потратили 4 часа, пытаясь понять, как сделать то, что уже было сделано, вы просто потратили свое время. Совершенно честно, если бы был лучший вариант, чем *2, это было бы сделано в векторном классе C++ (и во многих других местах) десятилетия назад.

наконец, если вы действительно хотите оптимизировать, не парься мелочь. Теперь дни, никто не заботится о 4KB памяти впустую, если они не работают на встроенных системах. Когда вы получаете до 1 ГБ объектов, которые находятся между 1 МБ и 10 МБ каждый, удвоение, вероятно, слишком много (я имею в виду, что между 100 и 1000 объектов). Если вы можете оценить ожидаемую скорость расширения, вы можете выровнять ее до линейной скорости роста в определенной точке. Если вы ожидаете около 10 объектов в минуту, то растет на 5 до 10 размеров объектов за шаг (один раз в 30 секунд до минута), вероятно, в порядке.

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

еще два цента

• большинство компьютеров имеют виртуальную память! В физической памяти вы можете иметь случайные страницы везде, которые отображаются как единое непрерывное пространство в виртуальной памяти вашей программы. Разрешение косвенности выполняется аппаратным обеспечением. Исчерпание виртуальной памяти проблема на 32-битных системах, но это действительно не проблема. Так что заполнение дыре больше не является проблемой (за исключением особых условиях). Начиная С Windows 7 даже Microsoft поддерживает 64 бит без дополнительных усилий. @ 2011
• O (1) достигается с любым r > 1 фактором. Же математическое доказательство работает не только для 2 в качестве параметра.
• r = 1.5 можно рассчитать с помощью old*3/2 таким образом, нет необходимости в операциях с плавающей запятой. (Я говорю /2 потому что компиляторы заменят его битовым сдвигом в сгенерированном коде сборки, если сочтут нужным.)
• MSVC пошел за r = 1.5, так что нет по крайней мере, один крупный компилятор, который не использует 2 в качестве отношения.

Как упоминалось кем-то 2 чувствует себя лучше, чем 8. А также 2 чувствует себя лучше, чем 1.1.

Я чувствую, что 1.5-это хороший дефолт. Кроме того, это зависит от конкретного случая.