Программирование массива

В информатике , программированию массив относится к решениям , которые позволяют применение операций ко всей совокупности значений на один раз. Такие решения обычно используются в научных и инженерных целях.

Современные языки программирования, поддерживающие программирование массивов (также известные как векторные или многомерные языки), были разработаны специально для обобщения операций над скалярами для прозрачного применения к векторам , матрицам и многомерным массивам. К ним относятся APL , J , Fortran 90 , Mata, MATLAB , Analytica , TK Solver (в виде списков), Octave , R , Cilk Plus , Julia , Perl Data Language (PDL) и NumPy.расширение для Python . На этих языках операцию, которая работает с целыми массивами, можно назвать векторизованной операцией ^[1], независимо от того, выполняется она на векторном процессоре (который реализует векторные инструкции) или нет. Примитивы программирования массивов кратко выражают общие идеи о манипуляциях с данными. Уровень краткости в некоторых случаях может быть поразительным: нередко можно найти однострочники на языке программирования массивов , для которых требуется несколько страниц объектно-ориентированного кода.

Концепции массива [ править ]

Фундаментальная идея программирования массивов состоит в том, что операции применяются сразу ко всему набору значений. Это делает ее моделью программирования высокого уровня, поскольку она позволяет программисту думать и оперировать целыми агрегатами данных, не прибегая к явным циклам отдельных скалярных операций.

Кеннет Э. Айверсон описал логику программирования массивов (фактически имея в виду APL ) следующим образом: ^[2]

большинство языков программирования явно уступают математической нотации и мало используются в качестве инструментов мышления, что, скажем, сочло бы значимым для прикладного математика.

Тезис состоит в том, что преимущества исполняемости и универсальности, присущие языкам программирования, могут быть эффективно объединены в едином согласованном языке с преимуществами математической нотации. Важно отличать сложность описания и изучения нотации от трудности усвоения ее значения. Например, выучить правила вычисления матричного произведения легко, но освоить его значение (например, его ассоциативность, его дистрибутивность над сложением и его способность представлять линейные функции и геометрические операции) - это другой и гораздо более сложный вопрос. .

В самом деле, из-за того, что нотация наводит на размышления, может показаться, что ее труднее выучить из-за множества свойств, которые она предлагает для исследования.

[...]

Пользователи компьютеров и языков программирования часто озабочены в первую очередь эффективностью выполнения алгоритмов и поэтому могут в целом отказаться от многих алгоритмов, представленных здесь. Такое увольнение было бы недальновидным, поскольку четкое изложение алгоритма обычно можно использовать в качестве основы, из которой можно легко вывести более эффективный алгоритм.

В основе программирования и мышления массивов лежит поиск и использование свойств данных, в которых отдельные элементы похожи или смежны. В отличие от объектной ориентации, которая неявно разделяет данные на составные части (или скалярные величины), ориентация массива ориентирована на группировку данных и применение единообразной обработки.

Ранжирование функции является важным понятием для языков программирования массивов в целом по аналогии с тензорным рангом в математике: функции, которые работают с данными, могут быть классифицированы по количеству измерений, в которых они действуют. Например, обычное умножение - это скалярная ранжированная функция, поскольку она работает с данными нулевой размерности (отдельными числами). Операция перекрестного произведения является примером функции ранга вектора, поскольку она работает с векторами, а не со скалярами. Умножение матриц является примером функции 2-го ранга, поскольку оно работает с 2-мерными объектами (матрицами). Операторы сворачиванияуменьшить размерность массива входных данных на одно или несколько измерений. Например, суммирование по элементам сворачивает входной массив на 1 измерение.

Использует [ редактировать ]

Программирование массивов очень хорошо подходит для неявного распараллеливания ; тема многих исследований в настоящее время. Кроме того, Intel и совместимые процессоры, разработанные и произведенные после 1997 года, содержали различные расширения набора команд, начиная с MMX и заканчивая SSSE3 и 3DNow! , которые включают в себя элементарные возможности массива SIMD . Обработка массивов отличается от параллельной обработки тем, что один физический процессор выполняет операции над группой элементов одновременно, в то время как параллельная обработка направлена ​​на разделение более крупной проблемы на более мелкие ( MIMD), которую нужно решать по частям многочисленными обработчиками. Сегодня все чаще встречаются процессоры с двумя и более ядрами.

Языки [ править ]

Канонические примеры языков программирования массива являются Fortran , АПЗ и Дж . Другие включают: A + , Analytica , Chapel , IDL , Julia , K , Klong, Q , Mata, MATLAB , MOLSF , NumPy , GNU Octave , PDL , R , S-Lang , SAC , Nial , ZPL и TI-BASIC .

Скалярные языки [ править ]

В скалярных языках, таких как C и Pascal , операции применяются только к отдельным значениям, поэтому a + b выражает сложение двух чисел. В таких языках добавление одного массива к другому требует индексации и цикла, кодирование которых утомительно.

