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

Question

Когда мы создаем массив, мы не можем изменить его размер; это фиксированная. Хорошо, кажется хорошим, мы можем создать новый больший массив и скопировать значения одно за другим, и это немного медленно Каково его техническое обоснование?

Answer 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

Answer 2

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

Answer 3

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

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

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

То есть вы не можете просто расширить массив, не переместив его физически.

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

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

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

Answer 4

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

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

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

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

Answer 5

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

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

Answer 6

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

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

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

Answer 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 / C ++ (3.0), Pascal (7.0), QBasic, PowerBasic и COM отладочные программы были основаны на этой архитектуре и могли работать лучше, чем это допускал Assembler.

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

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

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