陣列編程

電腦科學中,陣列編程指稱允許向作為整體的一組數值同時應用運算操作的一種解決方案。這種方案經常用於科學和工程上的各種場合(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). 

外部連結