for  ( i  =  0 ;  i  <  n ;  i ++ )  for  ( j  =  0 ;  j  <  n ;  j ++ )  a [ i ] [ j ]  + =  b [ i ] [ j ];

В языках, основанных на массивах, например в Фортране , вложенный цикл for выше может быть записан в формате массива в одну строку,

а  =  а  +  б

или, альтернативно, чтобы подчеркнуть массивность объектов,

а (:, :)  =  а (:, :)  +  b (:, :)

Языки массивов [ править ]

В языках массивов операции обобщены для применения как к скалярам, ​​так и к массивам. Таким образом, a + b выражает сумму двух скаляров, если a и b являются скалярами, или сумму двух массивов, если они являются массивами.

Язык массивов упрощает программирование, но, возможно, за счет потери абстракции . ^{[3] [4] [5]} Поскольку добавления выполняются изолированно от остальной части кодирования, они могут не создавать оптимально наиболее эффективный код. (Например, добавления других элементов одного и того же массива могут впоследствии встречаться во время одного и того же выполнения, вызывая ненужные повторные поиски.) Даже самому сложному оптимизирующему компилятору будет чрезвычайно трудно объединить две или более явно несопоставимых функции, которые могут появиться в различные программные разделы или подпрограммы, даже если программист мог бы сделать это легко, агрегируя суммы за один проход по массиву, чтобы минимизироватьнакладные расходы ).

Ада [ править ]

Предыдущий код C стал следующим на языке Ada ^[6], который поддерживает синтаксис программирования массивов.

А  : =  А  +  В ;

APL [ править ]

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                

Мата [ править ]

Язык программирования матриц Stata Mata поддерживает программирование массивов. Ниже мы проиллюстрируем сложение, умножение, сложение матрицы и скаляра, поэлементное умножение, индексирование и одну из многих функций обратной матрицы Mata.

. мата :: А = ( 1 , 2 , 3 ) \ ( 4 , 5 , 6 ): А 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 ) // Матрица единиц 3 на 2: 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: ГРАММ 1  2  + ----------- +  1 | 9  9 | 2 | 18  18 | + ----------- +: H = F [( 2 \ 1 ), ( 1 , 2 )] // Индексирование для получения подматрицы F и: // переключаем строки 1 и 2: H 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 позволяет использовать ту же экономию, что и при использовании языка Fortran .

А = А + В ;    

Вариантом языка MATLAB является язык GNU Octave , который расширяет исходный язык с помощью расширенных назначений :

А  + =  В ;

И MATLAB, и GNU Octave изначально поддерживают операции линейной алгебры, такие как умножение матриц, обращение матриц и численное решение системы линейных уравнений , даже с использованием псевдообратной матрицы Мура – ​​Пенроуза . ^{[7] [8]}

Ниал пример скалярного произведения двух массивов может быть реализован с использованием родного оператора умножения матриц. If a- вектор-строка размера [1 n] и bсоответствующий вектор-столбец размера [n 1].

а * б;

Внутреннее произведение между двумя матрицами, имеющими одинаковое количество элементов, может быть реализовано с помощью вспомогательного оператора (:), который преобразует заданную матрицу в вектор-столбец, и оператора транспонирования' :

A (:) '* B (:);

rasql [ править ]

Язык rasdaman запрос представляет собой базу данных , ориентированных на массив языка программирования. Например, два массива можно добавить с помощью следующего запроса:

ВЫБЕРИТЕ  A  +  B ИЗ  A ,  B

R [ править ]

Язык 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

Математические рассуждения и языковые обозначения [ править ]

Оператор матричного деления влево кратко выражает некоторые семантические свойства матриц. Как и в скалярном эквивалент, если ( определитель из) коэффициента (матрицы) 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 . ^[9]

Возвращаясь к предыдущей цитате Айверсона, теперь должно быть очевидным ее обоснование:

Важно отличать сложность описания и изучения нотации от трудности усвоения ее значения. Например, выучить правила вычисления матричного произведения легко, но освоить его значение (например, его ассоциативность, его дистрибутивность над сложением и его способность представлять линейные функции и геометрические операции) - это другой и гораздо более сложный вопрос. . В самом деле, из-за того, что нотация наводит на размышления, может показаться, что ее труднее выучить из-за множества свойств, которые она предлагает для исследования.

Сторонние библиотеки [ править ]

Использование специализированных и эффективных библиотек для предоставления более лаконичных абстракций также распространено в других языках программирования. В C ++ несколько библиотек линейной алгебры используют способность языка перегружать операторы . В некоторых случаях очень краткая абстракция в этих языках явно зависит от парадигмы программирования массива, как это делают библиотеки Armadillo и Blitz ++ . ^{[10] [11]}

См. Также [ править ]

• Нарезка массива
• Список языков программирования массивов

Ссылки [ править ]

Внешние ссылки [ править ]

• Программирование "без вонючих петель"
• Открытие языков массивов