Вектор Илиффа

В компьютерном программировании вектор Илиффа , также известный как дисплей , представляет собой структуру данных , используемую для реализации многомерных массивов .

Структура данных

Вектор Илиффа для n -мерного массива (где n ≥ 2) состоит из вектора (или одномерного массива) указателей на ( n - 1)-мерный массив. Их часто используют, чтобы избежать необходимости выполнять дорогостоящие операции умножения при выполнении вычисления адреса элемента массива. Их также можно использовать для реализации зубчатых массивов , таких как треугольные массивы , треугольные матрицы и другие виды массивов неправильной формы. Структура данных названа в честь Джона К. Илиффа .

Их недостатки включают необходимость использования нескольких косвенных указателей для доступа к элементу и дополнительную работу, необходимую для определения следующей строки в n -мерном массиве, чтобы позволить оптимизирующему компилятору выполнить предварительную выборку ее. Оба этих фактора являются источником задержек в системах, где ЦП значительно быстрее основной памяти.

Вектор Илиффа для двумерного массива — это просто вектор указателей на векторы данных, т. е. вектор Илиффа представляет столбцы массива, где каждый элемент столбца является указателем на вектор-строку.

Многомерные массивы в таких языках, как Java , Python (многомерные списки), Ruby , Visual Basic .NET , Perl , PHP , JavaScript , Objective-C (при использовании NSArray, а не с крупными строками массива в стиле C ), Swift и Atlas. Автокод реализован как векторы Илиффа. Векторы Илиффа использовались для реализации разреженных многомерных массивов в продукте OLAP Holos .

Векторы Илиффа контрастируют с векторами допинга в таких языках, как Фортран , которые содержат коэффициенты шага и значения смещения для индексов в каждом измерении.

Ссылки

• Джон К. Илифф (1961). «Использование системы Genie в численных расчетах». Ежегодный обзор автоматического программирования . 2 : 25. дои : 10.1016/S0066-4138(61)80002-5 .

Дальнейшее чтение

• «Глава 3: Сопоставления структур данных» . Техники компиляции . Ассоциированное общество по применению технологической литературы . Проверено 5 мая 2015 г.