Array - Revision history

Brian at 03:08, 17 April 2012

2012-04-17T03:08:30Z

Brian at 21:27, 1 January 2012

2012-01-01T21:27:12Z

Brian at 22:19, 5 March 2011

2011-03-05T22:19:41Z

Brian at 19:03, 5 March 2011

2011-03-05T19:03:44Z

Brian: Created page with "The '''array''' is a data structure considered fundamental in imperative programming languages. We shall take the definition of the term to be ''a collection of objects, all ..."

2011-03-05T07:17:07Z

Created page with "The '''array''' is a data structure considered fundamental in imperative programming languages. We shall take the definition of the term to be ''a collection of objects, all ..."

New page

The '''array''' is a data structure considered fundamental in [[imperative programming language]]s. We shall take the definition of the term to be ''a collection of objects, all of the same size and type, regularly spaced in random-access memory (RAM)''. Because the objects are regularly spaced in memory, their addresses occur in arithmetic progression. Therefore, when we assign the object at the lowest memory address an ''index'' of, for example, zero, the next object after that an index of one, and so on up to the <math>n</math>th object, which receives an index of <math>n-1</math>, we can access any object in the array in constant time just by knowing the index (using the formula for the <math>i</math>th term of an arithmetic progression). This property makes the array data structure useful and applicable to a wide variety of different algorithms, and many other data structures contain arrays, using them to organize information internally. In particular, an array is often the ideal data structure for a finite [[sequence]].

In [[functional programming language]]s based upon the [[lambda calculus]], arrays are not fundamental ingredients, as the lambda calculus is not aware of the organization of computer memory. Nevertheless, they may have language support for the sake of efficiency.

==Terminology==
The '''size''' of an array is the number of objects it contains. The stored objects themselves are known as '''elements''', '''entries''', or '''values''' of the array. An element of an array is uniquely identified in that array by an '''index''', which is usually a natural number (as in the preceding paragraph), but may be any kind of object taken from a finite well-ordered set. (For example, the Pascal programming language allows the use of characters as array indices, as characters may be well-ordered according to their [[ASCII]] values; it allows boolean indices, with false = 0 and true = 1; but it does not allow reals. All programming languages that support arrays support natural numbers as indices, and some do not support any other type of index.) ''Indices do '''not''' appear in the array itself''; the choice of index is an arbitrary convention we use to abstract the locations of elements in arrays, without using the addresses themselves, which can be cumbersome to work with and may change every time a program is run and memory for the array allocated. If an element of an array is located at index <math>i</math>, the element immediately following it in the array, if there is one, occurs at an index equal to the successor of <math>i</math>; if <math>i</math> is an integer then this is <math>i+1</math>.

A '''segment''' or '''slice''' of an array consists of exactly those values of the array occurring at indices taken from a contiguous range. For example, we may choose the entire array, or we may choose no elements at all, or we may choose the fifth element, or we may choose the ninth, tenth, eleventh, and twelfth elements; all these are considered segments or slices.

==Address computation==
If each element in an array occupies <math>x</math> bytes of memory, then the difference in addresses of consecutive elements in the array is some value <math>d \geq x</math>. It may be exactly <math>x</math>, in which case the array takes up exactly the same amount of space as its individual elements combined, but, depending on the programming language, <math>d</math> may also be somewhat greater than <math>x</math> in order to keep the elements word-aligned. (In practice, most compilers will ''not'' choose <math>d > x</math>, simply because it wastes space.)

Now, suppose this array is indexed by members of some finite well-ordered set <math>I</math>. Define a bijection <math>f</math> between <math>I</math> and <math>\mathbb{N}</math> (starting from zero) as follows: since <math>I</math> is well-ordered, it has a least element <math>l</math>; we shall write <math>f(0) = l</math>. Then, either <math>I</math> is exhausted, or it contains a next smaller element, <math>l'</math>; then we shall write <math>f(1) = l'</math>, and so on until the elements of <math>I</math> have been put into order in one-to-one correspondence with <math>\{0, 1, ..., n-1\}</math> (where <math>n = |I|</math>).

Furthermore, suppose that the first element in the array, the element located at the lowest memory address, in fact has address <math>a</math>. Then the element located at index <math>i</math> will have address <math>a+df^{-1}(i)</math>. Likewise, if we know the address <math>a'</math> of an element, then its index is given by <math>f((a'-a)/d)</math>.

