Iliffe vector: Difference between revisions
Correction in the Iliffe's paper: replacement of "Genie" (correct) for the previous "Genic" (wrong). |
No edit summary Tags: Mobile edit Mobile web edit |
||
| (39 intermediate revisions by 31 users not shown) | |||
| Line 1: | Line 1: | ||
{{Short description|Data structure used to implement multi-dimensional arrays}} |
|||
| ⚫ | |||
{{primary sources|date=September 2015}} |
|||
In [[computer programming]], an '''Iliffe vector''', also known as a '''display''', is a [[data structure]] used to implement multi-dimensional [[array data structure|arrays]]. |
|||
==Data structure== |
|||
| ⚫ | Their disadvantages include the need for multiple |
||
| ⚫ | An Iliffe vector for an ''n''-dimensional array (where ''n'' ≥ 2) consists of a vector (or 1-dimensional array) of [[pointer (computer programming)|pointer]]s 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 [[jagged array]]s, such as [[triangular array]]s, [[triangular matrix|triangular matrices]] and other kinds of irregularly shaped arrays. The data structure is named after [[John Iliffe (computer designer)|John K. Iliffe]]. |
||
| ⚫ | Their disadvantages include the need for multiple chained pointer indirections to access an element, and the extra work required to determine the next row in an ''n''-dimensional array to allow an optimising compiler to prefetch it. Both of these are a source of delays 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. |
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 (programming language)|Java]] and [[Atlas Autocode]] are implemented as Iliffe vectors. |
Multidimensional arrays in languages such as [[Java (programming language)|Java]], [[Python (programming language)|Python]] (multidimensional lists), [[Ruby (programming language)|Ruby]], [[Visual Basic .NET]], [[Perl]], [[PHP]], [[JavaScript]], [[Objective-C]] (when using NSArray, not a [[row-major]] C-style array), [[Swift (programming language)|Swift]], and [[Atlas Autocode]] are implemented as Iliffe vectors. Iliffe vectors were used to implement sparse multidimensional arrays in the OLAP product [[Holos (software)|Holos]]. |
||
==Notes== |
|||
Iliffe vectors are contrasted with [[dope vector]]s in languages such as [[Fortran#Fortran 90|Fortran]], which contain the stride factors and offset values for the subscripts in each dimension. |
|||
| ⚫ | |||
==References== |
==References== |
||
| ⚫ | |||
*{{cite journal| author=John K. Iliffe|title=The Use of The Genie System in Numerical Calculations|journal=Annual Review in Automatic Programming|volume=2|year=1961| |
*{{cite journal| author=John K. Iliffe|title=The Use of The Genie System in Numerical Calculations|journal=Annual Review in Automatic Programming|volume=2|year=1961|page=25|doi=10.1016/S0066-4138(61)80002-5}} |
||
*{{Cite book | last=Peter | first=Van der Linden| authorlink=Van der Linden, Peter | title=Expert C programming: deep C secrets | date=1994 | publisher=SunSoft Press | location=Englewood Cliffs, N.J. | isbn=0-13-177429-8}} |
|||
| ⚫ | |||
[[Category:Data structures]] |
|||
==Further reading== |
|||
{{comp-sci-stub}} |
|||
* {{cite web |title=Chapter 3: Data Structure Mappings |url=http://www.chilton-computing.org.uk/acl/literature/books/compilingtechniques/p003.htm |work=Compiling Techniques |publisher=Associates Technology Literature Applications Society |accessdate=5 May 2015}} |
|||
| ⚫ | |||
Latest revision as of 19:44, 14 January 2024
 |
In computer programming, an Iliffe vector, also known as a display, is a data structure used to implement multi-dimensional arrays.
Data structure
[edit]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 jagged arrays, such as triangular arrays, triangular matrices and other kinds of irregularly shaped arrays. The data structure is named after John K. Iliffe.
Their disadvantages include the need for multiple chained pointer indirections to access an element, and the extra work required to determine the next row in an n-dimensional array to allow an optimising compiler to prefetch it. Both of these are a source of delays 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, Python (multidimensional lists), Ruby, Visual Basic .NET, Perl, PHP, JavaScript, Objective-C (when using NSArray, not a row-major C-style array), Swift, and Atlas Autocode are implemented as Iliffe vectors. Iliffe vectors were used to implement sparse multidimensional arrays in the OLAP product Holos.
Iliffe vectors are contrasted with dope vectors in languages such as Fortran, which contain the stride factors and offset values for the subscripts in each dimension.
References
[edit]- John K. Iliffe (1961). "The Use of The Genie System in Numerical Calculations". Annual Review in Automatic Programming. 2: 25. doi:10.1016/S0066-4138(61)80002-5.
Further reading
[edit]- "Chapter 3: Data Structure Mappings". Compiling Techniques. Associates Technology Literature Applications Society. Retrieved 5 May 2015.