阵列编程

计算机科学中,阵列编程指称允许向作为整体的一组数值同时应用运算操作的一种解决方案。这种方案经常用于科学和工程上的各种场合(settings)。

支持阵列编程的现代编程语言(也叫做向量多维语言),已经具体的工程设计为将在标量上的运算,推广为透明的适用于向量矩阵和高维数组。其典型例子是APL/J语言、Fortran 90,其他例子还包括:Analytica英语Analytica (software)Cilk PlusJuliaMataMATLABNumPyPython语言扩展)、OctavePDL英语Perl Data LanguageRTK Solver英语TK Solver(作为列表)、Wolfram语言等。在这些语言中,在一个整体的阵列上的运算可以叫做“向量化”运算[1],无论它是否执行于向量处理器(它实现了向量指令)。阵列编程原语(primitive)简明的表达了关于数据运算的宽泛想法。这种简明程度在特定情况下可能是戏剧性的:不难发现与阵列编程语言的一行程序相对应Java程序有时需要很多页代码[2]

阵列的概念

阵列编程背后的基本思想,是将运算同时应用于作为整体的一组数值。这使得它成为了一种高级编程语言模型,因为它允许编程者在整个数据聚集上思考和操作,而不用诉诸显式的循环和单独的标量运算。

Kenneth E. Iverson在《以符号表示作为思考工具》中描述了阵列编程(实指APL)背后的原理[3]

多数编程语言明显的比不上数学符号表示(notation),而且很少有应用数学家认为它是重要的思考工具。本论主旨,是在编程语言中找到的可执行性和普遍性的优点,和数学符号表示提供的优点,二者能有效的结合起来,形成单一且融洽的语言。将描述和学习一段符号表示的难度,和掌握它的含义的难度,二者区分开来是很重要的。例如,学习计算一个矩阵乘法的规则是容易的,而理解它的内涵(比如它的结合律、在加法上的分配律和它表达线性函数和几何运算的能力),是不同而且更加困难的事情。

实际上,一个符号表示强烈的启示性,使得它更加难以学习,因为它提示了有很多属性要探索。

[...]

计算机和编程语言的用户,通常主要关心算法的执行效率,从而可能仓促的不去理会这里提出的算法。这种忽略是短视的,因为对算法的清晰陈述,通常可以作为一种基础,籍此能更容易的推导出更高效的算法。

阵列编程和思考的背后基础,是找到并利用数据的某种属性(property),它使得单独元素之间有相似性或相毗邻。不同于面向对象范型,它隐含的将数据分解成它的各个构成部件(或标量数量),面向阵列范型注重组合(group)数据并应用统一(uniform)处理。

函数的(rank)是阵列编程的重要一般概念,类似于数学中的张量秩:在数据上运算的函数,可以按它们所作用的数据的维度来分类。例如,普通的乘法是标量秩函数,因为它运算于零维数据(个体的数值)。叉积运算是向量秩函数的例子,因为它运算于向量而非标量。矩阵乘法是2秩函数的例子,因为它运算于二维对象(矩阵)。缩减(collapse)运算将输入数据阵列的维度减少一或多维。例如,在元素上的合计运算将输入阵列缩减1维。

用途

阵列编程非常适合于隐式并行英语implicit parallelization;这是当下的广泛研究主题。进一步的说,在1997年后开发和生产的Intel和兼容的CPU都包含各种指令集扩展,开始自MMX和随后的SSSE3以及3DNow!,它们介入了基本的SIMD阵列功能。阵列处理不同于并行处理之处在于,它是一个物理的处理器在一组计算单元上同时进行运算;而并行运算目标是把大型问题分解成更小的问题(MIMD),而由多个处理器来逐个的解决。带有两个或更多核心的处理器现今日益常见。

阵列语言

阵列编程语言的典范例子包括APL/J语言、Fortran 90。其他例子包括:A+Analytica英语Analytica (software)Chapel英语Chapel (programming language)FutharkIDLJuliaK、Klong、MataMATLABMOLSF英语MOLSFNial英语NialNumPyOctavePDL英语Perl Data LanguageQ英语Q (programming language from Kx Systems)RS-Lang英语S-LangSACWolfram语言ZPL英语ZPL (programming language)等。

在阵列语言中,运算被推广为应用到标量和数组二者之上。因此a+b,在ab是标量之时,可以表达两个标量的和;在它们是数组之时,也可以表达两个数组的和。阵列语言简化了编程但可能有着叫做“抽象惩罚”的代价[4][5][6]。因为这些加法是孤立于代码余下部份而运行的,它们可能不会生成优化的最有效率代码。例如,相同数组的其他元素的加法,可能在这次运行中随后遇到,导致不必须的重复查找。

