Что такое массив?

Приложению погоды, которое показывает температуру за неделю, нужно семь чисел. Можно было бы завести семь отдельных переменных, monday, tuesday и так далее, но тогда никакой цикл не смог бы их обойти, а добавление восьмого дня означало бы написание нового кода. Массив собирает все семь чисел под одним именем, temperatures, в пронумерованных ячейках от 0 до 6.

Как работает массив

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

address of element i = start address + i × element size

Допустим, массив 32-битных целых чисел (по 4 байта каждое) начинается с адреса памяти 1000. Элемент 0 находится по адресу 1000, элемент 1 по адресу 1004, элемент 2 по адресу 1008, а элемент 3 по адресу 1012. Добраться до элемента 3 или до элемента 3 000 000 можно за один и тот же шаг, поэтому чтение массива по индексу называют операцией за константное время, O(1).

Модуль array в Python хранит числа именно так, поэтому арифметику можно проверить:

from array import array

scores = array("i", [90, 75, 88, 62])
print(scores.itemsize, "bytes per element")
print(len(scores) * scores.itemsize, "bytes in total")

start = 1000  # pretend the array starts at address 1000
for index in range(len(scores)):
    address = start + index * scores.itemsize
    print("scores[" + str(index) + "] =", scores[index], "at address", address)

4 bytes per element
16 bytes in total
scores[0] = 90 at address 1000
scores[1] = 75 at address 1004
scores[2] = 88 at address 1008
scores[3] = 62 at address 1012

Эта формула объясняет и то, почему большинство языков считают с 0. Индекс является смещением: сколько элементов нужно пропустить от начала. Первый элемент находится в 0 элементах от начала, поэтому его индекс равен 0, а у последнего элемента массива длины n индекс n − 1. Некоторые языки, например Lua, MATLAB, R и Fortran, начинают с 1.

Массив в Python

В большинстве программ на Python роль массива играет встроенный list. Его создают квадратными скобками, читают и меняют элементы по индексу, а длину узнают через len():

temperatures = [18, 21, 25, 23, 19]

print(temperatures[0])   # first element
print(temperatures[2])   # third element
print(temperatures[-1])  # last element
print(len(temperatures))

temperatures[1] = 22     # change one element
temperatures.append(20)  # add one at the end
print(temperatures)

18
25
19
5
[18, 22, 25, 23, 19, 20]

Отрицательный индекс считается с конца, поэтому temperatures[-1] является последним элементом. Это особенность Python; в C и Java отрицательных индексов нет.

Сколько стоят операции с массивом

Непрерывное расположение делает одни операции быстрыми, а другие медленными. Стоимость растёт вместе с n, числом элементов:

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

Обход массива в цикле

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

prices = [4.50, 12.00, 3.25, 8.75]

total = 0
for price in prices:
    total = total + price

print("Total:", total)
print("Most expensive:", max(prices))

Total: 28.5
Most expensive: 12.0

Массивы в других языках

В C у массива фиксированный размер, заданный при объявлении, и он хранит сырые значения одного типа. sizeof сообщает его размер в байтах:

int scores[5] = {90, 75, 88, 62, 100};   /* 5 × 4 bytes = 20 bytes */

Массивы в Java тоже имеют фиксированную длину, а новые элементы получают значение по умолчанию, например 0 для чисел. Если нужен массив Java, который растёт, используют ArrayList:

int[] scores = new int[5];   // five elements, all 0
scores[0] = 90;

Массивы в JavaScript свободно растут и уменьшаются и могут смешивать типы, как в [1, "two", true].

Растущие массивы, такие как list в Python, ArrayList в Java и std::vector в C++, называют динамическими массивами. Они резервируют дополнительное место в конце. Когда это место заканчивается, они выделяют блок побольше, копируют туда все элементы и продолжают работу. Копирование происходит достаточно редко, поэтому добавление в конец в среднем остаётся быстрым.

Массив может хранить и другие массивы. grid[row][col] читает одну ячейку двумерного массива: такое расположение используют игровые поля, электронные таблицы и изображения. Руководство по многомерным массивам в C показывает, как они лежат в памяти.

Частые ошибки

Ошибка на единицу. У массива из 3 элементов индексы 0, 1 и 2, поэтому индекс 3 находится за концом. Python останавливается с ошибкой:

scores = [90, 75, 88]
print(scores[3])

IndexError: list index out of range

Java выбрасывает ArrayIndexOutOfBoundsException, а JavaScript молча возвращает undefined. C вообще ничего не проверяет: чтение за концом массива является неопределённым поведением, которое может вернуть мусор или обрушить программу с ошибкой сегментации.

Копирование присваиванием. В Python, Java и JavaScript b = a не копирует массив; оба имени ссылаются на один и тот же массив, поэтому изменение b меняет и a. Для настоящей копии используй a.copy() в Python или [...a] в JavaScript. Почему так, объясняет страница о переменной.

Что изучить дальше

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