阵列编程

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

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

阵列的概念编辑

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

Kenneth E. Iverson将阵列编程(实指APL)背后的原理描述如下[3]

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

实际上,一个表示法的强烈启示性使得它更加难学,因为它提示了有很多特性(property)要探索。

[...]

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

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

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

用途编辑

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

语言编辑

阵列编程语言的典范例子包括APLFortran 90J语言。其他例子包括:A+AnalyticaChapelIDLJuliaK、Klong、Mata、MATLABMOLSFNialNumPyOctavePDLQRS-LangSACWolfram语言ZPL等。

标量语言编辑

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

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

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

a = a + b

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

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

阵列语言编辑

在阵列语言中,运算被推广为应用到标量和数组二者之上。因此a+b可以表达两个标量的和,如果a和b是标量;也可以表达两个数组的和,如果它们是数组。

阵列语言简化了编程但可能有着叫做“抽象惩罚”的代价[4][5][6]。因为这些加法是孤立于代码余下部份而运行的,它们可能不会生成优化的最有效率代码。(例如,相同数组的其他元素的加法在这次运行中可能随后遇到,导致不必须的重复查找。)

Ada编辑

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

A := A + B;

APL编辑

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

A  A + B

这个运算作用于任意秩(包括0秩)的两个数组,和一个标量与一个数组。Dyalog 页面存档备份,存于互联网档案馆APL向最初的语言扩展了增广赋值

A + B

Analytica编辑

Analytica提供与Ada一样的经济型表达式:

A := A + B;

BASIC编辑

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

Mata编辑

Stata的矩阵编程语言Mata支持阵列编程。下面例子展示了加法、乘法、一个矩阵和一个标量的加法、逐个元素的乘法、下标和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编辑

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

A = A + B;

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

A += B;

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

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

 a * b;

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

 A(:)' * B(:);

rasql编辑

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

SELECT A + B
FROM   A, B

R编辑

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

参见编辑

引用编辑

  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. ^ GNU Octave Manual. Arithmetic Operators.. [2011-03-19]. (原始内容存档于2010-12-25). 
  9. ^ MATLAB documentation. Arithmetic Operators.. [2011-03-19]. (原始内容存档于2011-09-25). 

外部链接编辑