Iliffe vector
From Wikipedia, the free encyclopedia
In computer programming, an Iliffe vector is a data structure used to implement multi-dimensional arrays. Named after John K. Iliffe, an Iliffe vector for an n dimensional array (where n>2) consists of a vector (or 1 dimensional array) of pointers to an n−1 dimensional array. They are often used to avoid the need for expensive multiplication operations when performing address calculation on an array element. They can also be used to implement triangular arrays, or other kinds of irregularly shaped arrays.
Their disadvantages include the need for multiple dependent pointer indirections to access an element, and the extra work associated with determining the next row in an n-dimensional array to allow an optimising compiler to prefetch it. Both of these cause slow downs on systems where the CPU is significantly faster than main memory.
The Iliffe vector for a 2-dimensional array is simply a vector of pointers to vectors of data, i.e., the Iliffe vector represents the columns of an array where each column element is a pointer to a row vector.
Multidimensional arrays in languages such as Java and Atlas Autocode are implemented as Iliffe vectors.
[edit] References
- John K. Iliffe (1961). "The Use of The Genic System in Numerical Calculations". Annual Review in Automatic Programming 2: 1-28. doi:.,see page 25