For example, suppose that a program is counting the number of words that start with each letter of the Latin alphabet. Then it will probably have an array indexed by the alphabet in which the values are, say, integers 4 bytes long. So the element at index '''a''' holds the number of words that start with '''a''', the element at index '''b''' holds the number of words that start with '''b''', and so on up to '''z'''. Then, we will have <math>f(x)</math> defined to be the <math>(x+1)</math>th letter of the alphabet, hence <math>f(0) =</math> '''a''', ..., <math>f(25) =</math> '''z'''.
So suppose that the first element of the array (the count of words starting with '''a''') has address 92631507. Then, suppose we wish to look up the number of words starting with the letter '''s'''. '''s''' is the 19th letter of the alphabet, so we will find this entry at address 92631507+4×18 = 92631579. Likewise, suppose we wish to know which element is located at address 92631555. To do this, we let <math>x = 92631555-92631507 = 48</math>, whence <math>x/4 = 12</math> and the index we seek is <math>f(12)</math>, the thirteenth letter of the alphabet, which is '''m'''. (This example illustrates that it's really not as complicated as it sounds; the mapping of indices to addresses is very intuitive.)

==Multidimensional arrays==
The visual interpretation of the array is, perhaps, a line of boxes, each of which is a variable (a space in memory that holds one of the array's elements). So, for example, suppose there were fifty people in a line and we wanted to store their names. Then we could assign each person a number according to his or her position in the line, and use these as indices to an array with 50 elements, each of which holds the name of one person (presumably as a fixed-length [[string]] or a [[pointer]] to a variable-length string)?

It becomes clear fairly quickly, however, that this mode of thinking is severely limiting. For example, suppose that there are 50 rows of 50 occupied chairs each, and we want to store the names of all 2500 people listening to a speech. What do we do now? One method is to imagine that we asked the first row to stand up and form a line off to the left side, then we asked the second row to stand up and line up behind the people who used to be in the first row, in such a way that if Alice is originally seated to the left of Bob, she will end up in front of Bob in the line; and so on down until all 2500 people have lined up, and we assign the number 0 to the first person in the line, 1 to the second person, and eventually 2499 to the last person. (In a bird's eye view facing the podium, we are assigning IDs in English reading order: left to right then top to bottom.) Then we could use an array indexed by the integers from 0 to 2499 to hold information about the names of all the people attending.

But this is cumbersome. Suppose that the guest sitting in the 12th row and the 34th column is randomly selected to win a prize, and we wish to call him out by name. Then we have to compute that his ID is <math>(34-1) + 50\cdot(12-1) = 583</math>, and look up the array element at index 583. It would be much more convenient if we could simply use the ordered pair <math>(34,12)</math> as an index --- not a location along a ''line'', but the coordinates of a point in a ''plane''. The array is being used, after all, to represent a ''table'' or ''matrix'' or ''grid'' of things, not a ''line''.

This, in fact, is the principle behind a '''multidimensional array''', an array indexed by <math>n</math>-tuples, where <math>n > 1</math>. (Such an array is said to be <math>n</math>-dimensional.) It is not hard to form a bijection between tuples and <math>\mathbb{N}</math>; in this example, we have a two-dimensional array with <math>f(0) = (1,1)</math>, <math>f(1) = (1,2)</math>, ..., <math>f(49) = (1,50)</math>, <math>f(50) = (2,1)</math>, ..., <math>f(99) = (2,50)</math>, ..., <math>f(2450) = (50,1)</math>, ..., <math>f(2499) = (50,50)</math>. The point is that, in order to ease the cognitive burden on the programmer and aid visualization, the details of the address translation should be taken care of by the compiler and hidden from the programmer. Many programming languages support arrays with several dimensions; these are particularly important in [[dynamic programming]]. The size of a multidimensional array is the product of the sizes of the individual sets whose Cartesian product was taken to form the set of tuples as indices for the array. The elements of the tuple need not be all of the same type.

(It is important to remember that a multidimensional array is still, in a sense, a line of values sitting in memory, and that the convention of indexing them by tuples is only for convenience and has no real existence within the machine. Accordingly, the interpretation of the array determines its abstract nature, and not ''vice versa''; whether the first element of an ordered pair as the index represents the row or the column is irrelevant as long as one is consistent, and they may represent, in fact, whatever the programmer wants; the first element may identify a star system and the second one of the stars in the system identified by the first, for example, or the interpretation may be totally abstract, with no physical nature.)

← Older revision		Revision as of 03:08, 17 April 2012
Line 2:		Line 2:

	In [[functional programming language]]s based upon the [[lambda calculus]], arrays are not fundamental ingredients, as the lambda calculus is not aware of the organization of computer memory. Nevertheless, they may have language support for the sake of efficiency.		In [[functional programming language]]s based upon the [[lambda calculus]], arrays are not fundamental ingredients, as the lambda calculus is not aware of the organization of computer memory. Nevertheless, they may have language support for the sake of efficiency.
		+
		+	In some programming languages (notably PHP), all arrays are [[Associative array\|associative]] by default. An associative array is not a type of array, but a more complex data structure named in analogy to the array.

	==Terminology==		==Terminology==

← Older revision		Revision as of 21:27, 1 January 2012
Line 7:		Line 7:

	A '''segment''' or '''slice''' of an array consists of exactly those values of the array occurring at indices taken from a contiguous range. For example, we may choose the entire array, or we may choose no elements at all, or we may choose the fifth element, or we may choose the ninth, tenth, eleventh, and twelfth elements; all these are considered segments or slices.		A '''segment''' or '''slice''' of an array consists of exactly those values of the array occurring at indices taken from a contiguous range. For example, we may choose the entire array, or we may choose no elements at all, or we may choose the fifth element, or we may choose the ninth, tenth, eleventh, and twelfth elements; all these are considered segments or slices.
		+
		+	===Indexing convention===
		+	The vast majority of arrays encountered in practice are '''zero-indexed''' or '''zero-based'''; that is, they are indexed with consecutive natural numbers starting from zero. This is probably due to the influence of C, in which arrays are formalisms constructed over pointers to their initial elements and indices are merely offsets, so that index 0 represents the initial element itself.
		+
		+	In theoretical contexts, arrays are again often zero-indexed, but are also often '''one-based''' or '''one-indexed''', that is, indexed with consecutive natural numbers starting from one. The author usually chooses whichever is more convenient.
		+
		+	Also, note that sometimes a zero-indexed array used in practice is treated as a one-indexed array, and the element at index zero is not used, or it is allowed to exist only for the sake of convenience, ''i.e.'', as a sentinel value, or a buffer against out-of-bounds accesses.

	==Address computation==		==Address computation==

@@ Line 54: / Line 54: @@
 * ''Map'': Apply the same unary function to every element in the array, either replacing it by the result of the function, or creating a new array that contains all the return values of the function, without rearranging them. (An example would be converting a string to uppercase.)
 * ''Reduce'': Consider each element of the array in turn, passing it to a binary function to update an accumulator, until all elements have been considered, and then return the accumulator. (Examples would be summing the array or finding its maximum element.)
 [[Category:Data structures]]

@@ Line 25: / Line 25: @@
 But this is cumbersome. Suppose that the guest sitting in the 12th row and the 34th column is randomly selected to win a prize, and we wish to call him out by name. Then we have to compute that his ID is <math>(34-1) + 50\cdot(12-1) = 583</math>, and look up the array element at index 583. It would be much more convenient if we could simply use the ordered pair <math>(34,12)</math> as an index --- not a location along a ''line'', but the coordinates of a point in a ''plane''. The array is being used, after all, to represent a ''table'' or ''matrix'' or ''grid'' of things, not a ''line''.
 This, in fact, is the principle behind a '''multidimensional array''', an array indexed by <math>n</math>-tuples, where <math>n > 1</math>. (Such an array is said to be <math>n</math>-dimensional.) It is not hard to form a bijection between tuples and <math>\mathbb{N}</math>; in this example, we have a two-dimensional array with <math>f(0) = (1,1)</math>, <math>f(1) = (1,2)</math>, ..., <math>f(49) = (1,50)</math>, <math>f(50) = (2,1)</math>, ..., <math>f(99) = (2,50)</math>, ..., <math>f(2450) = (50,1)</math>, ..., <math>f(2499) = (50,50)</math>. The point is that, in order to ease the cognitive burden on the programmer and aid visualization, the details of the address translation should be taken care of by the compiler and hidden from the programmer. Many programming languages support arrays with several dimensions; these are particularly important in [[dynamic programming]]. The size of a multidimensional array is the product of the sizes of the individual sets whose Cartesian product was taken to form the set of tuples as indices for the array. The elements of the tuple need not be all of the same type.
 (It is important to remember that a multidimensional array is still, in a sense, a line of values sitting in memory, and that the convention of indexing them by tuples is only for convenience and has no real existence within the machine. Accordingly, the interpretation of the array determines its abstract nature, and not ''vice versa''; whether the first element of an ordered pair as the index represents the row or the column is irrelevant as long as one is consistent, and they may represent, in fact, whatever the programmer wants; the first element may identify a star system and the second one of the stars in the system identified by the first, for example, or the interpretation may be totally abstract, with no physical nature.)