陣列編程
![本頁使用了標題或全文手工轉換](http://images.weserv.nl/?url=//upload.wikimedia.org/wikipedia/commons/thumb/c/cd/Zh_conversion_icon_m.svg/35px-Zh_conversion_icon_m.svg.png)
在計算機科學中,陣列編程指稱允許向作為整體的一組數值同時應用運算操作的一種解決方案。這種方案經常用於科學和工程上的各種場合(settings)。
支持陣列編程的現代編程語言(也叫做向量或多維語言),已經具體的工程設計為將在標量上的運算,推廣為透明的適用於向量、矩陣和高維數組。其典型例子是APL/J語言、Fortran 90,其他例子還包括:Analytica、Cilk Plus、Julia、Mata、MATLAB、NumPy(Python語言擴展)、Octave、PDL、R、TK 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),而由多個處理器來逐個的解決。帶有兩個或更多核心的處理器現今日益常見。
陣列語言
陣列編程語言的典範例子包括APL/J語言、Fortran 90。其他例子包括:A+、Analytica、Chapel、Futhark、IDL、Julia、K、Klong、Mata、MATLAB、MOLSF、Nial、NumPy、Octave、PDL、Q、R、S-Lang、SAC、Wolfram語言、ZPL等。
在陣列語言中,運算被推廣為應用到標量和數組二者之上。因此a+b
,在a
和b
是標量之時,可以表達兩個標量的和;在它們是數組之時,也可以表達兩個數組的和。陣列語言簡化了編程但可能有着叫做「抽象懲罰」的代價[4][5][6]。因為這些加法是孤立於代碼餘下部份而運行的,它們可能不會生成優化的最有效率代碼。例如,相同數組的其他元素的加法,可能在這次運行中隨後遇到,導致不必須的重複查找。
標量語言擴展
在標量語言如C和Pascal語言中,運算只能應用在單一數值上,所以 a+b
表達兩個數值的加法。在這種語言中,一個數組到另一個數組的加法需要索引和循環,這種編碼是冗長的:
for (i = 0; i < n; i++)
for (j = 0; j < n; j++)
a[i][j] += b[i][j];
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
前面的C代碼可以用支持數組編程語法的Ada語言寫為如下[7]:
A := A + B;
在基於數組的Fortran 90中,上述的嵌套for循環可以用數組格式以一行寫為:
a = a + b
或者使用一種替代形式,強調對象的數組本質:
a(:,:) = a(:,:) + b(:,:)
APL
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的光柵查詢語言是面向數據庫的陣列編程語言。例如,兩個數組可以使用如下查詢來相加:
SELECT A + B
FROM A, B
參見
引用
- ^ 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.
- ^ Michael Schidlowsky. Java and K. [2008-01-23]. (原始內容存檔於2017-11-01).
- ^ 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).
- ^ Surana P. Meta-Compilation of Language Abstractions. (PDF). 2006 [2008-03-17]. (原始內容 (PDF)存檔於2015-02-17).
- ^ Kuketayev. The Data Abstraction Penalty (DAP) Benchmark for Small Objects in Java.. [2008-03-17]. (原始內容存檔於2009-01-11).
- ^ 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.
- ^ Ada Reference Manual (頁面存檔備份,存於網際網路檔案館): G.3.1 Real Vectors and Matrices (頁面存檔備份,存於網際網路檔案館)
- ^ Dyalog (頁面存檔備份,存於網際網路檔案館)
- ^ GNU Octave Manual. Arithmetic Operators.. [2011-03-19]. (原始內容存檔於2010-12-25).
- ^ MATLAB documentation. Arithmetic Operators.. [2011-03-19]. (原始內容存檔於2011-09-25).
外部連結
- "No stinking loops" programming (頁面存檔備份,存於網際網路檔案館)
- Discovering Array Languages
- what is Array (頁面存檔備份,存於網際網路檔案館)
|
|