Array (data structure): Difference between revisions

Revision as of 19:04, 17 December 2003

Revision as of 04:38, 18 December 2003

Line 49:

The first two forms are more compact and have potentially better locality of reference, but are also more limiting; the arrays must be <i>rectangular</i>, meaning that no row or column can contain more elements than any other. Arrays of arrays, on the other hand, allow the creation of <i>ragged arrays</i>, 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.

Finally, in some applications where the data is the same or is missing for most values of the indexes, or for large ranges of indexes, space is saved by not storing an array at all, but having an [[associative array]] with integer keys. There are many specialized data structures specifically for this purpose, such as [[Patricia treestries]] and [[Judy arrays]]. Example applications include [[virtual memory|address translation table]]s and [[routing table]]s.

In many applications, such as numerical applications working with [[matrix (mathematics)|matrices]], we iterate over rectangular two-dimensional arrays, especially two-dimensional arrays, in interesting ways. For example, computing an element of the matrix product <b>AB</b> involves iterating over a row of <b>A</b> and a column of <b>B</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 <b>A</b>, and column-major order for <b>B</b>. Even more exotic orderings can be used, for example if we iterate over the [[main diagonal]] of a matrix.