Программирование массива - Array programming
В Информатика, программирование массива относится к решениям, которые позволяют применять операции ко всему набору значений сразу. Такие решения обычно используются в научный и инженерные настройки.
Современные языки программирования, поддерживающие программирование массивов (также известные как вектор или же многомерный языках) были разработаны специально для обобщения операций над скаляры применять прозрачно к векторов, матрицы, и многомерные массивы. К ним относятся APL, J, Фортран 90, Мата, MATLAB, Аналитика, TK Solver (в виде списков), Октава, р, Силк Плюс, Юля, Язык данных Perl (PDL), Язык Wolfram Language, а NumPy расширение на Python. На этих языках операцию, которая работает с целыми массивами, можно назвать векторизованный операция[1] независимо от того, выполняется ли он на векторный процессор (который реализует векторные инструкции) или нет. Примитивы программирования массивов кратко выражают общие идеи о манипулировании данными. Уровень лаконичности в некоторых случаях может быть поразительным: нередко можно найти язык программирования массивов. однострочные для этого требуется более пары страниц объектно-ориентированного кода.
Понятия массива
Фундаментальная идея программирования массивов состоит в том, что операции применяются сразу ко всему набору значений. Это делает его высокоуровневое программирование модель, поскольку она позволяет программисту думать и оперировать целыми агрегатами данных, не прибегая к явным циклам отдельных скалярных операций.
Кеннет Э. Айверсон описал обоснование программирования массивов (фактически имея в виду APL ) следующее:[2]
большинство языков программирования явно уступают математической нотации и мало используются в качестве инструментов мышления, что, скажем, сочло бы значимым для прикладного математика.
Тезис состоит в том, что преимущества исполняемости и универсальности, присущие языкам программирования, могут быть эффективно объединены в едином согласованном языке с преимуществами математической нотации. Важно отличать трудность описания и изучения нотации от трудности усвоения ее значения. Например, выучить правила вычисления матричного произведения легко, но освоить его значение (например, его ассоциативность, его дистрибутивность над сложением и его способность представлять линейные функции и геометрические операции) - это другой и гораздо более сложный вопрос. .
В самом деле, сам факт внушения нотации может сделать его сложнее для изучения из-за множества свойств, которые он предлагает для исследования.
[...]
Пользователи компьютеров и языков программирования часто в первую очередь озабочены эффективностью выполнения алгоритмов и поэтому могут в целом отклонить многие из представленных здесь алгоритмов. Такое увольнение было бы недальновидным, поскольку четкое изложение алгоритма обычно может использоваться в качестве основы, из которой можно легко вывести более эффективный алгоритм.
В основе программирования и мышления массивов лежит поиск и использование свойств данных, в которых отдельные элементы похожи или смежны. В отличие от объектной ориентации, которая неявно разбивает данные на составные части (или скаляр количества), ориентация массива направлена на группировку данных и применение единообразной обработки.
Ранг функции является важной концепцией для языков программирования массивов в целом, по аналогии с тензор ранг в математике: функции, которые работают с данными, могут быть классифицированы по количеству измерений, в которых они действуют. Например, обычное умножение - это скалярная ранжированная функция, потому что она работает с нульмерными данными (отдельными числами). В перекрестное произведение операция является примером функции ранга вектора, поскольку она работает с векторами, а не со скалярами. Умножение матриц является примером функции 2-го ранга, потому что она работает с 2-мерными объектами (матрицами). Операторы сворачивания уменьшить размерность массива входных данных на одно или несколько измерений. Например, суммирование по элементам сворачивает входной массив на 1 измерение.
Использует
Программирование массивов очень хорошо подходит для неявное распараллеливание; тема многих исследований в настоящее время. Дальше, Intel и совместимые процессоры, разработанные и произведенные после 1997 г., содержали различные расширения набора команд, начиная с MMX и продолжая через SSSE3 и 3DNow!, которые включают элементарные SIMD возможности массива. Обработка массива отличается от параллельная обработка в том, что один физический процессор выполняет операции над группой элементов одновременно, в то время как параллельная обработка направлена на разделение более крупной проблемы на более мелкие (MIMD ), которые будут решаться по частям многочисленными обработчиками. Сегодня все чаще встречаются процессоры с двумя и более ядрами.
Языки
Канонические примеры языков программирования массивов: Фортран, APL, и J. Другие включают: А +, Аналитика, Часовня, IDL, Юля, K, Клонг, Q, Мата, Язык Wolfram Language, MATLAB, MOLSF, NumPy, GNU Octave, PDL, р, Сленг, SAC, Ниал, ZPL и TI-BASIC.
Скалярные языки
В скалярных языках, таких как C и Паскаль, операции применяются только к отдельным значениям, поэтому а+б выражает сложение двух чисел. В таких языках добавление одного массива к другому требует индексации и цикла, кодирование которых утомительно.
за (я = 0; я < п; я++) за (j = 0; j < п; j++) а[я][j] += б[я][j];В языках, основанных на массивах, например в Фортран, вложенный цикл for выше может быть записан в формате массива в одну строку,
а = а + били, альтернативно, чтобы подчеркнуть массивность объектов,
а(:,:) = а(:,:) + б(:,:)Языки массивов
В языках массивов операции обобщены для применения как к скалярам, так и к массивам. Таким образом, а+б выражает сумму двух скаляров, если а и б являются скалярами или суммой двух массивов, если они являются массивами.
Язык массивов упрощает программирование, но, возможно, за счет затрат, известных как штраф за абстракцию.[3][4][5] Поскольку добавления выполняются изолированно от остального кодирования, они могут не дать оптимального результата. эффективный код. (Например, добавления других элементов одного и того же массива могут впоследствии встречаться во время одного и того же выполнения, вызывая ненужные повторные поиски.) Даже самые сложные оптимизирующий компилятор было бы чрезвычайно сложно объединить две или более явно несопоставимых функций, которые могли бы появиться в разных разделах программы или подпрограммах, даже если программист мог бы сделать это легко, агрегируя суммы за один проход по массиву, чтобы минимизировать накладные расходы ).
Ада
Предыдущий код C стал следующим в Ада язык,[6] который поддерживает синтаксис программирования массива.
А := А + B;APL
APL использует односимвольные символы Unicode без синтаксического сахара.
А ← А + BЭта операция работает с массивами любого ранга (включая ранг 0), а также со скаляром и массивом. Dyalog APL расширяет исходный язык с помощью дополненные задания:
А +← BАналитика
Analytica обеспечивает ту же экономию выражения, что и Ada.
А: = А + В;
БАЗОВЫЙ
Дартмутский ОСНОВНОЙ в третьем издании (1966 г.) были операторы MAT для управления матрицами и массивами.
ТусклыйА(4),B(4),C(4)МАТА=1МАТB=2*АМАТC=А+BМАТРАСПЕЧАТАТЬА,B,CМата
Stata Язык программирования матриц Mata поддерживает программирование массивов. Ниже мы проиллюстрируем сложение, умножение, сложение матрицы и скаляра, поэлементное умножение, индексирование и одну из многих функций обратной матрицы Mata.
. мата:: A = (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): // симметричная положительно полуопределенная матрица: I [симметричный] 1 2 3 +-------------------------------------------+ 1 | 0 | 2 | 0 3.25 | 3 | 0 -1.75 .9444444444 | +-------------------------------------------+: конецMATLAB
Реализация в MATLAB обеспечивает ту же экономию, что и при использовании Фортран язык.
А = А + B;Вариантом языка MATLAB является GNU Octave язык, который расширяет исходный язык за счет дополненные задания:
А += B;И MATLAB, и GNU Octave изначально поддерживают операции линейной алгебры, такие как умножение матриц, инверсия матриц, а численное решение система линейных уравнений, даже используя Псевдообратная матрица Мура – Пенроуза.[7][8]
В Ниал Пример внутреннего произведения двух массивов может быть реализован с использованием собственного оператора умножения матриц. Если а вектор-строка размера [1 n] и б - соответствующий вектор-столбец размера [n 1].
а * б;
Внутреннее произведение между двумя матрицами, имеющими одинаковое количество элементов, может быть реализовано с помощью вспомогательного оператора (:), который преобразует заданную матрицу в вектор-столбец, а транспонировать оператор ':
A (:) '* B (:);
rasql
В расдамский язык запросов - это язык программирования массивов, ориентированный на базы данных. Например, два массива можно добавить с помощью следующего запроса:
ВЫБЕРИТЕ A + BFROM A, B
р
В р язык поддерживает парадигма массива по умолчанию. В следующем примере показан процесс умножения двух матриц с последующим сложением скаляра (который, по сути, является одноэлементным вектором) и вектора:
> А <- матрица(1:6, Nrow=2) !!это имеет Nrow=2 ... и А имеет 2 ряды> А [,1] [,2] [,3][1,] 1 3 5[2,] 2 4 6> B <- т( матрица(6:1, Nrow=2) ) # t () - оператор транспонирования !! он имеет nrow = 2 ... и B имеет 3 строки --- явное противоречие с определением A> B [,1] [,2][1,] 6 5[2,] 4 3[3,] 2 1> C <- А %*% 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Математические рассуждения и языковые обозначения
Оператор матричного деления влево кратко выражает некоторые семантические свойства матриц. Как и в скалярном эквиваленте, если (детерминант коэффициента) (матрицы) А не равно нулю, то можно решить (векторное) уравнение А * х = Ь умножив обе части слева на обратный из А: А−1 (на языках MATLAB и GNU Octave: А ^ -1). Следующие математические утверждения верны, когда А это полный ранг квадратная матрица:
A ^ -1 * (A * x) == A ^ -1 * (b)(A ^ -1 * A) * x == A ^ -1 * b(матрица-умножение ассоциативность )х = А ^ -1 * б
куда == эквивалентность реляционный оператор Предыдущие операторы также являются действительными выражениями MATLAB, если третье из них выполняется раньше других (числовые сравнения могут быть ложными из-за ошибок округления).
Если система переопределена - так что А имеет больше строк, чем столбцов - псевдообратная А+ (на языках MATLAB и GNU Octave: pinv (А)) может заменить обратный А−1, следующее:
pinv (A) * (A * x) == pinv (A) * (b)(pinv (A) * A) * x == pinv (A) * b(ассоциативность матричного умножения)x = pinv (A) * b
Однако эти решения не являются ни самыми краткими (например, по-прежнему сохраняется необходимость обозначения переопределенных систем), ни наиболее эффективными с вычислительной точки зрения. Последнее легко понять, если снова рассмотреть скалярный эквивалент а * х = б, для которого решение х = а ^ -1 * б потребовалось бы две операции вместо более эффективной х = б / аПроблема в том, что умножение матриц обычно не выполняется. коммутативный поскольку расширение скалярного решения на матричный случай потребует:
(а * х) / а == б / а(х * а) / а == б / а(для матриц коммутативность не выполняется!)х * (а / а) == б / а(ассоциативность имеет место и для матриц)х = б / а
Язык MATLAB вводит оператор левого деления \ чтобы сохранить существенную часть аналогии со скалярным случаем, тем самым упрощая математические рассуждения и сохраняя краткость:
А (А * х) == А б(А А) * х == А б(ассоциативность имеет место и для матриц, коммутативность больше не требуется)х = А Ь
Это не только пример краткого программирования массивов с точки зрения кодирования, но также и с точки зрения вычислительной эффективности, которая в некоторых языках программирования массивов выигрывает от довольно эффективных библиотек линейной алгебры, таких как АТЛАС или же ЛАПАК.[9][10]
Возвращаясь к предыдущей цитате Айверсона, теперь должно быть очевидным ее обоснование:
Важно отличать трудность описания и изучения нотации от трудности усвоения ее значения. Например, выучить правила вычисления матричного произведения легко, но освоить его значение (например, его ассоциативность, его дистрибутивность над сложением и его способность представлять линейные функции и геометрические операции) - это другой и гораздо более сложный вопрос. На самом деле, из-за того, что нотация наводит на размышления, может показаться, что ее труднее выучить из-за множества свойств, которые она предлагает для исследования.
Сторонние библиотеки
Использование специализированных и эффективных библиотек для предоставления более лаконичных абстракций также распространено в других языках программирования. В C ++ несколько библиотек линейной алгебры используют способность языка операторы перегрузки. В некоторых случаях на очень сжатую абстракцию в этих языках явно влияет парадигма программирования массива, так как Armadillo и Блиц ++ библиотеки делают.[11][12]
Смотрите также
Рекомендации
- ^ Стефан ван дер Вальт; С. Крис Кольбер и Гаэль Вароко (2011). «Массив NumPy: структура для эффективных численных вычислений». Вычислительная техника в науке и технике. IEEE. 13 (2): 22–30. arXiv:1102.1523. Bibcode:2011CSE .... 13b..22V. Дои:10.1109 / mcse.2011.37.
- ^ Айверсон, К. Э. (1980). «Обозначения как инструмент мысли». Коммуникации ACM. 23 (8): 444–465. Дои:10.1145/358896.358899. Архивировано из оригинал на 2013-09-20. Получено 2011-03-22.
- ^ Сурана П. (2006). «Мета-компиляция языковых абстракций» (PDF). Архивировано из оригинал (PDF) на 2015-02-17. Получено 2008-03-17. Цитировать журнал требует
| журнал =(помощь) - ^ Кукетаев. «Тест на наказание за абстракцию данных (DAP) для небольших объектов в Java». Архивировано из оригинал на 2009-01-11. Получено 2008-03-17.
- ^ Хатзигеоргиу; Стефанидес (2002). «Оценка производительности и мощности объектно-ориентированных и процедурных языков программирования». В Блибергере; Strohmeier (ред.). Труды - 7-я Международная конференция по надежным программным технологиям - Ada-Europe'2002. Springer. п. 367. ISBN 978-3-540-43784-0.
- ^ Справочное руководство по Ada: G.3.1 Действительные векторы и матрицы
- ^ "Руководство по GNU Octave. Арифметические операторы". Получено 2011-03-19.
- ^ «Документация MATLAB. Арифметические операторы». Получено 2011-03-19.
- ^ "Руководство по GNU Octave. Приложение G Установка Octave". Получено 2011-03-19.
- ^ «Документация по системе Mathematica 5.2. Ссылки на программное обеспечение». Получено 2011-03-19.
- ^ «Ссылка на Armadillo 1.1.8. Примеры синтаксиса Matlab / Octave и концептуально соответствующего синтаксиса Armadillo». Получено 2011-03-19.
- ^ "Руководство пользователя Blitz ++. 3. Выражения массива". Архивировано из оригинал на 2011-03-23. Получено 2011-03-19.