Массив¶

Массив — это структура данных, предназначенная для хранения упорядоченного набора элементов одного типа, доступ к которым осуществляется по целочисленному индексу. Массивы являются одной из фундаментальных и наиболее распространённых структур данных в программировании, лежащей в основе многих алгоритмов и вычислительных процессов. Ключевыми характеристиками массива являются фиксированный или динамический размер (в зависимости от реализации), однородность элементов (в статически типизированных языках) и прямой доступ к любому элементу по его индексу за константное время O(1).

¶История

Концепция массива восходит к ранним этапам развития вычислительной техники. Математические основы были заложены в теориях множеств и матриц. Первые программные реализации массивов появились в языках программирования 1950-х годов, таких как FORTRAN (1957) и ALGOL (1958). В FORTRAN массивы были статическими и одномерными, что позволяло компактно хранить числовые данные. В ALGOL была введена поддержка многомерных массивов.

В языках 1960—1970-х годов, таких как C (1972), массивы стали неотъемлемой частью системного программирования. В C массив определяется как непрерывная область памяти, а имя массива трактуется как указатель на его первый элемент. Эта особенность обеспечила тесную связь массива с адресной арифметикой, что повысило производительность, но потребовало от программиста контроля над границами массива.

С развитием объектно-ориентированного программирования (C++, Java, C#) появились классы-обёртки, которые добавили управление памятью, проверку границ и динамическое изменение размера (например, std::vector в C++, ArrayList в Java, List<T> в C#). В современных скриптовых языках (Python, JavaScript, PHP) массивы стали более гибкими: они могут хранить элементы разных типов, динамически расширяться и предоставлять встроенные методы для обработки данных.

¶Классификация массивов

Массивы классифицируются по нескольким признакам:

¶По размерности

• Одномерные (векторы) — линейный набор элементов.
• Многомерные — два и более измерения (матрицы, кубы данных). Пример: двумерный массив int matrix[3][4] в C++.

¶По способу выделения памяти

• Статические — размер задаётся на этапе компиляции и не может быть изменён. Память выделяется в стеке или в сегменте данных. Например, int arr[10] в C.
• Динамические — память выделяется во время выполнения программы (в куче) и может быть перераспределена. В языках с управляемой памятью (Java, C#, Python) все массивы являются динамическими.

¶По типу элементов

• Гомогенные — все элементы имеют один тип (характерно для статически типизированных языков, например int[] в Java).
• Гетерогенные — элементы могут быть разных типов (доступно в динамически типизированных языках, например массивы array в PHP или list в Python, хотя в Python используется термин «список», а под «массивом» часто понимают модуль array с однородными данными).

¶Устройство и характеристики

В языках низкого уровня (C, C++) массив представляет собой непрерывную область памяти фиксированного размера. Элементы располагаются последовательно, начиная с базового адреса массива. Адрес i-го элемента вычисляется как базовый_адрес + i * размер_элемента. Это обеспечивает прямой доступ (O(1)), однако вставка или удаление элемента в середине массива требует сдвига всех последующих элементов, что занимает O(n) времени.

В языках высокого уровня (Java, Python, C#, JavaScript) массивы реализованы как объекты с дополнительной метаинформацией (длина, тип). Память по-прежнему выделяется непрерывно, но размер может быть изменён путём выделения нового блока и копирования данных (в случае динамических массивов).

Основные операции с массивами:

• Чтение по индексу: O(1).
• Запись по индексу: O(1).
• Вставка в конец (для динамических массивов, если есть свободное место): амортизированное O(1).
• Удаление с конца: O(1).
• Поиск значения по ключу (без хеширования): O(n) в неотсортированном массиве.
• Сортировка: O(n log n) для эффективных алгоритмов (например, быстрая сортировка).

¶Применение

Массивы используются в широком спектре прикладных и системных задач:

• Научные вычисления: матричные операции, обработка сигналов, численное моделирование.
• Графика: хранение пикселей (растровые изображения), текстур, вершин (в OpenGL и DirectX).
• Базы данных: внутреннее представление строк и индексов.
• Алгоритмы и структуры данных: реализация стеков, очередей, куч, хеш-таблиц.
• Ввод-вывод: буферы для чтения/записи данных с дисков или из сети.
• Системное программирование: таблицы страниц памяти, таблицы векторов прерываний.

¶Различия в языках программирования

¶Альтернативы и расширения

В ряде случаев вместо массивов используются другие структуры данных:

• Связные списки — эффективная вставка/удаление в середине, но медленный доступ по индексу.
• Стеки и очереди — специализированные структуры на основе массивов или списков.
• Хеш-таблицы — быстрый поиск по ключу, но неупорядоченное хранение.
• Срезы (slices) — в Go и Rust представляют собой динамическое представление участка массива.
• Разрежённые массивы — для хранения большого количества данных с несплошными индексами (например, словари).

¶Интересные факты

• В языке C имя массива в большинстве контекстов неявно преобразуется в указатель на его первый элемент. Это исключение сделано для оператора sizeof, который возвращает размер всего массива.
• В языке Java массивы являются объектами, поэтому их можно передавать по ссылке, а их длина (length) является полем, а не методом.
• В Python термин «массив» чаще относится к модулю array.array, предназначенному для однородных числовых данных, в то время как встроенный тип list является динамическим гетерогенным массивом.
• В 1978 году в языке Pascal были введены «открытые массивы» (open arrays) — массивы переменной длины, передаваемые в процедуры по значению.
• Многомерные массивы в некоторых языках (Java, C#) на самом деле являются массивами массивов, тогда как в C и C++ многомерный массив — это единый непрерывный блок памяти.

¶Источники

• Керниган Б., Ритчи Д. — «Язык программирования C», 2-е издание, 1988.
• Страуструп Б. — «Язык программирования C++», 4-е издание, 2013.
• Кормен Т., Лейзерсон Ч., Ривест Р., Штайн К. — «Алгоритмы: построение и анализ», 3-е издание, 2009.
• Арнольд К., Гослинг Дж., Холмс Д. — «Язык программирования Java», 3-е издание, 2005.
• Документация Python 3.12: «Sequence Types — list, tuple, range» (2023).
• Спецификация ECMAScript 2023: «Array Objects», раздел 22.1.