Почему массивы не расширяются?

Ответ 1

В этом вопросе не упоминался язык, поэтому я собираюсь выбрать массивы на основе C для моего ответа.

Массивы выделяются как один кусок памяти. Растущий массив проблематичен, потому что единственный способ сделать это правильно - это вырастить его в конце. Для роста размера N в конце массива должно быть не менее N свободных байтов до следующего выделенного адреса.

Поддержка такого типа выделения требует, чтобы распределения распределялись по виртуальному адресному пространству. Это и устраняет преимущества, связанные с распределением памяти ближе друг к другу и служит для увеличения фрагментации. Это бросается в глаза большинству менеджеров памяти, которые пытаются объединить память и уменьшить фрагментацию.

Выделение нового массива в месте в памяти с достаточным пространством и копирование массива просто не является вариантом в качестве общего решения. Причина в том, что предыдущее местоположение массива видимо для потребителей через указатели.

int* array = malloc(int*someSize);
int* pointer1 = &(arr[2]);
growArray(&array, 12);  // Can't move because pointer1 knows the address of the array

Ответ 2

Массив у его корней является непрерывным "массивом" памяти. Другие данные могут занимать данные до и после этой области памяти, поэтому они не могут быть динамически изменены без выделения новой, другой области памяти, которая соответствует новому большему размеру.

Ответ 3

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

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

В любом случае, когда вы выделяете больше памяти, вы хотите поместить новую память в конец массива - иначе вы бы сегментировали свою память с помощью дыры - зачем вы это делаете?

Поэтому вы не можете просто расширить массив без физического перемещения.

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

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

Многие языки просто переносят массивы в виде коллекций, которые допускают такую ​​функциональность. Например, Java Vector/ArrayList автоматически перераспределит для вас память. Связанный список фактически просто выделяет один элемент каждый раз указателем на следующий. Делает это очень быстро, чтобы добавлять элементы, но очень медленно перейти к элементу 5000 (вы должны прочитать каждый отдельный элемент, тогда как элемент 1 считывания массива так же быстро, как и элемент 5000)

Ответ 4

Это зависит от языка.

В C (и подобных языках, таких как Java), когда вы объявили массив типа int ary[10], система выделила достаточно памяти для хранения десяти целых чисел назад. Расширение было непростым, потому что система не выделяла лишнее пространство (поскольку оно не имеет понятия, хотите ли вы расширить его или насколько) и память, которая появилась сразу после того, как массив, вероятно, использовался чем-то другим. Таким образом, единственный способ получить более крупный массив - выделить новый блок памяти, который будет содержать расширенный массив, затем скопировать старое содержимое и добавить новые элементы.

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

Другой способ - использовать язык более высокого уровня с расширенными массивами. Например, Ruby позволяет добавлять дополнительные элементы в массив без необходимости объявлять память или копировать содержимое массива.

Ответ 5

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

В большинстве случаев array фиксированы - абстракция (как-то) низкого уровня - и lists или collections построена поверх массивов и знает, как динамически изменяют размеры.

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

Ответ 6

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

Например, на языке программирования Curl существует тип FastArray, размер которого и максимальный размер. Максимальный размер определяет максимальный размер массива и определяет, сколько памяти будет выделено для массива. Существует более общий тип массива, который использует FastArray как свою базовую реализацию и заменяет экземпляр FastArray, если массив должен быть расширен за максимальный размер базового FastArray.

Ответ 7

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

Итак, примерно так выглядит (Borland Turbo Assembler):

.DATA
    myStringVariable   DB   "Hello world!", 13, 10
    myArrayVariable    DW   "                    " 'Reserving 20 bytes in memory (in a row)

.CODE

    MOV AX, @DATA
    MOV DS, AX
    ' ...

Затем, как только сегмент .DATA был ограничен, его нельзя было изменить, так как сегмент .CODE(CS) начинался с нескольких байтов.

Итак, если бы массив был расширяемым, например, коллекции были в .NET, данные перезаписали бы код, вызывая сбой программы и т.д.

C/С++ (3.0), Pascal (7.0), QBasic, PowerBasic и COM-отладки были основаны на этой архитектуре и могли делать все, что было лучше, чем позволял Ассемблер.

Сегодня, с более гибкой технологией, мы теперь можем, по мере необходимости, распределять адреса памяти "на лету" и сохранять ссылку на них только с одной переменной, поэтому массивы становятся расширяемыми вместе с коллекцией. Но есть некоторая ситуация, когда у вас есть точное количество байтов, чтобы уважать, например, сетевые пакеты и т.д., Например, где массивы по-прежнему полезны. Другим примером является хранение изображений в базе данных. Вы точно знаете, что большая длина в байтах - это изображение, поэтому вы можете сохранить его в байтовом массиве (Byte []).

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

Надеюсь, это поможет! =)