Программирование массивов
В информатике относится к решениям , программирование массивов которые позволяют применять операции ко всему набору значений одновременно. Такие решения обычно используются в научных и инженерных целях.
Современные языки программирования, поддерживающие программирование массивов (также известные как векторные или многомерные языки), были разработаны специально для обобщения операций над скалярами для прозрачного применения к векторам , матрицам и многомерным массивам. К ним относятся 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 , Perl Data Language (PDL), R , Raku , S-Lang , SAC , Nial , ZPL , Futhark. и ТИ-БЕЙСИК .
Скалярные языки
[ редактировать ]В скалярных языках, таких как C и Pascal , операции применяются только к одиночным значениям, поэтому a + b выражает сложение двух чисел. В таких языках добавление одного массива к другому требует индексации и циклов, кодирование которых утомительно.
for (i = 0; i < n; i++)
for (j = 0; j < n; j++)
a[i][j] += b[i][j];
В языках, основанных на массивах, например в Фортране, приведенный выше вложенный цикл for можно записать в формате массива в одну строку:
a = a + b
или, альтернативно, чтобы подчеркнуть массивность объектов,
a(:,:) = a(:,:) + b(:,:)
ЦП, Хотя скалярные языки, такие как C, не имеют собственных элементов программирования массивов как часть самого языка, это не означает, что программы, написанные на этих языках, никогда не используют преимущества базовых методов векторизации (т. е. использования векторных инструкций если они есть). их или используя несколько ядер ЦП). Некоторые компиляторы C, такие как GCC, на некоторых уровнях оптимизации обнаруживают и векторизуют разделы кода, которые, по мнению его эвристики, выиграют от этого. Другой подход представлен API OpenMP , который позволяет распараллеливать соответствующие разделы кода, используя преимущества нескольких ядер ЦП.
Языки массивов
[ редактировать ]В языках массивов операции обобщены и применимы как к скалярам, так и к массивам. Таким образом, a + b выражает сумму двух скаляров, если a и b являются скалярами, или сумму двух массивов, если они являются массивами.
Язык массивов упрощает программирование, но, возможно, ценой, известной как штраф за абстракцию . [3] [4] [5] Поскольку дополнения выполняются изолированно от остального кода, они не могут создать оптимально наиболее эффективный код. (Например, добавление других элементов того же массива может впоследствии встретиться во время того же выполнения, что приведет к ненужным повторным поискам.) Даже самому сложному оптимизирующему компилятору будет чрезвычайно трудно объединить две или более явно несопоставимые функции, которые могут появиться в различные разделы программы или подпрограммы, хотя программист мог бы сделать это легко, агрегируя суммы за один проход по массиву, чтобы минимизировать накладные расходы ).
Есть
[ редактировать ]стал бы следующим Предыдущий код C на языке Ada : [6] который поддерживает синтаксис программирования массивов.
A := A + B;
АПЛ
[ редактировать ]APL использует односимвольные символы Юникода без синтаксического сахара.
A ← A + B
Эта операция работает с массивами любого ранга (включая ранг 0), а также со скаляром и массивом. Dyalog APL расширяет исходный язык дополнительными назначениями :
A +← B
Аналитика
[ редактировать ]Analytica обеспечивает ту же экономичность выражения, что и Ada.
A := A + B;
БАЗОВЫЙ
[ редактировать ]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 поддерживает программирование массивов. Ниже мы иллюстрируем сложение, умножение, сложение матрицы и скаляра, поэлементное умножение, индексацию и одну из многих обратных матричных функций Маты.
. mata:
: A = (1,2,3) \(4,5,6)
: A
1 2 3
+-------------+
1 | 1 2 3 |
2 | 4 5 6 |
+-------------+
: B = (2..4) \(1..3)
: B
1 2 3
+-------------+
1 | 2 3 4 |
2 | 1 2 3 |
+-------------+
: C = J(3,2,1) // A 3 by 2 matrix of ones
: C
1 2
+---------+
1 | 1 1 |
2 | 1 1 |
3 | 1 1 |
+---------+
: D = A + B
: D
1 2 3
+-------------+
1 | 3 5 7 |
2 | 5 7 9 |
+-------------+
: E = A*C
: E
1 2
+-----------+
1 | 6 6 |
2 | 15 15 |
+-----------+
: F = A:*B
: F
1 2 3
+----------------+
1 | 2 6 12 |
2 | 4 10 18 |
+----------------+
: G = E :+ 3
: G
1 2
+-----------+
1 | 9 9 |
2 | 18 18 |
+-----------+
: H = F[(2\1), (1, 2)] // Subscripting to get a submatrix of F and
: // switch row 1 and 2
: H
1 2
+-----------+
1 | 4 10 |
2 | 2 6 |
+-----------+
: I = invsym(F'*F) // Generalized inverse (F*F^(-1)F=F) of a
: // symmetric positive semi-definite matrix
: I
[symmetric]
1 2 3
+-------------------------------------------+
1 | 0 |
2 | 0 3.25 |
3 | 0 -1.75 .9444444444 |
+-------------------------------------------+
: end
МАТЛАБ
[ редактировать ]Реализация в MATLAB обеспечивает ту же экономию, что и при использовании языка Фортран.
A = A + B;
Вариантом языка MATLAB является язык GNU Octave , который расширяет исходный язык расширенными присваиваниями:
A += B;
И MATLAB, и GNU Octave изначально поддерживают операции линейной алгебры, такие как умножение матриц, обращение матриц и численное решение системы линейных уравнений , даже с использованием псевдообратных операций Мура-Пенроуза . [7] [8]
Пример в Nial внутреннего произведения двух массивов можно реализовать с помощью собственного оператора умножения матриц. Если a представляет собой вектор-строку размера [1 n] и b — соответствующий вектор-столбец размера [n 1].
a * b;
Напротив, продукт начального уровня реализуется как:
a .* b;
Внутренний продукт между двумя матрицами, имеющими одинаковое количество элементов, может быть реализован с помощью вспомогательного оператора (:), который преобразует данную матрицу в вектор-столбец, и транспонирования оператор ':
A(:)' * B(:);
rasql
[ редактировать ]Язык запросов расдаман — это язык программирования массивов, ориентированный на базы данных. Например, два массива можно добавить с помощью следующего запроса:
SELECT A + B
FROM A, B
Р
[ редактировать ]Язык R по умолчанию поддерживает парадигму массива . Следующий пример иллюстрирует процесс умножения двух матриц с последующим сложением скаляра (который, по сути, является одноэлементным вектором) и вектора:
> A <- matrix(1:6, nrow=2) # !!this has nrow=2 ... and A has 2 rows
> A
[,1] [,2] [,3]
[1,] 1 3 5
[2,] 2 4 6
> B <- t( matrix(6:1, nrow=2) ) # t() is a transpose operator !!this has nrow=2 ... and B has 3 rows --- a clear contradiction to the definition of 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() creates a vector
[,1] [,2]
[1,] 30 21
[2,] 42 30
Раку
[ редактировать ]Raku поддерживает парадигму массива через свои метаоператоры. [9] В следующем примере показано добавление массивов @a и @b с использованием гипероператора в сочетании с оператором плюс.
[0] > my @a = [[1,1],[2,2],[3,3]];
[[1 1] [2 2] [3 3]]
[1] > my @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: A−1 (на языках MATLAB и GNU Octave: A^-1). Следующие математические утверждения справедливы, когда A представляет собой полного ранга квадратную матрицу :
A^-1 *(A * x)==A^-1 * (b)(A^-1 * A)* x ==A^-1 * bумножения матрицы ( ассоциативность )x = A^-1 * b
где == эквивалентности — оператор отношения .
Предыдущие операторы также являются допустимыми выражениями MATLAB, если третий выполняется раньше остальных (числовые сравнения могут быть ложными из-за ошибок округления).
Если система переопределена – так что A имеет больше строк, чем столбцов – псевдообратный A+ (на языках MATLAB и GNU Octave: 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]
См. также
[ редактировать ]Ссылки
[ редактировать ]- ^ Стефан ван дер Вальт; С. Крис Колберт и Гаэль Варокво (2011). «Массив NumPy: структура для эффективных численных вычислений». Вычисления в науке и технике . 13 (2). ИИЭР: 22–30. arXiv : 1102.1523 . Бибкод : 2011CSE....13b..22V . дои : 10.1109/mcse.2011.37 . S2CID 16907816 .
- ^ Айверсон, Кентукки (1980). «Нотация как инструмент мышления» . Коммуникации АКМ . 23 (8): 444–465. дои : 10.1145/358896.358899 .
- ^ Сурана П. (2006). Мета-компиляция языковых абстракций (Диссертация).
- ^ Кукетаев. «Бенчмарк штрафа за абстракцию данных (DAP) для небольших объектов в Java» . Архивировано из оригинала 11 января 2009 г. Проверено 17 марта 2008 г.
- ^ Хацигеоргиу; Стефанидес (2002). «Оценка производительности и возможностей объектно-ориентированных и процедурных языков программирования». В Блибергере; Штромайер (ред.). Материалы - 7-я Международная конференция по надежным программным технологиям - Ada-Europe'2002 . Спрингер. п. 367. ИСБН 978-3-540-43784-0 .
- ^ Справочное руководство Ada : G.3.1 Реальные векторы и матрицы
- ^ «Руководство GNU Octave. Арифметические операторы» . Проверено 19 марта 2011 г.
- ^ «Документация MATLAB. Арифметические операторы» . Архивировано из оригинала 7 сентября 2010 г. Проверено 19 марта 2011 г.
- ^ «Раздел метаоператоров документации Raku Оператор» .
- ^ «Руководство GNU Octave. Приложение G. Установка Octave» . Проверено 19 марта 2011 г.
- ^ «Ссылка на Armadillo 1.1.8. Примеры синтаксиса Matlab/Octave и концептуально соответствующего синтаксиса Armadillo» . Проверено 19 марта 2011 г.
- ^ «Руководство пользователя Blitz++. 3. Выражения массивов» . Архивировано из оригинала 23 марта 2011 г. Проверено 19 марта 2011 г.