В информатике программирование массивов относится к решениям, которые позволяют применять операции ко всему набору значений одновременно. Такие решения обычно используются в научных и инженерных целях.
Современные языки программирования, поддерживающие программирование массивов (также известные как векторные или многомерные языки), были разработаны специально для обобщения операций над скалярами для прозрачного применения к векторам , матрицам и многомерным массивам. К ним относятся APL , J , Fortran , MATLAB , Analytica , Octave , R , Cilk Plus , Julia , Perl Data Language (PDL) . В этих языках операцию, которая работает с целыми массивами, можно назвать векторизованной операцией [1] независимо от того, выполняется ли она на векторном процессоре , реализующем векторные инструкции. Примитивы программирования массивов кратко выражают общие идеи о манипулировании данными. В некоторых случаях уровень краткости может быть впечатляющим: нередко [ нужен пример ] встречаются однострочники языка программирования массивов , требующие нескольких страниц объектно-ориентированного кода.
Фундаментальная идея программирования массивов заключается в том, что операции применяются сразу ко всему набору значений. Это делает ее моделью программирования высокого уровня , поскольку она позволяет программисту думать и работать с целыми совокупностями данных, не прибегая к явным циклам отдельных скалярных операций.
Кеннет Э. Айверсон описал обоснование программирования массивов (фактически имея в виду APL) следующим образом: [2]
большинство языков программирования явно уступают математической записи и мало используются в качестве инструментов мышления способами, которые, скажем, для прикладного математика могли бы считаться важными.
Тезис состоит в том, что преимущества исполнительности и универсальности, присущие языкам программирования, могут быть эффективно объединены в одном связном языке с преимуществами, предлагаемыми математической нотацией. важно отличать трудность описания и изучения части обозначений от трудности освоения ее значений. Например, выучить правила вычисления матричного произведения легко, но овладеть его значениями (такими как его ассоциативность, его дистрибутивность по сложению и его способность представлять линейные функции и геометрические операции) — это другой и гораздо более трудный вопрос. .
Действительно, из-за самой многозначительности нотации может показаться, что ее сложнее изучить из-за множества свойств, которые она предлагает для исследования.
[...]
Пользователи компьютеров и языков программирования часто озабочены в первую очередь эффективностью выполнения алгоритмов и поэтому могут сразу отвергнуть многие из представленных здесь алгоритмов. Такое отклонение было бы недальновидным, поскольку четкое изложение алгоритма обычно можно использовать в качестве основы, на основе которой можно легко вывести более эффективный алгоритм.
В основе программирования и мышления массивов лежит поиск и использование свойств данных, в которых отдельные элементы похожи или соседствуют. В отличие от объектной ориентации, которая неявно разбивает данные на составные части (или скалярные величины), ориентация массива предполагает группировку данных и применение единообразной обработки.
Ранг функции является важной концепцией для языков программирования в целом, по аналогии с тензорным рангом в математике: функции, которые работают с данными, могут быть классифицированы по количеству измерений, на которые они воздействуют. Например, обычное умножение является скалярной ранговой функцией, поскольку оно работает с нульмерными данными (отдельными числами). Операция векторного произведения является примером функции векторного ранга, поскольку она работает с векторами, а не со скалярами. Умножение матриц является примером функции 2-го ранга, поскольку оно работает с двумерными объектами (матрицами). Операторы свертывания уменьшают размерность массива входных данных на одно или несколько измерений. Например, суммирование по элементам сжимает входной массив на 1 измерение.
Программирование массивов очень хорошо подходит для неявного распараллеливания ; тема многих исследований в настоящее время. Кроме того, процессоры Intel и совместимые процессоры, разработанные и произведенные после 1997 года, содержали различные расширения набора команд, начиная с MMX и заканчивая SSSE3 и 3DNow! , которые включают в себя элементарные возможности массива SIMD . Это продолжалось и в 2020-е годы с такими наборами команд, как AVX-512 , превращающими современные процессоры в сложные векторные процессоры. Обработка массивов отличается от параллельной обработки тем, что один физический процессор одновременно выполняет операции над группой элементов, в то время как параллельная обработка направлена на разделение более крупной задачи на более мелкие ( MIMD ), которые должны решаться по частям множеством процессоров. С 2023 года процессоры с несколькими ядрами и графические процессоры с тысячами общих вычислительных ядер станут обычным явлением.
Каноническими примерами языков программирования массивов являются Fortran , APL и J. Другие включают: A+ , Analytica , Chapel , IDL , Julia , K , Klong, Q , MATLAB , GNU Octave , Scilab , FreeMat , PDL , R , S-Lang , SAC , Nial , ZPL , Futhark и TI-BASIC .
В скалярных языках, таких как C и Pascal , операции применяются только к одиночным значениям, поэтому a + b выражает сложение двух чисел. В таких языках добавление одного массива к другому требует индексации и циклов, кодирование которых утомительно.
for ( я знак равно 0 ; я < n ; я ++ ) for ( j знак равно 0 ; j < n ; j ++ ) a [ я ][ j ] += b [ я ][ j ]; В языках, основанных на массивах, например в Фортране, приведенный выше вложенный цикл for можно записать в формате массива в одну строку:
а = а + б или, альтернативно, чтобы подчеркнуть массивность объектов,
a (:,:) = a (:,:) + b (:,:) Хотя скалярные языки, такие как C, не имеют собственных элементов программирования массивов как часть самого языка, это не означает, что программы, написанные на этих языках, никогда не используют преимущества базовых методов векторизации (т. е. использования векторных инструкций ЦП, если они есть). их или используя несколько ядер ЦП). Некоторые компиляторы C, такие как GCC, на некоторых уровнях оптимизации обнаруживают и векторизуют разделы кода, которые, по мнению его эвристики, выиграют от этого. Другой подход представлен API OpenMP , который позволяет распараллеливать соответствующие разделы кода, используя преимущества нескольких ядер ЦП.
В языках массивов операции обобщены и применимы как к скалярам, так и к массивам. Таким образом, a + b выражает сумму двух скаляров, если a и b являются скалярами, или сумму двух массивов, если они являются массивами.
Язык массивов упрощает программирование, но, возможно, ценой, известной как штраф за абстракцию . [3] [4] [5] Поскольку дополнения выполняются изолированно от остального кодирования, они не могут создать оптимально наиболее эффективный код. (Например, добавление других элементов того же массива может впоследствии встретиться во время того же выполнения, что приведет к ненужным повторным поискам.) Даже самому сложному оптимизирующему компилятору будет чрезвычайно трудно объединить две или более явно несопоставимые функции, которые могут появиться в различные разделы программы или подпрограммы, хотя программист мог бы сделать это легко, агрегируя суммы за один проход по массиву, чтобы минимизировать накладные расходы ).
Предыдущий код C стал бы следующим на языке Ada [6] , который поддерживает синтаксис программирования массивов.
А := А + Б ;APL использует односимвольные символы Юникода без синтаксического сахара.
А ← А + Б Эта операция работает с массивами любого ранга (включая ранг 0), а также со скаляром и массивом. Dyalog APL расширяет исходный язык дополнительными назначениями :
А + ← Б Analytica обеспечивает ту же экономичность выражения, что и Ada.
А := А + В;
В третьем издании Dartmouth BASIC (1966 г.) были операторы MAT для манипуляций с матрицами и массивами.
DIM A ( 4 ), B ( 4 ), C ( 4 ) MAT A = 1 MAT B = 2 * A MAT C = A + B MAT PRINT A , B , C Язык матричного программирования Stata Mata поддерживает программирование массивов. Ниже мы иллюстрируем сложение, умножение, сложение матрицы и скаляра, поэлементное умножение, индексацию и одну из многих обратных матричных функций Маты.
. мата :: А знак равно ( 1 , 2 , 3 ) \( 4 , 5 , 6 ): А 1 2 3 +-------------+ 1 | 1 2 3 | 2 | 4 5 6 | +-------------+: B = ( 2 .. 4 ) \( 1 .. 3 ): Б 1 2 3 +-------------+ 1 | 2 3 4 | 2 | 1 2 3 | +-------------+: C = J ( 3 , 2 , 1 ) // Матрица единиц размером 3 на 2: С 1 2 +---------+ 1 | 1 1 | 2 | 1 1 | 3 | 1 1 | +---------+: Д = А + Б: Д 1 2 3 +-------------+ 1 | 3 5 7 | 2 | 5 7 9 | +-------------+: Е = А * С: Э 1 2 +-----------+ 1 | 6 6 | 2 | 15 15 | +-----------+: F = А: * Б: Ф 1 2 3 +----------------+ 1 | 2 6 12 | 2 | 4 10 18 | +----------------+: Г = Е : + 3: Г 1 2 +-----------+ 1 | 9 9 | 2 | 18 18 | +-----------+: H = F[( 2 \ 1 ), ( 1 , 2 )] // Индексация для получения подматрицы F и: // переключаем строки 1 и 2: Ч 1 2 +-----------+ 1 | 4 10 | 2 | 2 6 | +-----------+: I = invsym (F' * F) // Обобщенная инверсия (F*F^(-1)F=F): // симметричная положительная полуопределенная матрица: Я[симметричный] 1 2 3 +-------------------------------------------+ 1 | 0 | 2 | 0 3,25 | 3 | 0–1,75 . 9444444444 | +-------------------------------------------+: конецРеализация в MATLAB обеспечивает ту же экономию, что и при использовании языка Фортран.
А = А + Б ; Вариантом языка MATLAB является язык GNU Octave , который расширяет исходный язык расширенными присваиваниями:
А += Б ;И MATLAB, и GNU Octave изначально поддерживают операции линейной алгебры , такие как умножение матриц, обращение матриц и численное решение системы линейных уравнений , даже с использованием псевдообратных операций Мура-Пенроуза . [7] [8]
Пример внутреннего произведения двух массивов в Nial можно реализовать с помощью собственного оператора умножения матриц. If a— вектор-строка размера [1 n] и bсоответствующий вектор-столбец размера [n 1].
а*б;
Напротив, продукт начального уровня реализуется как:
а .* б;
Внутренний продукт между двумя матрицами, имеющими одинаковое количество элементов, может быть реализован с помощью вспомогательного оператора (:), который преобразует данную матрицу в вектор-столбец, и оператора транспонирования' :
А(:)' * Б(:);
Язык запросов расдаман — это язык программирования массивов, ориентированный на базы данных. Например, два массива можно добавить с помощью следующего запроса:
ВЫБЕРИТЕ A + B ИЗ A , B Язык R по умолчанию поддерживает парадигму массива. Следующий пример иллюстрирует процесс умножения двух матриц с последующим сложением скаляра (который, по сути, является одноэлементным вектором) и вектора:
> A <- матрица ( 1 : 6 , nrow = 2 ) # !!this имеет nrow=2 ... и A имеет 2 строки > A [,1] [,2] [,3] [1,] 1 3 5 [2,] 2 4 6 > B <- t ( матрица ( 6 : 1 , nrow = 2 ) ) # t() — оператор транспонирования !! здесь nrow=2 ... и B имеет 3 строки — - явное противоречие с определением A > B [,1] [,2] [1,] 6 5 [2,] 4 3 [3,] 2 1 > C <- A %*% B > C [, 1] [,2] [1,] 28 19 [2,] 40 28 > D <- C + 1 > D [,1] [,2] [1,] 29 20 [2,] 41 29 > D + c ( 1 , 1 ) # c() создает вектор [,1] [,2] [1,] 30 21 [2,] 42 30 Оператор левого деления матрицы кратко выражает некоторые семантические свойства матриц. Как и в скалярном эквиваленте, если ( определитель ) коэффициента (матрицы) Aне равен нулю, тогда можно решить (векторное) уравнение, A * x = bумножив обе части слева на обратную : (как в языках MATLAB, так и в GNU Octave) A. : ). Следующие математические утверждения справедливы, когда является квадратной матрицей полного ранга :A−1A^-1A
A^-1 *(A * x)==A^-1 * (b)(A^-1 * A)* x ==A^-1 * b ( ассоциативность умножения матрицы )x = A^-1 * bгде – оператор отношения== эквивалентности . Предыдущие операторы также являются допустимыми выражениями MATLAB, если третий выполняется раньше остальных (числовые сравнения могут быть ложными из-за ошибок округления).
Если система переопределена – так что Aв ней больше строк, чем столбцов – псевдоинверсия (в языках MATLAB и GNU Octave: ) может заменить инверсию следующим образом:A+pinv(A)A−1
pinv(A) *(A * x)==pinv(A) * (b)(pinv(A) * A)* x ==pinv(A) * b (ассоциативность умножения матрицы)x = pinv(A) * bОднако эти решения не являются ни наиболее краткими (например, все еще сохраняется необходимость нотационного дифференцирования переопределенных систем), ни наиболее эффективными в вычислительном отношении. Последний момент легко понять, если снова рассмотреть скалярный эквивалент a * x = b, для решения которого x = a^-1 * bпотребуются две операции вместо более эффективной x = b / a. Проблема в том, что обычно матричные умножения не являются коммутативными , поскольку расширение скалярного решения на матричный случай требует:
(a * x)/ a ==b / a(x * a)/ a ==b / a (для матриц коммутативность не выполняется!)x * (a / a)==b / a (ассоциативность справедлива и для матриц)x = b / aЯзык MATLAB вводит оператор левого деления, \чтобы сохранить существенную часть аналогии со скалярным случаем, тем самым упрощая математические рассуждения и сохраняя краткость:
A \ (A * x)==A \ b(A \ A)* x ==A \ b (ассоциативность справедлива и для матриц, коммутативность больше не требуется)x = A \ bЭто не только пример краткого программирования массивов с точки зрения кодирования, но и с точки зрения эффективности вычислений, которая в некоторых языках программирования массивов выигрывает от довольно эффективных библиотек линейной алгебры, таких как ATLAS или LAPACK . [9]
Возвращаясь к предыдущей цитате Айверсона, теперь ее обоснование должно быть очевидным:
важно отличать трудность описания и изучения части обозначений от трудности освоения ее значений. Например, выучить правила вычисления матричного произведения легко, но освоить его значения (такие как его ассоциативность, его дистрибутивность по сложению и его способность представлять линейные функции и геометрические операции) — это другой и гораздо более трудный вопрос. . Действительно, из-за самой многозначительности нотации может показаться, что ее сложнее изучить из-за множества свойств, которые она предлагает для исследования.
Использование специализированных и эффективных библиотек для обеспечения более кратких абстракций также распространено в других языках программирования. В C++ несколько библиотек линейной алгебры используют возможность языка перегружать операторы . В некоторых случаях очень краткая абстракция в этих языках явно зависит от парадигмы программирования массивов, как это происходит с библиотекой расширения NumPy для библиотек Python , Armadillo и Blitz++ . [10] [11]