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