Илифф вектор - Iliffe vector

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

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

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

Многомерные массивы в таких языках, как Ява, Python (многомерные списки), Рубин, Visual Basic .NET, Perl, PHP, JavaScript, Цель-C (при использовании NSArray не рядовой Массив в стиле C), Быстрый, и Атлас Автокод реализованы как векторы Илиффа. Векторы Илиффа использовались для реализации разреженных многомерных массивов в продукте OLAP. Голос.

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

Рекомендации

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

Смотрите также

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