标量语言扩展

在标量语言如CPascal语言中,运算只能应用在单一数值上,所以 a+b表达两个数值的加法。在这种语言中,一个数组到另一个数组的加法需要索引和循环,这种编码是冗长的:

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

Dartmouth英语Dartmouth BASIC 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

前面的C代码可以用支持数组编程语法的Ada语言写为如下[7]

A := A + B;

在基于数组的Fortran 90中,上述的嵌套for循环可以用数组格式以一行写为:

a = a + b

或者使用一种替代形式,强调对象的数组本质:

a(:,:) = a(:,:) + b(:,:)

APL

APL使用单一字符Unicode符号而没有语法糖

A  A + B

这个运算作用于任意秩(包括0秩)的两个数组,和一个标量与一个数组。Dyalog APL[8]向最初的语言扩展了增广赋值

A + B

MATLAB

MATLAB中的实现允许同使用Fortran语言一样的经济型表达式:

A = A + B;

GNU Octave语言是MATLAB语言的一种变体,它向最初的语言扩展了增广赋值

A += B;

MATLAB和GNU Octave二者都固有的支持线性代数运算比如矩阵乘法、逆矩阵和一些线性方程组的数值解,甚至使用了摩尔-彭若斯广义逆[9][10]

两个数组的内积的例子可以使用固有矩阵乘法运算来实现。如果a是一个大小为[1 n]的行向量而b是对应的一个大小为[n 1]的列向量。

 a * b;

两个有相同数目元素的矩阵的内积有可以使用辅助算符(:),它将一个给定矩阵改造成一个列向量,和转置算符'来实现:

 A(:)' * B(:);

R

R语言缺省的支持阵列范型。下列例子展示计算两个矩阵的乘法和随后的一个标量(实际上是一个元素的向量)与一个向量的加法的过程:

> A <- matrix(1:6, nrow=2)
> A                # 设置了nrow=2 ... 而且A有2行
     [,1] [,2] [,3]
[1,]    1    3    5
[2,]    2    4    6
> B <- t( matrix(6:1, nrow=2) )  # t()是转置算子
> B               # 设置了nrow=2 ... 而且B有3行   
     [,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

rasql

Rasdaman英语Rasdaman光栅查询语言是面向数据库的阵列编程语言。例如,两个数组可以使用如下查询来相加:

SELECT A + B
FROM   A, B

参见

引用

  1. ^ Stéfan van der Walt; S. Chris Colbert & Gaël Varoquaux. The NumPy array: a structure for efficient numerical computation. Computing in Science and Engineering (IEEE). 2011, 13 (2): 22–30. Bibcode:2011CSE....13b..22V. arXiv:1102.1523 . doi:10.1109/mcse.2011.37. 
  2. ^ Michael Schidlowsky. Java and K. [2008-01-23]. (原始内容存档于2017-11-01). 
  3. ^ Iverson, K. E. Notations as a Tool of Thought.. Communications of the ACM. 1980, 23 (8): 444–465 [2011-03-22]. doi:10.1145/358896.358899. (原始内容存档于2013-09-20). 
  4. ^ Surana P. Meta-Compilation of Language Abstractions. (PDF). 2006 [2008-03-17]. (原始内容 (PDF)存档于2015-02-17). 
  5. ^ Kuketayev. The Data Abstraction Penalty (DAP) Benchmark for Small Objects in Java.. [2008-03-17]. (原始内容存档于2009-01-11). 
  6. ^ Chatzigeorgiou; Stephanides. Evaluating Performance and Power Of Object-Oriented Vs. Procedural Programming Languages. Blieberger; Strohmeier (编). Proceedings - 7th International Conference on Reliable Software Technologies - Ada-Europe'2002. Springer. 2002: 367. ISBN 978-3-540-43784-0. 
  7. ^ Ada Reference Manual页面存档备份,存于互联网档案馆): G.3.1 Real Vectors and Matrices页面存档备份,存于互联网档案馆
  8. ^ Dyalog页面存档备份,存于互联网档案馆
  9. ^ GNU Octave Manual. Arithmetic Operators.. [2011-03-19]. (原始内容存档于2010-12-25). 
  10. ^ MATLAB documentation. Arithmetic Operators.. [2011-03-19]. (原始内容存档于2011-09-25). 

外部链接