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

Ответ 1

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

Нет такой вещи, как "идеальный фактор роста". Это не только теоретически зависит от приложения, но и зависит от приложения.

2 - довольно распространенный фактор роста - я уверен, что те, что используются ArrayList и List<T> в .NET. ArrayList<T> в Java использует 1.5.

EDIT: Как указывает Эрих, Dictionary<,> в .NET использует "удваивает размер, а затем увеличивается до следующего простого числа", так что хеш-значения могут быть распределены разумно между ведрами. (Я уверен, что недавно я видел документацию, предлагающую, что простые числа на самом деле не так хороши для распространения хэш-ведер, но это аргумент для другого ответа.)

Ответ 2

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

Обоснование таково:

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

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

• Начните с 16 байтов.
• Когда вам нужно больше, выделите 24 байта, затем освободите 16, оставив 16-байтовое отверстие.
• Когда вам нужно больше, выделите 36 байт, затем освободите 24, оставив 40-байтовое отверстие.
• Когда вам нужно больше, выделите 54 байта, затем освободите 36, оставив 76-байтовое отверстие.
• Когда вам нужно больше, выделите 81 байт, затем освободите 54, оставив 130-байтовое отверстие.
• Если вам нужно больше, используйте 122 байта (округление) из 130-байтового отверстия.

Ответ 3

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

На практике вам нужно что-то близкое, например 1.5.

Причина объясняется в ссылке выше - она ​​включает в себя решение уравнения x ^{n - 1}= x ^{n + 1} - x ⁿ положительное решение которого x = φ.

Ответ 4

Один из подходов при ответе на такие вопросы - просто "обмануть" и посмотреть, что делают популярные библиотеки, в предположении, что широко используемая библиотека, по крайней мере, не делает что-то ужасное.

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

Ответ 5

Скажем, вы увеличиваете размер массива на 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.

Ответ 6

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

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

Ответ 7

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

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

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

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

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

Ответ 8

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

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

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

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

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

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

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

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

Ответ 9

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

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

Ответ 10

Еще два цента

• Большинство компьютеров имеют виртуальную память! В физической памяти вы можете иметь случайные страницы повсюду, которые отображаются как одно непрерывное пространство в вашей виртуальной памяти программы. Разрешение косвенности осуществляется аппаратным обеспечением. Устранение виртуальной памяти было проблемой для 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 является хорошим дефолтом. Кроме того, это зависит от конкретного случая.