Array
2052
226178631
2008-07-17T04:52:47Z
202.125.143.77
{{Unreferenced|date=February 2007}}
{{For|the DNA microarray in life sciences|DNA microarray}}
{{Linear data structures}}
In [[computer science]] an '''array''' is a [[data structure]] consisting of a group of [[element (mathematics)|element]]s that are accessed by [[index (information technology)|indexing]]. In most [[programming language]]s each element has the same [[data type]] and the array occupies a contiguous area of [[computer memory|storage]].
''The foremost benefit of an array is that it gives a very fast processing to the user. It accesses the data just by reading its index. The processing occurs because all the memory locations in an array are consective. The compiler takes nano seconds to reach to the next consective memory location. (Syed Awais Kazmi)''
Most programming languages have a built-in ''array'' data type, although what is called an array in the language documentation is sometimes really an [[associative array]]. Conversely, the contiguous storage kind of array discussed here may alternatively be called a ''vector'', ''list'',<ref>[[Tcl]] 8 lists are implemented using [[C (programming language)|C]] vectors.</ref> or ''[[Tables|table]]''.<ref>This was the practice in some older languages, e.g. [[COBOL]]: [http://www.csis.ul.ie/cobol/Course/Tables1.htm Using Tables in COBOL]</ref>
Some programming languages support [[array programming]] (e.g., [[APL programming language|APL]], newer versions of [[Fortran]]) which generalises operations and functions to work transparently over arrays as they do with scalars, instead of requiring looping over array members.
'''Multi-dimensional arrays''' are accessed using more than one index: one for each dimension.
Arrays can be classified as ''fixed-sized arrays'' (sometimes known as ''static arrays'') whose size cannot change once their storage has been allocated, or '''[[dynamic array]]s''', which can be resized.
==Properties==
Fixed-size arrays permit efficient (constant time, [[Big O notation|O]](1)) [[random access]]. They are compact data structures, having a constant memory [[Computational overhead|overhead]]. And, on [[CPU]]s which support [[cache]]s, sequential iteration over an array has good [[locality of reference]] because its elements occupy contiguous memory locations. However, when an array is [[random access|randomly accessed]], for example when probing a [[hash table]], locality of reference may be lost.
==Applications==
Because of their performance characteristics, arrays are used to implement other data structures, such as [[heap (data structure)|heaps]], [[hash table]]s, [[deque]]s, [[queue (data structure)|queue]]s, [[stack (data structure)|stacks]], [[String (computer science)|strings]], and [[VList]]s.
Some algorithms store a variable number of elements in part of a fixed-size array, which is equivalent to using [[dynamic array]] with a fixed capacity. See [[dynamic array]] for details.
[[Associative array]]s provide a mechanism for array-like functionality without huge storage overheads when the index values are sparse. Specialized associative arrays with integer keys include [[Patricia trie]]s and [[Judy array]]s.
==Indexing==
{{main|Index (information technology)}}
The valid index values of each dimension of an array are a bounded set of integers. Programming environments that check indexes for validity are said to perform [[bounds checking]].
===Index of the first element===
The index of the first element (sometimes called the ''"origin"'') varies by language. There are three main implementations: ''zero-based'', ''one-based'', and ''n-based'' arrays, for which the first element has an index of zero, one, or a programmer-specified value. The zero-based array is more natural in the root [[machine language]] and was popularized by the [[C (programming language)|C programming language]], in which the abstraction of ''array'' is very weak, and an index ''n'' of a one-dimensional array is simply the offset of the element accessed from the address of the first (or "zero<sup>th</sup>") element (scaled by the size of the element). One-based arrays are based on traditional mathematics notation for [[matrix (mathematics)|matrices]] and most, but not all, mathematical [[sequence]]s. ''n-based'' is made available so the programmer is free to choose the lower bound, which may even be negative, which is most naturally suited for the problem at hand.
The [[Comparison of programming languages (array)]], indicates the base index used by various languages.
Supporters of ''zero-based'' indexing sometimes criticize ''one-based'' and ''n-based'' arrays for being slower. Often this criticism is mistaken when ''one-based'' or ''n-based'' array accesses are optimized with [[common subexpression elimination]] (for single dimensioned arrays) and/or with well-defined [[dope vector]]s (for multi-dimensioned arrays). However, in multidimensional arrays where the net offset into linear memory is computed from all of the indices, ''zero-based'' indexing is more natural, simpler, and faster. [[Edsger W. Dijkstra]] expressed an opinion in this debate: [http://www.cs.utexas.edu/users/EWD/transcriptions/EWD08xx/EWD831.html Why numbering should start at zero].
The 0-based/1-based debate is not limited to just programming languages. For example, the ground-floor of a building is elevator button "0" in France, but elevator button "1" in the USA.
===Indexing Methods===
When the Array is implemented as continuous storage, the index-based access, e.g. to element ''n'', is simply done (for zero-based indexing) by using the address of the first element and adding ''n'' · sizeof(one element). So this is a Θ(1) operation.
But there are cases, where continuous storage might be a bad idea:
* Insertion and deletion should also be a common operation, but continuous storage requires Θ(''n'') time for them. Here a balanced tree can be used, giving Θ(''log n'') for both index access and inserting/deleting. <ref>[http://www.nist.gov/dads/HTML/array.html NIST's Dictionary of Algorithms and Data Structures: Array]</ref><ref>[http://www.chiark.greenend.org.uk/~sgtatham/algorithms/cbtree.html Counted B-Tree]</ref> For example the TextBuffer of [[GTK+]] is implemented on top of a [[B-Tree]], which has lower overhead compared to a binary tree like the [[AVL Tree]].
* Allowing non-integer indices, which is also called an [[Associative array]]. [[PHP]] Arrays are indexed by integers, but can also be accessed by string keys.
==Multi-dimensional arrays==
Ordinary arrays are indexed by a single integer. Also useful, particularly in numerical and graphics applications, is the concept of a ''multi-dimensional array'', in which we index into the array using an ordered list of integers, such as in ''a''[3,1,5]. The number of integers in the list used to index into the multi-dimensional array is always the same and is referred to as the array's ''dimensionality'', and the bounds on each of these are called the array's ''dimensions''. An array with dimensionality ''k'' is often called ''k''-dimensional. One-dimensional arrays correspond to the simple arrays discussed thus far; two-dimensional arrays are a particularly common representation for [[matrix (math)|matrices]]. In practice, the dimensionality of an array rarely exceeds three.
Mapping a one-dimensional array into memory is obvious, since memory is logically itself a (very large) one-dimensional array. When we reach higher-dimensional arrays, however, the problem is no longer obvious. Suppose we want to represent this simple two-dimensional array:
:<math>\mathbf{A} =
\begin{bmatrix}
1 & 2 & 3 \\
4 & 5 & 6 \\
7 & 8 & 9
\end{bmatrix}.
</math>
It is most common to index this array using the ''RC''-convention, where elements are referred in ''row'', ''column'' fashion or <math>A_{row,col}\,</math>, such as:
:<math>A_{1,1}=1,\ A_{1,2}=2,\ \ldots,\ A_{3,2}=8,\ A_{3,3}=9.\,</math>
Common ways to index into multi-dimensional arrays include:
* [[Row-major order]]. Used most notably by statically-declared arrays in [[C (programming language)|C]]. The elements of each row are stored in order.
{| border=1
|-
| 1 || 2 || 3 || 4 || 5 || 6 || 7 || 8 || 9
|}
* [[Column-major order]]. Used most notably in [[Fortran]]. The elements of each column are stored in order.
{| border=1
|-
| 1 || 4 || 7 || 2 || 5 || 8 || 3 || 6 || 9
|}
* Arrays of arrays. Multi-dimensional arrays are typically represented by one-dimensional arrays of [[reference (computer science)|references]] ([[Iliffe vector]]s) to other one-dimensional arrays. The subarrays can be either the rows or columns.
[[Image:Array of array storage.svg|120px|A two-dimensional array stored as a one-dimensional array of one-dimensional arrays.]]
The first two forms are more compact and have potentially better locality of reference, but are also more limiting; the arrays must be ''rectangular'', meaning that no row can contain more elements than any other. Arrays of arrays, on the other hand, allow the creation of ''ragged arrays'', also called ''jagged arrays'', in which the valid range of one index depends on the value of another, or in this case, simply that different rows can be different sizes. Arrays of arrays are also of value in programming languages that only supply one-dimensional arrays as primitives.
In many applications, such as numerical applications working with [[matrix (math)|matrices]], we iterate over rectangular two-dimensional arrays in predictable ways. For example, computing an element of the matrix product '''AB''' involves iterating over a row of '''A''' and a column of '''B''' simultaneously. In mapping the individual array indexes into memory, we wish to exploit locality of reference as much as we can. A compiler can sometimes automatically choose the layout for an array so that sequentially accessed elements are stored sequentially in memory; in our example, it might choose row-major order for '''A''', and column-major order for '''B'''. Even more exotic orderings can be used, for example if we iterate over the [[main diagonal]] of a matrix.
==References==
<references/>
==See also==
{{Wiktionary|array}}
*[[Array slicing]]
*[[Collection class]]
*[[Comparison of programming languages (array)]]
*[[Parallel array]]
*[[Set (computer science)]]
*[[Sparse array]]
*[[Variable-length array]]
*[[wikibooks:Data Structures/Arrays]]
*[[wikibooks:Ada Programming/Types/array]]
==External links==
*[http://www.nist.gov/dads/HTML/array.html NIST's Dictionary of Algorithms and Data Structures: Array]
[[Category:Arrays|*]]
[[Category:Data structures]]
[[bn:অ্যারে]]
[[ca:Vector (programació)]]
[[cs:Pole (datová struktura)]]
[[de:Array]]
[[es:Vector (programación)]]
[[eo:Aro (komputiko)]]
[[fr:Tableau (structure de données)]]
[[id:Larik]]
[[is:Fylki (tölvunarfræði)]]
[[it:Array]]
[[he:מערך (מבנה נתונים)]]
[[hu:Tömb]]
[[nl:Array]]
[[ja:配列]]
[[pl:Tablica]]
[[pt:Array]]
[[ru:Индексный массив]]
[[simple:Array]]
[[sk:Pole (údajová štruktúra)]]
[[sl:Tabela (računalništvo)]]
[[sr:Низ (структура података)]]
[[fi:Taulukko (tietorakenne)]]
[[sv:Array]]
[[tr:Dizi (bilgisayar bilimleri)]]
[[uk:Масив (структура даних)]]
[[zh:数组]]