Массивы под капотом: память, адресация и сложность операций

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

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

Каждый элемент массива имеет индекс — порядковый номер. В большинстве языков программирования индексация начинается с 0.

Массив в информатике — это тип данных, в котором хранится упорядоченный набор однотипных элементов.

Можно выделить одномерные и многомерные массивы.

Одномерные — это просто ряд пронумерованных значений.

Многомерные — матрица: каждое из значений массива само является массивом. Соответственно, доступ к элементу возможен по двум индексам — строки и столбца

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

Массив помогает:

• хранить несколько однотипных значений внутри одной переменной;

• структурировать и упорядочивать информацию;

• легко получать доступ к каждому элементу;

• быстро применять одинаковые действия ко всем элементам массива;

• экономить память и поддерживать высокую скорость выполнения действий.

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

Детали:

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

2. При создании массива компьютер выделяет непрерывный участок памяти и складывает в него элементы один за другим.

3. Так как все элементы принадлежат одному типу, они занимают одинаковый объём памяти. Допустим, в нашей архитектуре числа с плавающей запятой весят 4 байта. Компьютер умножает вес одного элемента на длину списка и получает количество памяти, которое ему нужно зарезервировать:

4. Теперь становится понятно, почему для классических массивов нужно заранее указывать тип данных и количество элементов:

   • Если компьютер не знает длину массива, то он не понимает, сколько памяти нужно под него выделить.

   • Если компьютер не знает тип данных, то он не понимает, сколько памяти нужно выделять под каждый элемент и на сколько ячеек смещаться при поиске элемента по индексу.

5. адрес определенного индекcа вычисляется по формуле - начальный адрес массива + индекс * число ячеек, которые занимает один элемент

6. по сути динамический массив — это тот же статический, но способный пересоздаваться с другой длиной.

7. массивы бывают -Однородные и гетерогенные

8. В гетерогенных массивах могут быть элементы разных типов

9. На самом деле гетерогенные массивы хранят в себе не сами данные, а ссылку на них.

10. гетерогенный массив практически не отличается от гомогенного. Он тоже хранит в себе один тип данных — ссылочный.

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

Сложность операций с Массивом:

1. Вставка в начало или середину массива имеет O(n) линейную временную сложность

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

3. Удаление из начала Массива имеет линейную сложность, так как нужно сдвинуть все элементы

4. Если не имеет значения порядок элементов то можно свапнуть первый и последний элемент и удалить последний, тогда сложность будет константная

5. удаление из конца массива имеет константную сложность

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

Детали:

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

2. При создании массива компьютер выделяет непрерывный участок памяти и складывает в него элементы один за другим.

3. Так как все элементы принадлежат одному типу, они занимают одинаковый объём памяти. Допустим, в нашей архитектуре числа с плавающей запятой весят 4 байта. Компьютер умножает вес одного элемента на длину списка и получает количество памяти, которое ему нужно зарезервировать:

4. Теперь становится понятно, почему для классических массивов нужно заранее указывать тип данных и количество элементов:

   • Если компьютер не знает длину массива, то он не понимает, сколько памяти нужно под него выделить.

   • Если компьютер не знает тип данных, то он не понимает, сколько памяти нужно выделять под каждый элемент и на сколько ячеек смещаться при поиске элемента по индексу.

5. адрес определенного индека вычесляется по формуе - начальный адрес массива + индекс * число ячеек, которые занимает один элемент

6. по сути динамический массив — это тот же статический, но способный пересоздаваться с другой длиной.

7. массивы бывают -Однородные и гетерогенные

8. В гетерогенных массивах могут быть элементы разных типов

9. На самом деле гетерогенные массивы хранят в себе не сами данные, а ссылку на них.

10. гетерогенный массив практически не отличается от гомогенного. Он тоже хранит в себе один тип данных — ссылочный.

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

Асимптотическая сложность операций с массивом:

1. Вставка в начало или середину массива имеет O(n) линейную временную сложность

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

3. Удаление из начала Массива имеет линейную сложность, так как нужно сдвинуть все элементы

4. Если не имеет значения порядок элементов то можно свапнуть первый и последний элемент и удалить последний, тогда сложность будет константная

5. удаление из конца массива имеет константную сложность

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