В информатике массив — это тип данных , который представляет собой набор элементов ( значений или переменных ), каждый из которых выбран одним или несколькими индексами (идентифицирующими ключами), которые могут быть вычислены во время выполнения во время выполнения программы. Такую коллекцию обычно называют переменной массива или значением массива . [1] По аналогии с математическими понятиями вектор и матрица , типы массивов с одним и двумя индексами часто называют векторным типом и матричным типом соответственно. В более общем смысле тип многомерного массива можно назвать тензорным типом по аналогии с физическим понятием тензор . [2]
Языковая поддержка типов массивов может включать определенные встроенные типы данных массива, некоторые синтаксические конструкции ( конструкторы типов массивов ), которые программист может использовать для определения таких типов и объявления переменных массива, а также специальные обозначения для индексации элементов массива. [1] Например, в языке программирования Паскаль объявление type MyTable = array [1..4,1..2] of integerопределяет новый тип данных массива, называемый MyTable. Затем объявление var A: MyTableопределяет переменную Aэтого типа, которая представляет собой совокупность восьми элементов, каждый из которых представляет собой целочисленную переменную, идентифицируемую двумя индексами. В программе на языке Паскаль эти элементы обозначаются A[1,1], A[1,2], A[2,1], …, A[4,2]. [3] Специальные типы массивов часто определяются стандартными библиотеками языка .
Динамические списки также более распространены и их легче реализовать [ сомнительно ] , чем динамические массивы . Типы массивов отличаются от типов записей главным образом потому, что они позволяют вычислять индексы элементов во время выполнения , как в присваивании Паскаля A[I,J] := A[N-I,2*J]. Помимо прочего, эта функция позволяет одному итеративному оператору обрабатывать произвольное количество элементов переменной массива.
В более теоретическом контексте, особенно в теории типов и при описании абстрактных алгоритмов , термины «массив» и «тип массива» иногда относятся к абстрактному типу данных (ADT), также называемому абстрактным массивом , или могут относиться к ассоциативному массиву , математическая модель с основными операциями и поведением типичного типа массива в большинстве языков — по сути, коллекция элементов, которые выбираются по индексам, вычисляемым во время выполнения.
В зависимости от языка типы массивов могут перекрываться (или отождествляться) с другими типами данных, описывающими совокупность значений, например списками и строками . Типы массивов часто реализуются структурами данных массива , но иногда и другими средствами, такими как хеш-таблицы , связанные списки или деревья поиска .
Язык программирования Хайнца Рутисхаузера Superplan (1949–1951) включал многомерные массивы. Однако Рутисхаузер, хотя и описал, как должен быть построен компилятор для его языка, не реализовал его.
Языки ассемблера и языки низкого уровня, такие как BCPL [4], обычно не имеют синтаксической поддержки массивов.
Из-за важности структур массивов для эффективных вычислений самые ранние языки программирования высокого уровня, включая FORTRAN (1957 г.), COBOL (1960 г.) и Algol 60 (1960 г.), обеспечивали поддержку многомерных массивов.
Структуру данных массива можно математически смоделировать как абстрактную структуру данных ( абстрактный массив ) с помощью двух операций.
Эти операции необходимы для удовлетворения аксиом [5]
для любого состояния массива A , любого значения V и любых кортежей I , J , для которых определены операции.
Первая аксиома означает, что каждый элемент ведет себя как переменная. Вторая аксиома означает, что элементы с разными индексами ведут себя как непересекающиеся переменные, поэтому сохранение значения в одном элементе не влияет на значение любого другого элемента.
Эти аксиомы не накладывают никаких ограничений на набор допустимых кортежей индексов I , поэтому эту абстрактную модель можно использовать для треугольных матриц и других массивов странной формы.
Чтобы эффективно реализовать переменные таких типов как структуры массива (с индексированием, выполняемым с помощью арифметики указателей ), многие языки ограничивают индексы целочисленными типами данных (или другими типами, которые можно интерпретировать как целые числа, например байтами и перечисляемыми типами ), и требуют, чтобы все элементы имели одинаковый тип данных и размер хранилища. Большинство этих языков также ограничивают каждый индекс конечным интервалом целых чисел, который остается фиксированным на протяжении всего времени существования переменной массива. Фактически, в некоторых компилируемых языках диапазоны индексов могут быть известны во время компиляции .
С другой стороны, некоторые языки программирования предоставляют более либеральные типы массивов, которые позволяют индексировать произвольные значения, такие как числа с плавающей запятой , строки , объекты , ссылки и т. д. Такие значения индекса не могут быть ограничены интервалом, а тем более фиксированный интервал. Таким образом, эти языки обычно позволяют создавать произвольные новые элементы в любое время. Этот выбор исключает реализацию типов массивов как структур данных массива. То есть эти языки используют синтаксис, подобный массиву, для реализации более общей семантики ассоциативного массива и, следовательно, должны быть реализованы с помощью хеш-таблицы или какой-либо другой структуры данных поиска .
Количество индексов, необходимых для указания элемента, называется размерностью , размерностью или рангом типа массива. (Эта номенклатура противоречит понятию размерности в линейной алгебре, которое выражает форму матрицы . Таким образом, массив чисел с 5 строками и 4 столбцами, следовательно, с 20 элементами, считается имеющим размерность 2 в вычислительном контексте, но представляет собой матрица, которая считается размерной 4 × 5. Кроме того, значение слова «ранг» в информатике противоречит понятию тензорного ранга , которое является обобщением концепции линейной алгебры ранга матрицы .)
Многие языки поддерживают только одномерные массивы. В этих языках многомерный массив обычно представляется вектором Илиффа — одномерным массивом ссылок на массивы на одно измерение меньше. В частности, двумерный массив будет реализован как вектор указателей на его строки. Таким образом, доступ к элементу в строке i и столбце j массива A будет осуществляться посредством двойной индексации ( A [ i ][ j ] в типичных обозначениях). Этот способ эмуляции многомерных массивов позволяет создавать зубчатые массивы , где каждая строка может иметь разный размер – или, вообще, где допустимый диапазон каждого индекса зависит от значений всех предыдущих индексов.
Такое представление многомерных массивов широко распространено в программном обеспечении C и C++. Однако C и C++ будут использовать формулу линейной индексации для многомерных массивов, которые объявлены с постоянным размером времени компиляции, например , int A[10][20]или int A[m][n]вместо традиционного int **A. [6]
Большинство языков программирования, поддерживающих массивы, поддерживают операции сохранения и выбора и имеют специальный синтаксис для индексации. В ранних языках использовались круглые скобки, например A(i,j), как в FORTRAN; другие выбирают квадратные скобки, например A[i,j]или A[i][j], как в Алголе 60 и Паскале (чтобы отличить использование круглых скобок для вызовов функций ).
Типы данных массива чаще всего реализуются как структуры массива: с индексами, ограниченными целочисленными (или полностью упорядоченными) значениями, диапазонами индексов, фиксированными во время создания массива, и полилинейной адресацией элементов. Так было в большинстве языков «третьего поколения» и до сих пор так происходит в большинстве языков системного программирования , таких как Ada , C и C++ . Однако в некоторых языках типы данных массива имеют семантику ассоциативных массивов с индексами произвольного типа и созданием динамических элементов. Это относится к некоторым языкам сценариев, таким как Awk и Lua , а также к некоторым типам массивов, предоставляемым стандартными библиотеками C++ .
Некоторые языки (например, Pascal и Modula) выполняют проверку границ при каждом доступе, вызывая исключение или прерывая программу, когда какой-либо индекс выходит за пределы допустимого диапазона. Составители могут разрешить отключение этих проверок, чтобы обменять безопасность на скорость. Другие языки (например, FORTRAN и C) доверяют программисту и не выполняют никаких проверок. Хорошие компиляторы могут также проанализировать программу, чтобы определить диапазон возможных значений, которые может иметь индекс, и этот анализ может привести к исключению проверки границ .
Некоторые языки, такие как C, предоставляют только типы массивов , отсчитываемые от нуля , для которых минимальное допустимое значение любого индекса равно 0. Этот выбор удобен для реализации массивов и вычислений адресов. С помощью такого языка, как C, можно определить указатель на внутреннюю часть любого массива, который будет символически действовать как псевдомассив, вмещающий отрицательные индексы. Это работает только потому, что C не проверяет индекс на соответствие границам при использовании.
Другие языки предоставляют только типы массивов, основанные на единице , где каждый индекс начинается с 1; это традиционное соглашение в математике для матриц и математических последовательностей . Некоторые языки, такие как Pascal и Lua, поддерживают типы массивов , основанные на n , минимальные допустимые индексы которых выбираются программистом. Относительные достоинства каждого выбора были предметом жарких споров. Индексация с отсчетом от нуля может избежать ошибок отклонения на единицу или ошибок столба забора , [7] в частности, итерации с отсчетом от 0 (5-0) раз, тогда как в эквивалентном полуоткрытом диапазоне с отсчетом от 1 цифра 6 сама по себе является потенциальной такой ошибкой. , обычно требуется , а включающий диапазон, отсчитываемый от 1, повторяется (5-1)+1 раз.for (i = 0; i < 5; i += 1)for (i = 1; i < 6; i += 1)length() + 1for (i = 1; i <= 5; i+= 1)
Связь между числами, появляющимися в объявлении массива, и индексом последнего элемента этого массива также зависит от языка. Во многих языках (например, C) необходимо указывать количество элементов, содержащихся в массиве; тогда как в других (таких как Pascal и Visual Basic .NET ) следует указать числовое значение индекса последнего элемента. Излишне говорить, что это различие несущественно в языках, где индексы начинаются с 1, таких как Lua .
Некоторые языки программирования поддерживают программирование массивов , где операции и функции, определенные для определенных типов данных, неявно расширяются на массивы элементов этих типов. Таким образом , можно написать A + B , чтобы добавить соответствующие элементы двух массивов A и B. Обычно эти языки обеспечивают как поэлементное умножение , так и стандартное матричное произведение линейной алгебры , и то, какое из них представлено оператором * , зависит от языка.
Языки, обеспечивающие возможности программирования массивов, получили широкое распространение после появления инноваций в этой области APL . Это основные возможности предметно-ориентированных языков, таких как GAUSS , IDL , Matlab и Mathematica . Они являются основным средством в новых языках, таких как Julia и последние версии Fortran . Эти возможности также предоставляются через стандартные библиотеки расширений для других языков программирования общего назначения (например, широко используемая библиотека NumPy для Python ).
Многие языки предоставляют встроенный строковый тип данных со специальной нотацией (« строковые литералы ») для построения значений этого типа. В некоторых языках (например, C) строка представляет собой просто массив символов или обрабатывается примерно таким же образом. Другие языки, такие как Паскаль , могут предоставлять совершенно другие операции со строками и массивами.
Некоторые языки программирования предоставляют операции, которые возвращают размер (количество элементов) вектора или, в более общем плане, диапазон каждого индекса массива. В C и C++ массивы не поддерживают функцию размера , поэтому программистам часто приходится объявлять отдельную переменную для хранения размера и передавать ее процедурам как отдельный параметр.
Элементы вновь созданного массива могут иметь неопределенные значения (как в C) или могут иметь определенное значение «по умолчанию», например 0 или нулевой указатель (как в Java).
В C++ объект std::vector поддерживает операции хранения , выбора и добавления с характеристиками производительности, описанными выше. У векторов можно запросить размер и изменить их размер. Также поддерживаются более медленные операции, такие как вставка элемента в середину.
Операция разрезания массива берет подмножество элементов объекта типа массива (значения или переменной), а затем собирает их в другой объект типа массива, возможно, с другими индексами. Если типы массивов реализованы как структуры массива, многие полезные операции разрезания (такие как выбор подмассива, замена индексов или изменение направления индексов на противоположное) могут выполняться очень эффективно, манипулируя вектором примеси структуры. Возможные срезы зависят от деталей реализации: например, FORTRAN позволяет отрезать один столбец матричной переменной, но не строку, и обрабатывать ее как вектор; тогда как C позволяет отрезать строку от матрицы, но не столбец.
С другой стороны, другие операции среза возможны, когда типы массивов реализованы другими способами.
Некоторые языки допускают динамические массивы (также называемые изменяемым размером, расширяемыми или расширяемыми): переменные массива, диапазоны индексов которых могут быть расширены в любое время после создания без изменения значений его текущих элементов.
Для одномерных массивов эта возможность может быть предоставлена как операция « append( A , x )», которая увеличивает размер массива A на единицу, а затем устанавливает значение последнего элемента в x . Другие типы массивов (например, строки Pascal) предоставляют оператор конкатенации, который можно использовать вместе с нарезкой для достижения этого эффекта и многого другого. В некоторых языках присвоение значения элементу массива при необходимости автоматически расширяет массив, включив в него этот элемент. В других типах массивов срез может быть заменен массивом другого размера с соответствующим перенумерованием последующих элементов – как в назначении списка Python « A [5:5] = [10,20,30]», которое вставляет три новых элементы (10,20 и 30) перед элементом « A [5]». Массивы изменяемого размера концептуально похожи на списки , и в некоторых языках эти две концепции являются синонимами.
Расширяемый массив может быть реализован как массив фиксированного размера со счетчиком, который записывает, сколько элементов фактически используется. Эта appendоперация просто увеличивает счетчик; до тех пор, пока не будет использован весь массив, когда appendоперация может быть определена как неудачная. Это реализация динамического массива с фиксированной емкостью, как в stringтипе Паскаля. Альтернативно, appendоперация может перераспределить базовый массив большего размера и скопировать старые элементы в новую область.
