Массив — один из самых простых и в то же время полезных типов данных. По сути это упорядоченная коллекция элементов одного типа, расположенная в памяти подряд. Такое расположение делает массивы быстрыми для доступа по индексу и предсказуемыми по расходу памяти.
Ключевые свойства
- Прямой доступ к элементу по индексу. Чтение или запись по индексу выполняются за постоянное время.
- Фиксированный или динамический размер. В разных языках массивы ведут себя по-разному: в C размер фиксирован, в Java массив тоже фиксирован, а списки Python реализованы как динамические массивы.
- Элементы одного типа. Это упрощает адресацию и арифметику указателей.
- Хорошая локальность памяти. Эффективно используются кеши процессора.
Простые примеры
Ниже — минимальные примеры в трёх популярных языках.
// C: статический массив
int a[5] = {1, 2, 3, 4, 5};
printf("%dn", a[2]); // 3
// Java: массив фиксированного размера
int[] a = {1, 2, 3, 4, 5};
System.out.println(a[2]); // 3
# Python: список, реализующий динамический массив
a = [1, 2, 3, 4, 5]
print(a[2]) # 3
Операции и их сложности
Важно знать временные характеристики основных операций:
- Доступ по индексу: O(1).
- Поиск без сортировки: O(n).
- Вставка или удаление в середине: O(n) из‑за сдвигов.
- Добавление в конец у динамического массива: амортизированно O(1) при увеличении ёмкости путём удвоения.
Динамические массивы: как это работает
Чтобы избежать постоянного перераспределения при добавлении элементов, динамические массивы резервируют чуть больше места, чем нужно. При переполнении выделяется новый блок в два раза больше, и данные копируются. Копирование дорогое, но происходит редко, поэтому средняя стоимость добавления низкая.
Многомерные массивы
Многомерные массивы — просто массивы массивов. Важный момент: порядок хранения. C использует по строкам, Fortran — по столбцам. От этого зависит производительность при последовательном доступе.
Когда выбирать массив
Выбирайте массив если нужны быстрые случайные обращения и предсказуемая структура памяти. Если часто вставляете и удаляете элементы в произвольных местах, лучше рассмотреть другие структуры: двусвязные списки, деревья или специализированные контейнеры.
Плюсы и минусы
- Плюсы: простота, скорость доступа, эффективная работа с кешем.
- Минусы: дорогие операции вставки/удаления в середине, ограничение по гомогенности типов и размеру (в статических реализациях).
Практические советы
- Если нужно часто добавлять элементы — используйте динамические массивы или заранее выделяйте запас.
- Для крупномасштабных вычислений учитывайте выравнивание и порядок обхода, чтобы уменьшать промахи кеша.
- При работе с многомерными массивами выбирайте порядок итерации в соответствии с тем, как данные расположены в памяти.
Короткая сводка
Массивы — базовый инструмент для хранения упорядоченных данных. Они просты в понимании, быстры для доступа и эффективны в плане памяти. Зная их ограничения и специфику реализации в вашем языке, можно принимать осознанные архитектурные решения.
