Сравнивайте с английским: нажмите на абзац — оригинал откроется в окне. Кнопка EN под абзацем показывает его прямо в тексте.
Введение
Структура данных, используемая для реализации многомерных массивов.
Data structure used to implement multi dimensional arrays
В компьютерном программировании вектор Илиффа, также известный как дисплей, — это структура данных, применяемая для реализации многомерных массивов.
In computer programming, an Iliffe vector, also known as a display, is a data structure used to implement multi dimensional arrays.
Структура данных
Вектор Илиффа для n-мерного массива (где n ≥ 2) состоит из вектора (или одномерного массива) указателей на (n − 1)-мерный массив. Они часто используются для избежания дорогостоящих операций умножения при вычислении адреса элемента массива. Они также могут использоваться для реализации массивов неправильной формы, таких как треугольные массивы, треугольные матрицы и другие виды массивов нерегулярной формы. Структура данных названа в честь Джона К. Илиффа. К их недостаткам относится необходимость множественных последовательных косвенных переходов по указателям для доступа к элементу, а также дополнительная работа, требуемая для определения следующей строки в n-мерном массиве, чтобы оптимизирующий компилятор мог предварительно загрузить её. Оба этих фактора являются источником задержек в системах, где процессор значительно быстрее основной памяти. Вектор Илиффа для двумерного массива – это просто вектор указателей на векторы данных, то есть вектор Илиффа представляет столбцы массива, где каждый элемент столбца является указателем на вектор-строку. Многомерные массивы в языках, таких как Java, Python (многомерные списки), Ruby, Visual Basic NET, Perl, PHP, JavaScript, Objective C (при использовании NSArray, а не массива в стиле C), Swift и Atlas Autocode, реализованы как векторы Илиффа. Векторы Илиффа использовались для реализации разреженных многомерных массивов в OLAP-продукте Holos. Векторы Илиффа противопоставляются векторам допа, используемым в языках, таких как Fortran, которые содержат коэффициенты шага и значения смещения для индексов в каждом измерении.
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.