В информатике программирование массивов относится к решениям, которые позволяют применять операции ко всему набору значений одновременно. Такие решения обычно используются в научных и инженерных условиях.
Современные языки программирования, поддерживающие программирование массивов (также известные как векторные или многомерные языки), были специально разработаны для обобщения операций над скалярами для прозрачного применения к векторам , матрицам и многомерным массивам. К ним относятся APL , J , Fortran , MATLAB , Analytica , Octave , R , Cilk Plus , Julia , Perl Data Language (PDL) . В этих языках операция, которая работает с целыми массивами, может быть названа векторизованной операцией [1] независимо от того, выполняется ли она на векторном процессоре , который реализует векторные инструкции. Примитивы программирования массивов лаконично выражают общие идеи о манипулировании данными. Уровень краткости может быть драматичным в определенных случаях: нередко [ нужен пример ] можно найти однострочники языка программирования массивов , которые требуют нескольких страниц объектно-ориентированного кода.
Основная идея программирования массивов заключается в том, что операции применяются сразу ко всему набору значений. Это делает его высокоуровневой моделью программирования, поскольку она позволяет программисту думать и работать с целыми совокупностями данных, не прибегая к явным циклам отдельных скалярных операций.
Кеннет Э. Айверсон описал обоснование программирования массивов (фактически ссылаясь на APL) следующим образом: [2]
большинство языков программирования определенно уступают математической нотации и мало используются в качестве инструментов мышления способами, которые могли бы считаться значимыми, скажем, для прикладной математики.
Тезис заключается в том, что преимущества исполняемости и универсальности, присущие языкам программирования, могут быть эффективно объединены в одном связном языке с преимуществами, предлагаемыми математической нотацией. важно отличать сложность описания и изучения части нотации от сложности освоения ее следствий. Например, изучение правил вычисления матричного произведения легко, но освоение ее следствий (таких как ее ассоциативность, ее дистрибутивность по сложению и ее способность представлять линейные функции и геометрические операции) — это другое и гораздо более сложное дело.
Действительно, сама суггестивность обозначения может сделать его изучение труднее из-за множества свойств, которые оно предлагает для исследования.
[...]
Пользователи компьютеров и языков программирования часто озабочены в первую очередь эффективностью выполнения алгоритмов и поэтому могут, вкратце, отбросить многие из представленных здесь алгоритмов. Такое отклонение было бы недальновидным, поскольку четкое изложение алгоритма обычно может быть использовано в качестве основы, из которой можно легко вывести более эффективный алгоритм.
Основой программирования и мышления массивов является поиск и использование свойств данных, где отдельные элементы похожи или смежны. В отличие от объектной ориентации, которая неявно разбивает данные на составные части (или скалярные величины), ориентация массивов стремится группировать данные и применять единообразную обработку.
Ранг функции является важным понятием для языков программирования массивов в целом, по аналогии с рангом тензора в математике: функции, которые работают с данными, можно классифицировать по числу измерений, на которые они действуют. Обычное умножение, например, является скалярной ранжированной функцией, поскольку она работает с нульмерными данными (отдельными числами). Операция векторного произведения является примером функции векторного ранга, поскольку она работает с векторами, а не скалярами. Матричное умножение является примером 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 , Perl Data Language (PDL), R , Raku , S-Lang , SAC , Nial , ZPL , Futhark и TI-BASIC .
В скалярных языках, таких как C и Pascal , операции применяются только к отдельным значениям, поэтому a + b выражает сложение двух чисел. В таких языках добавление одного массива к другому требует индексации и циклов, кодирование которых утомительно.
для ( i = 0 ; i < n ; i ++ ) для ( j = 0 ; j < n ; j ++ ) a [ i ][ j ] += b [ i ][ j ]; В языках, основанных на массивах, например в Фортране, вложенный цикл for, представленный выше, можно записать в формате массива в одну строку:
а = а + б или, в качестве альтернативы, подчеркнуть массивную природу объектов,
а (:,:) = а (:,:) + б (:,:) Хотя скалярные языки, такие как C, не имеют собственных элементов программирования массивов как части языка, это не означает, что программы, написанные на этих языках, никогда не используют базовые методы векторизации (т. е. использование векторных инструкций ЦП , если они у него есть, или использование нескольких ядер ЦП). Некоторые компиляторы C, такие как GCC, на некоторых уровнях оптимизации обнаруживают и векторизуют разделы кода, которые, по мнению их эвристики, выиграют от этого. Другой подход предоставляется API OpenMP , который позволяет распараллеливать применимые разделы кода, используя преимущества нескольких ядер ЦП.
В языках массивов операции обобщены для применения как к скалярам, так и к массивам. Таким образом, a + b выражает сумму двух скаляров, если a и b являются скалярами, или сумму двух массивов, если они являются массивами.
Язык массивов упрощает программирование, но, возможно, за счет так называемого штрафа за абстракцию . [3] [4] [5] Поскольку добавления выполняются изолированно от остальной части кодирования, они могут не создавать оптимально наиболее эффективный код. (Например, добавления других элементов того же массива могут впоследствии встречаться во время того же выполнения, вызывая ненужные повторные поиски.) Даже самому сложному оптимизирующему компилятору было бы чрезвычайно трудно объединить две или более явно разнородных функций, которые могут появляться в разных разделах программы или подпрограммах, хотя программист мог бы сделать это легко, агрегируя суммы за один проход по массиву, чтобы минимизировать накладные расходы .
Предыдущий код на языке C будет выглядеть следующим образом на языке Ada [6] , который поддерживает синтаксис программирования массивов.
А := А + В ;APL использует односимвольные символы Unicode без синтаксического сахара.
А ← А + Б Эта операция работает с массивами любого ранга (включая ранг 0), а также со скаляром и массивом. Dyalog APL расширяет исходный язык с помощью расширенных назначений :
А + ← Б Analytica обеспечивает ту же экономию выражения, что и Ada.
А := А + В;
В третьем издании Dartmouth BASIC (1966) имелись операторы MAT для манипулирования матрицами и массивами.
РАЗМЕР A ( 4 ), B ( 4 ), C ( 4 ) МАТ A = 1 МАТ B = 2 * A МАТ C = A + B МАТ ПЕЧАТЬ A , B , C Язык программирования матриц Mata от Stata поддерживает программирование массивов. Ниже мы проиллюстрируем сложение, умножение, сложение матрицы и скаляра, поэлементное умножение, индексацию и одну из многих обратных матричных функций Mata.
. мата :: А = ( 1 , 2 , 3 ) \( 4 , 5 , 6 ): А 1 2 3 +-------------+ 1 | 1 2 3 | 2 | 4 5 6 | +-------------+: В = ( 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 | +-----------+: Ф = А: * Б: Ф 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 обеспечивает ту же экономию, что и при использовании языка Fortran.
А = А + В ; Вариантом языка MATLAB является язык GNU Octave , который расширяет исходный язык с помощью расширенных назначений:
А += В ;И MATLAB, и GNU Octave изначально поддерживают операции линейной алгебры, такие как умножение матриц, обращение матриц и численное решение систем линейных уравнений , даже с использованием псевдообратной матрицы Мура–Пенроуза . [7] [8]
Пример Nial внутреннего произведения двух массивов может быть реализован с использованием собственного оператора умножения матриц. Если a— вектор-строка размером [1 n], а b— соответствующий вектор-столбец размером [n 1].
а * б;
Напротив, входной продукт реализуется следующим образом:
а .* б;
Скалярное произведение двух матриц с одинаковым числом элементов можно реализовать с помощью вспомогательного оператора (:), который преобразует заданную матрицу в вектор-столбец, и оператора транспонирования' :
А(:)' * Б(:);
Язык запросов rasdaman — это язык программирования массивов, ориентированный на базы данных. Например, два массива можно добавить с помощью следующего запроса:
ВЫБЕРИТЕ A + B ИЗ A , B Язык R по умолчанию поддерживает парадигму массива. Следующий пример иллюстрирует процесс умножения двух матриц с последующим сложением скаляра (который, по сути, является вектором из одного элемента) и вектора:
> A <- matrix ( 1 : 6 , nrow = 2 ) # !! здесь nrow=2 ... и у A 2 строки > A [,1] [,2] [,3] [1,] 1 3 5 [2,] 2 4 6 > B <- t ( matrix ( 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 Raku поддерживает парадигму массивов с помощью своих метаоператоров. [9] Следующий пример демонстрирует сложение массивов @a и @b с использованием гипероператора в сочетании с оператором «плюс».
[ 0 ] > мой @a = [[ 1 , 1 ],[ 2 , 2 ],[ 3 , 3 ]];[[ 1 1 ] [ 2 2 ] [ 3 3 ]][ 1 ] > мой @b = [[ 4 , 4 ],[ 5 , 5 ],[ 6 , 6 ]];[[ 4 4 ] [ 5 5 ] [ 6 6 ]][ 2 ] > @a »+« @b ;[[ 5 5 ] [ 7 7 ] [ 9 9 ]]Оператор левого деления матрицы лаконично выражает некоторые семантические свойства матриц. Как и в скалярном эквиваленте, если ( детерминант ) коэффициента (матрицы) Aне равен нулю, то можно решить (векторное) уравнение A * x = b, умножив обе стороны слева на обратную матрицу A: (в языках MATLAB и GNU Octave: ). Следующие математические утверждения справедливы, когда — квадратная матрица полного ранга :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 . [10]
Возвращаясь к предыдущей цитате Айверсона, теперь ее обоснование должно быть очевидным:
важно различать сложность описания и изучения части нотации от сложности освоения ее импликаций. Например, изучение правил вычисления матричного произведения легко, но освоение ее импликаций (таких как ее ассоциативность, ее дистрибутивность по сложению и ее способность представлять линейные функции и геометрические операции) — это другое и гораздо более сложное дело. Действительно, сама суггестивность нотации может сделать ее изучение более сложным из-за многих свойств, которые она предлагает для исследований.
Использование специализированных и эффективных библиотек для предоставления более лаконичных абстракций также распространено в других языках программирования. В C++ несколько библиотек линейной алгебры используют способность языка перегружать операторы . В некоторых случаях очень лаконичная абстракция в этих языках явно находится под влиянием парадигмы программирования массивов, как это делают библиотеки расширения NumPy для Python , Armadillo и Blitz++ . [11] [12]