В информатике массив — это структура данных, состоящая из набора элементов ( значений или переменных ) одинакового размера памяти, каждый из которых идентифицируется по крайней мере одним индексом массива или ключом . Массив хранится таким образом, что положение каждого элемента может быть вычислено из его индексного кортежа с помощью математической формулы. [1] [2] [3] Простейшим типом структуры данных является линейный массив, также называемый одномерным массивом.
Например, массив из десяти 32-битных (4-байтовых) целочисленных переменных с индексами от 0 до 9 может храниться как десять слов по адресам памяти 2000, 2004, 2008, ..., 2036 (в шестнадцатеричном формате : 0x7D0, 0x7D4, 0x7D8, ..., 0x7F4), так что элемент с индексом i имеет адрес 2000 + ( i × 4). [4]
Адрес памяти первого элемента массива называется первым адресом, основным адресом или базовым адресом.
Поскольку математическое понятие матрицы может быть представлено как двумерная сетка, двумерные массивы также иногда называют «матрицами». В некоторых случаях термин «вектор» используется в вычислениях для обозначения массива, хотя кортежи, а не векторы, являются более математически правильным эквивалентом. Таблицы часто реализуются в виде массивов, особенно таблицы поиска ; слово «таблица» иногда используется как синоним массива.
Массивы являются одними из старейших и важнейших структур данных и используются почти каждой программой. Они также используются для реализации многих других структур данных, таких как списки и строки . Они эффективно используют логику адресации компьютеров. В большинстве современных компьютеров и многих внешних запоминающих устройствах память представляет собой одномерный массив слов, индексы которых являются их адресами. Процессоры , особенно векторные процессоры , часто оптимизированы для операций с массивами.
Массивы полезны в основном потому, что индексы элементов могут быть вычислены во время выполнения . Помимо прочего, эта функция позволяет одному итеративному оператору обрабатывать произвольное количество элементов массива. По этой причине элементы структуры данных массива должны иметь одинаковый размер и должны использовать одинаковое представление данных. Набор допустимых индексных кортежей и адреса элементов (и, следовательно, формула адресации элементов) обычно, [3] [5] , но не всегда, [2] фиксируются во время использования массива.
Термин «массив» может также относиться к типу данных массива , виду типа данных , предоставляемому большинством языков программирования высокого уровня , который состоит из набора значений или переменных, которые могут быть выбраны одним или несколькими индексами, вычисляемыми во время выполнения. Типы массивов часто реализуются с помощью структур массивов; однако в некоторых языках они могут быть реализованы с помощью хэш-таблиц , связанных списков , деревьев поиска или других структур данных.
Этот термин также используется, особенно при описании алгоритмов , для обозначения ассоциативного массива или «абстрактного массива», теоретической модели компьютерной науки ( абстрактного типа данных или АТД), предназначенной для описания основных свойств массивов.
Первые цифровые компьютеры использовали программирование на машинном языке для настройки и доступа к структурам массивов для таблиц данных, векторных и матричных вычислений и для многих других целей. Джон фон Нейман написал первую программу сортировки массивов ( сортировка слиянием ) в 1945 году во время создания первого компьютера с хранимой программой . [6] Индексация массивов изначально выполнялась с помощью самомодифицирующегося кода , а позднее с использованием индексных регистров и косвенной адресации . Некоторые мэйнфреймы, разработанные в 1960-х годах, такие как Burroughs B5000 и его последователи, использовали сегментацию памяти для выполнения проверки границ индекса на аппаратном уровне. [7]
Языки ассемблера обычно не имеют специальной поддержки массивов, кроме той, которую предоставляет сама машина. Самые ранние языки программирования высокого уровня, включая FORTRAN (1957), Lisp (1958), COBOL (1960) и ALGOL 60 (1960), имели поддержку многомерных массивов, как и C (1972). В C++ (1983) существуют шаблоны классов для многомерных массивов, размерность которых фиксирована во время выполнения [3] [5], а также для гибких во время выполнения массивов. [2]
Массивы используются для реализации математических векторов и матриц , а также других видов прямоугольных таблиц. Многие базы данных , как маленькие, так и большие, состоят из (или включают) одномерных массивов, элементами которых являются записи .
Массивы используются для реализации других структур данных, таких как списки, кучи , хэш-таблицы , деки , очереди , стеки , строки и VLists. Реализации других структур данных на основе массивов часто просты и эффективны с точки зрения пространства ( неявные структуры данных ), требуют небольших накладных расходов , но могут иметь низкую сложность пространства, особенно при модификации, по сравнению со структурами данных на основе деревьев (сравните отсортированный массив с деревом поиска ).
Иногда один или несколько больших массивов используются для эмуляции динамического распределения памяти в программе , в частности, распределения пула памяти . Исторически это иногда было единственным способом переносимого распределения «динамической памяти».
Массивы могут использоваться для определения частичного или полного потока управления в программах, как компактная альтернатива (иначе повторяющимся) множественным IFоператорам. Они известны в этом контексте как таблицы управления и используются в сочетании со специально созданным интерпретатором, поток управления которого изменяется в соответствии со значениями, содержащимися в массиве. Массив может содержать указатели подпрограмм (или относительные номера подпрограмм, на которые могут воздействовать операторы SWITCH ), которые направляют путь выполнения.
Когда объекты данных хранятся в массиве, отдельные объекты выбираются по индексу, который обычно является неотрицательным скалярным целым числом . Индексы также называются индексами. Индекс сопоставляет значение массива с хранимым объектом.
Существует три способа индексации элементов массива:
Использование индексации с нулевой базой является выбором дизайна многих влиятельных языков программирования, включая C , Java и Lisp . Это приводит к более простой реализации, где индекс ссылается на смещение от начальной позиции массива, поэтому первый элемент имеет смещение, равное нулю.
Массивы могут иметь несколько измерений, поэтому не редкость получить доступ к массиву с помощью нескольких индексов. Например, двумерный массив Aс тремя строками и четырьмя столбцами может предоставить доступ к элементу во 2-й строке и 4-м столбце с помощью выражения A[1][3]в случае системы индексации с нулевой базой. Таким образом, для двумерного массива используются два индекса, для трехмерного массива — три, а для n -мерного массива — n .
Число индексов, необходимых для указания элемента, называется размерностью, размерностью или рангом массива.
В стандартных массивах каждый индекс ограничен определенным диапазоном последовательных целых чисел (или последовательных значений некоторого перечислимого типа ), а адрес элемента вычисляется по «линейной» формуле по индексам.
Одномерный массив (или массив с одним измерением) — это тип линейного массива. Доступ к его элементам осуществляется с помощью одного индекса, который может представлять индекс строки или столбца.
В качестве примера рассмотрим декларацию C int anArrayName[10];, которая объявляет одномерный массив из десяти целых чисел. Здесь массив может хранить десять элементов типа int. Этот массив имеет индексы, начинающиеся от нуля до девяти. Например, выражения anArrayName[0]и anArrayName[9]являются первым и последним элементами соответственно.
Для вектора с линейной адресацией элемент с индексом i расположен по адресу B + c · i , где B — фиксированный базовый адрес , а c — фиксированная константа, иногда называемая приращением адреса или шагом .
Если допустимые индексы элементов начинаются с 0, константа B — это просто адрес первого элемента массива. По этой причине язык программирования C определяет, что индексы массива всегда начинаются с 0; и многие программисты будут называть этот элемент « нулевым », а не «первым».
Однако можно выбрать индекс первого элемента, выбрав соответствующий базовый адрес B. Например, если массив имеет пять элементов, проиндексированных от 1 до 5, и базовый адрес B заменен на B + 30 c , то индексы этих же элементов будут от 31 до 35. Если нумерация не начинается с 0, константа B может не быть адресом какого-либо элемента.
Для многомерного массива элемент с индексами i , j будет иметь адрес B + c · i + d · j , где коэффициенты c и d являются приращениями адреса строки и столбца соответственно.
В более общем случае, в k -мерном массиве адрес элемента с индексами i 1 , i 2 , ..., i k равен
Например: int a[2][3];
Это означает, что массив a имеет 2 строки и 3 столбца, и массив имеет целочисленный тип. Здесь мы можем хранить 6 элементов, они будут храниться линейно, но начиная с первой строки линейно, а затем продолжая второй строкой. Вышеуказанный массив будет храниться как a 11 , a 12 , a 13 , a 21 , a 22 , a 23 .
Эта формула требует только k умножений и k сложений для любого массива, который может поместиться в памяти. Более того, если какой-либо коэффициент является фиксированной степенью 2, умножение можно заменить сдвигом битов .
Коэффициенты c k должны быть выбраны таким образом, чтобы каждый допустимый индексный кортеж соответствовал адресу отдельного элемента.
Если минимально допустимое значение для каждого индекса равно 0, то B — это адрес элемента, все индексы которого равны нулю. Как и в одномерном случае, индексы элементов можно изменить, изменив базовый адрес B. Таким образом, если двумерный массив имеет строки и столбцы, проиндексированные от 1 до 10 и от 1 до 20 соответственно, то замена B на B + c 1 − 3 c 2 приведет к их перенумерации от 0 до 9 и от 4 до 23 соответственно. Используя эту возможность, некоторые языки (например, FORTRAN 77) указывают, что индексы массива начинаются с 1, как в математической традиции, в то время как другие языки (например, Fortran 90, Pascal и Algol) позволяют пользователю выбирать минимальное значение для каждого индекса.
Формула адресации полностью определяется измерением d , базовым адресом B и приращениями c 1 , c 2 , ..., c k . Часто бывает полезно упаковать эти параметры в запись, называемую дескриптором массива, вектором шага или вектором dope . [2] [3] Размер каждого элемента, а также минимальное и максимальное значения, допустимые для каждого индекса, также могут быть включены в вектор dope. Вектор dope является полным дескриптором для массива и удобным способом передачи массивов в качестве аргументов процедурам . Многие полезные операции по нарезке массива (такие как выбор подмассива, обмен индексами или изменение направления индексов) могут быть выполнены очень эффективно путем манипулирования вектором dope . [2]
Часто коэффициенты выбираются так, чтобы элементы занимали непрерывную область памяти. Однако это не обязательно. Даже если массивы всегда создаются с непрерывными элементами, некоторые операции по нарезке массивов могут создавать из них ненепрерывные подмассивы.
Существуют два систематических компактных макета для двумерного массива. Например, рассмотрим матрицу
В компоновке с приоритетом строк (принятой в языке C для статически объявленных массивов) элементы в каждой строке хранятся в последовательных позициях, и все элементы строки имеют меньший адрес, чем любой из элементов последовательной строки:
В столбцовом порядке (традиционно используемом в Фортране) элементы в каждом столбце располагаются в памяти последовательно, и все элементы столбца имеют меньший адрес, чем любой из элементов последовательного столбца:
Для массивов с тремя и более индексами "порядок по строкам" помещает в последовательные позиции любые два элемента, индексные кортежи которых отличаются только на единицу в последнем индексе. "Порядок по столбцам" аналогичен в отношении первого индекса.
В системах, использующих кэш процессора или виртуальную память , сканирование массива происходит намного быстрее, если последовательные элементы хранятся в последовательных позициях в памяти, а не разбросаны. Это известно как пространственная локальность, которая является типом локальности ссылки . Многие алгоритмы, использующие многомерные массивы, будут сканировать их в предсказуемом порядке. Программист (или сложный компилятор) может использовать эту информацию для выбора между строковой или столбцовой компоновкой для каждого массива. Например, при вычислении произведения A · B двух матриц было бы лучше хранить A в строковом порядке, а B в столбцовом порядке.
Статические массивы имеют фиксированный размер при создании и, следовательно, не позволяют вставлять или удалять элементы. Однако, выделяя новый массив и копируя в него содержимое старого массива, можно эффективно реализовать динамическую версию массива; см. динамический массив . Если эта операция выполняется нечасто, вставки в конец массива требуют только амортизированного постоянного времени.
Некоторые структуры данных массива не перераспределяют память, но сохраняют счетчик количества используемых элементов массива, называемый счетчиком или размером. Это фактически делает массив динамическим массивом с фиксированным максимальным размером или емкостью; строки Pascal являются примерами этого.
Иногда используются более сложные (нелинейные) формулы. Например, для компактного двумерного треугольного массива формула адресации представляет собой полином степени 2.
И store , и select занимают (детерминированный худший случай) постоянное время . Массивы занимают линейное ( O ( n )) пространство в количестве элементов n , которые они содержат.
В массиве с размером элемента k и на машине с размером строки кэша B байт итерация по массиву из n элементов требует минимума ceiling( nk /B) промахов кэша, поскольку его элементы занимают смежные ячейки памяти. Это примерно в B/ k раз лучше, чем количество промахов кэша, необходимых для доступа к n элементам в случайных ячейках памяти. Как следствие, последовательная итерация по массиву на практике заметно быстрее, чем итерация по многим другим структурам данных, свойство, называемое локальностью ссылки (это не означает, однако, что использование идеального хеша или тривиального хеша в том же (локальном) массиве не будет еще быстрее - и достижимо за постоянное время ). Библиотеки предоставляют оптимизированные на низком уровне средства для копирования диапазонов памяти (например, memcpy ), которые можно использовать для перемещения смежных блоков элементов массива значительно быстрее, чем это можно достичь с помощью доступа к отдельным элементам. Ускорение таких оптимизированных процедур зависит от размера элемента массива, архитектуры и реализации.
С точки зрения памяти массивы представляют собой компактные структуры данных без накладных расходов на каждый элемент . Накладные расходы на каждый массив могут быть (например, для хранения границ индекса), но это зависит от языка. Также может случиться, что элементы, хранящиеся в массиве, требуют меньше памяти, чем те же элементы, хранящиеся в отдельных переменных, поскольку несколько элементов массива могут храниться в одном слове ; такие массивы часто называют упакованными массивами. Крайним (но часто используемым) случаем является битовый массив , где каждый бит представляет один элемент. Таким образом, один октет может содержать до 256 различных комбинаций до 8 различных условий в наиболее компактной форме.
Доступ к массивам со статически предсказуемыми шаблонами доступа является основным источником параллелизма данных .
Динамические массивы или растущая матрица похожи на массивы, но добавляют возможность вставлять и удалять элементы; добавление и удаление в конце особенно эффективно. Однако они резервируют линейное ( Θ ( n )) дополнительное хранилище, тогда как массивы не резервируют дополнительное хранилище.
Ассоциативные массивы предоставляют механизм для функциональности, подобной массиву, без огромных накладных расходов на хранение, когда значения индекса разрежены. Например, массив, содержащий значения только с индексами 1 и 2 миллиарда, может выиграть от использования такой структуры. Специализированные ассоциативные массивы с целочисленными ключами включают Patricia trys , Judy arrays и van Emde Boas trees .
Сбалансированные деревья требуют O(log n ) времени для индексированного доступа, но также позволяют вставлять или удалять элементы за O(log n ) времени, [11] тогда как расширяемые массивы требуют линейного (Θ( n )) времени для вставки или удаления элементов в произвольной позиции.
Связанные списки допускают постоянное время удаления и вставки в середину, но требуют линейного времени для индексированного доступа. Их использование памяти обычно хуже, чем у массивов, но все равно линейно.
Вектор Илиффе — это альтернатива многомерной структуре массива. Он использует одномерный массив ссылок на массивы на одно измерение меньше. Для двух измерений, в частности, эта альтернативная структура будет вектором указателей на векторы, по одному на каждую строку (указатель на c или c++). Таким образом, элемент в строке i и столбце j массива A будет доступен с помощью двойной индексации ( A [ i ][ j ] в типичной нотации). Эта альтернативная структура допускает неровные массивы , где каждая строка может иметь разный размер — или, в общем случае, где допустимый диапазон каждого индекса зависит от значений всех предыдущих индексов. Это также экономит одно умножение (на приращение адреса столбца), заменяя его битовым сдвигом (для индексации вектора указателей строк) и одним дополнительным доступом к памяти (извлечение адреса строки), что может быть целесообразным в некоторых архитектурах.
Размерность массива — это количество индексов, необходимых для выбора элемента. Таким образом, если массив рассматривать как функцию на множестве возможных комбинаций индексов, то это размерность пространства, дискретным подмножеством которого является его домен. Таким образом, одномерный массив — это список данных, двумерный массив — это прямоугольник данных, [12] трехмерный массив — это блок данных и т. д.
Это не следует путать с размерностью множества всех матриц с заданным доменом, то есть с числом элементов в массиве. Например, массив с 5 строками и 4 столбцами является двумерным, но такие матрицы образуют 20-мерное пространство. Аналогично, трехмерный вектор может быть представлен одномерным массивом размера три.
В большинстве языков программирования индекс массива (отсчет) начинается с 0, а не с 1. Индекс первого элемента массива равен 0, индекс второго элемента массива равен 1 и т. д. В массиве имен ниже вы можете увидеть индексы и значения.
Структуры данных/массивы в Wikibooks
