В информатике массив — это структура данных , состоящая из набора элементов ( значений или переменных ) одинакового размера памяти, каждый из которых идентифицируется по крайней мере одним индексом или ключом массива . Массив хранится таким образом, что положение каждого элемента можно вычислить по его индексному кортежу с помощью математической формулы. [1] [2] [3] Самый простой тип структуры данных — это линейный массив, также называемый одномерным массивом.
Например, массив из десяти 32-битных (4-байтовых) целочисленных переменных с индексами от 0 до 9 может быть сохранен в виде десяти слов по адресам памяти 2000, 2004, 2008, ..., 2036 (в шестнадцатеричном формате : 0x7D0, 0x7D4, 0x7D8, ..., 0x7F4) так, чтобы элемент с индексом i имел адрес 2000 + ( i × 4). [4]
Адрес памяти первого элемента массива называется первым адресом, основным адресом или базовым адресом.
Поскольку математическую концепцию матрицы можно представить в виде двумерной сетки, двумерные массивы также иногда называют «матрицами». В некоторых случаях термин «вектор» используется в вычислениях для обозначения массива, хотя кортежи , а не векторы, являются более математически правильным эквивалентом. Таблицы часто реализуются в виде массивов, особенно таблиц поиска ; слово «таблица» иногда используется как синоним массива.
Массивы являются одними из старейших и наиболее важных структур данных и используются практически во всех программах. Они также используются для реализации многих других структур данных, таких как списки и строки . Они эффективно используют логику адресации компьютеров. В большинстве современных компьютеров и многих внешних запоминающих устройствах память представляет собой одномерный массив слов, индексами которого являются их адреса. Процессоры , особенно векторные , часто оптимизированы для операций с массивами.
Массивы полезны главным образом потому, что индексы элементов могут быть вычислены во время выполнения . Помимо прочего, эта функция позволяет одному итеративному оператору обрабатывать произвольное количество элементов массива. По этой причине элементы структуры данных массива должны иметь одинаковый размер и использовать одно и то же представление данных. Набор допустимых индексных кортежей и адреса элементов (и, следовательно, формула адресации элементов) обычно [3] [5] , но не всегда [2] фиксированы во время использования массива.
Термин «массив» может также относиться к типу данных массива , типу данных , предоставляемому большинством языков программирования высокого уровня, который состоит из набора значений или переменных, которые могут быть выбраны по одному или нескольким индексам, вычисляемым во время выполнения. . Типы массивов часто реализуются структурами массивов; однако в некоторых языках они могут быть реализованы с помощью хеш-таблиц , связанных списков , деревьев поиска или других структур данных.
Этот термин также используется, особенно при описании алгоритмов , для обозначения ассоциативного массива или «абстрактного массива», теоретической модели информатики ( абстрактного типа данных или ADT), предназначенной для отражения основных свойств массивов.
Первые цифровые компьютеры использовали машинное программирование для создания структур массивов и доступа к ним для таблиц данных, векторных и матричных вычислений и для многих других целей. Джон фон Нейман написал первую программу сортировки массивов ( сортировка слиянием ) в 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 элементов, они будут храниться линейно, но начиная с линейной первой строки, а затем продолжая вторую строку. Приведенный выше массив будет сохранен как 11 , 12 , 13 , 21 , 22 , 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 . Часто бывает полезно упаковать эти параметры в запись, называемую дескриптором массива , вектором шага или вектором допинга . [2] [3] Размер каждого элемента, а также минимальное и максимальное значения, разрешенные для каждого индекса, также могут быть включены в вектор привязки. Вектор допинга — это полный дескриптор массива и удобный способ передачи массивов в качестве аргументов процедурам . Многие полезные операции разрезания массива (например, выбор подмассива, замена индексов или изменение направления индексов на противоположное) могут быть выполнены очень эффективно, манипулируя вектором примеси. [2]
Часто коэффициенты выбираются так, чтобы элементы занимали непрерывную область памяти. Однако в этом нет необходимости. Даже если массивы всегда создаются из смежных элементов, некоторые операции разрезания массива могут создавать из них несмежные подмассивы.
Существует два систематических компактных макета двумерного массива. Например, рассмотрим матрицу
В макете построчного порядка (принятом в C для статически объявленных массивов) элементы в каждой строке хранятся в последовательных позициях, и все элементы строки имеют меньший адрес, чем любой из элементов последовательной строки:
В порядке по столбцам (традиционно используемом в Фортране) элементы в каждом столбце расположены последовательно в памяти, и все элементы столбца имеют меньший адрес, чем любой из элементов последовательного столбца:
Для массивов с тремя или более индексами «основной порядок строк» помещает в последовательные позиции любые два элемента, кортежи индексов которых отличаются только на один в последнем индексе . «Основной порядок столбца» аналогичен первому индексу .
В системах, использующих кэш процессора или виртуальную память , сканирование массива происходит намного быстрее, если последовательные элементы хранятся в последовательных позициях в памяти, а не разбросаны по разбросу. Это известно как пространственная локальность, которая представляет собой тип локальности отсчета . Многие алгоритмы, использующие многомерные массивы, сканируют их в предсказуемом порядке. Программист (или сложный компилятор) может использовать эту информацию для выбора между расположением строк или столбцов для каждого массива. Например, при вычислении произведения A · B двух матриц было бы лучше хранить A в порядке строк, а B — в порядке столбцов.
Статические массивы имеют размер, который фиксируется при их создании, и, следовательно, не позволяют вставлять или удалять элементы. Однако, выделив новый массив и скопировав в него содержимое старого массива, можно эффективно реализовать динамическую версию массива; см. динамический массив . Если эта операция выполняется нечасто, вставки в конец массива требуют только амортизированного постоянного времени.
Некоторые структуры данных массива не перераспределяют память, но сохраняют количество используемых элементов массива, называемое счетчиком или размером. Это фактически делает массив динамическим с фиксированным максимальным размером или емкостью; Строки Паскаля являются примером этого.
Иногда используются более сложные (нелинейные) формулы. Например, для компактного двумерного треугольного массива формулой адресации является полином второй степени.
И сохранение , и выбор занимают (в худшем детерминированном случае) постоянное время . Массивы занимают линейное ( O ( n )) пространство по количеству элементов n , которые они содержат.
В массиве с размером элемента k и на машине с размером строки кэша B байт итерация по массиву из n элементов требует минимального количества промахов в кэше ( nk /B), поскольку его элементы занимают смежные ячейки памяти. Это примерно в B/ k раз больше, чем количество промахов в кэше, необходимых для доступа к n элементам в случайных ячейках памяти. Как следствие, последовательная итерация по массиву на практике выполняется заметно быстрее, чем итерация по многим другим структурам данных, свойство, называемое локальностью ссылки (однако это не означает, что использование идеального хеша или тривиального хеша в одном и том же (локальном) массиве , не будет еще быстрее - и достижимо за постоянное время ). Библиотеки предоставляют низкоуровневые оптимизированные средства для копирования диапазонов памяти (например, memcpy ), которые можно использовать для перемещения смежных блоков элементов массива значительно быстрее, чем это может быть достигнуто при доступе к отдельным элементам. Ускорение таких оптимизированных процедур зависит от размера элемента массива, архитектуры и реализации.
С точки зрения памяти массивы представляют собой компактные структуры данных без затрат на каждый элемент . Могут существовать дополнительные издержки для каждого массива (например, для хранения границ индекса), но это зависит от языка. Также может случиться так, что элементы, хранящиеся в массиве, требуют меньше памяти, чем те же элементы, хранящиеся в отдельных переменных, поскольку несколько элементов массива могут храниться в одном слове ; такие массивы часто называют упакованными массивами. Крайним (но часто используемым) случаем является битовый массив , где каждый бит представляет один элемент. Таким образом, один октет может содержать до 256 различных комбинаций до 8 различных условий в наиболее компактной форме.
Доступ к массивам со статически предсказуемыми шаблонами доступа является основным источником параллелизма данных .
Динамические или расширяемые массивы аналогичны массивам, но добавляют возможность вставки и удаления элементов; добавление и удаление в конце особенно эффективно. Однако они резервируют линейную ( Θ ( n )) дополнительную память, тогда как массивы не резервируют дополнительную память.
Ассоциативные массивы предоставляют механизм для функциональности, подобной массиву, без огромных затрат на хранение, когда значения индекса разрежены. Например, массив, содержащий значения только с индексами 1 и 2 миллиарда, может выиграть от использования такой структуры. К специализированным ассоциативным массивам с целочисленными ключами относятся массивы Патрисии Три , массивы Джуди и деревья Ван Эмде Боаса .
Сбалансированные деревья требуют времени O(log n ) для индексированного доступа, но также позволяют вставлять или удалять элементы за время O(log n ), [13] тогда как растущие массивы требуют линейного (Θ( n )) времени для вставки или удаления элементов за один раз. произвольное положение.
Связанные списки позволяют удалять и вставлять посередине в постоянное время, но для индексированного доступа требуется линейное время. Их использование памяти обычно хуже, чем у массивов, но все равно линейно.
Вектор Илиффа является альтернативой многомерной структуре массива. Он использует одномерный массив ссылок на массивы на одно измерение меньше. В частности, для двух измерений эта альтернативная структура будет вектором указателей на векторы, по одному на каждую строку (указатель на c или c++). Таким образом, доступ к элементу в строке i и столбце j массива A будет осуществляться посредством двойной индексации ( A [ i ][ j ] в типичных обозначениях). Эта альтернативная структура допускает неровные массивы , где каждая строка может иметь разный размер или, вообще, где допустимый диапазон каждого индекса зависит от значений всех предыдущих индексов. Это также экономит одно умножение (на приращение адреса столбца), заменяя его битовым сдвигом (для индексации вектора указателей строк) и один дополнительный доступ к памяти (выборка адреса строки), что может быть полезно в некоторых архитектурах.
Размерность массива — это количество индексов, необходимых для выбора элемента . Таким образом, если массив рассматривается как функция набора возможных комбинаций индексов, это размерность пространства, дискретным подмножеством которого является его область определения. Таким образом, одномерный массив — это список данных, двумерный массив — это прямоугольник данных, [14] трехмерный массив — это блок данных и т. д.
Не следует путать это с размерностью множества всех матриц с заданным доменом, то есть количеством элементов в массиве. Например, массив из 5 строк и 4 столбцов является двумерным, но такие матрицы образуют 20-мерное пространство. Аналогично трехмерный вектор может быть представлен одномерным массивом размера три.
{{cite conference}}: CS1 maint: статус URL ( ссылка )В большинстве компьютерных языков индекс массива (отсчет) начинается с 0, а не с 1. Индекс первого элемента массива равен 0, индекс второго элемента массива равен 1 и так далее.
В массиве имен ниже вы можете увидеть индексы и значения.
Структуры данных/массивы в Wikibooks