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

Если к индексированной переменной обращаются внутри одного или нескольких операторов более одного раза, присвойте ее значение другой переменной. Например, выражение

X=(A(I)+1/A(I))+A(I)

следует привести к виду

А1=А(1)

X=(AI+1/AI) + AI

Во втором примере необходимо выполнить только одно вычисление с индексом, в то время как в первом требуется произвести три таких вычисления. Возможно, это сделает оптимизирующий компилятор.

Далее, не следует применять индексацию внутри цикла там, где можно обойтись использованием простой переменной. Рассмотрим пример вложенного цикла.

ПЛЦ:

DO 1=1 ТО 10;

DO К=1 ТО 25; В(К)=В(К)+А(1);

END; END;

Здесь при каждой реализации внутреннего цикла необходимо вычислять индекс для А(1), даже если он не изменяется в этом цикле. Более эффективной была бы следующая программа:

ПЛЦ:

DO 1 = 1 ТО 10; А1 = А(1); DO К=1 ТО 25;

В(К)=В(К)+А1; END;

END;

В первой программе индекс для А(1) вычислялся 25X10=250 раз. Во второй программе индекс для А(1) вычислялся только 10 раз. Поскольку на вычисление индексов тратится время, следует вывести из циклов всю ненужную индексацию, заменив ее переменными без индексов. На рис. 3.1 показан еще один пример уменьшения количества вычислений с индексами.

Индексация обладает еще одной особенностью: чем больше индексов используется, тем менее эффективна программа. Это означает, что массив А(720) более эффективен, чем массив А(12, 5, 12). Большинство программистов охотнее работают с массивами, имеющими два и более индекса, если индексы имеют мнемонический смысл при программировании. Но если имеется часто применяемая подпрограмма, которая использует многомерные массивы, то лучше перейти в процессе отладки к одномерным массивам.

Некоторые программисты все время используют одномерные массивы и, по-видимому, считают, что ухудшение удобочитаемости при этом незначительно.

PL/I Медленный способ

DO I = 1 ТО N; DO J = 1 ТО М;

A(I,J) =0; ^ DO К - 1 ТО L;

A(I,J) = A(I,J) + B(J,K) * C(K,J); END; END; END;

PL/I более быстрый способ

DO I = 1 TO N; DO J = 1 TO M; TEMP = 0; DO К = 1 TO L;

TEMP = TEMP + B(J,K) * C(K,JJ; END;

A(I,J) = TEMP; END; > END;

Рис. 3.1. Пример вычислений с уменьшением количества индексаций.

Для преобразования двумерной матрицы NXM в вектор NXM элементов можно использовать один из нижеследующих способов:

1. Если первый индекс изменяется быстрее второго, то К-й элемент получается как

VECTOR (К) = MATRIX (I, J) гдеК-I+IN* (1-1)]

2. Если последний индекс изменяется быстрее второго, то К-й элемент получается как

VECTOR (К) = MATRIX (I, J)

где К = J + [М * (J —1)1

I метод преобразует J* ^ £| в [ad Ь е с f].

II метод преобразует [^^] в [abcdef]9

Ввиду того что эти методы преобразования двумерного массива в одномерный ухудшают удобочитаемость большинства программ, их следует применять очень осторожно.

Еще один метод сокращения числа индексов заключается в том, чтобы сделать двумерные или многомерные массивы эквивалентными одномерному массиву. Очень часто для этого необходимо присвоить нулевые значения всем элементам многомерного массива. Обычно это делают следующим образом:

ФОРТРАН:

DIMENSION А(2,3,4,5)

DO 10 1=1,2 DO 10 J = lf3 DO 10 K=l,4 DO 10 L=l,5

A(I,J,K,L)=0.0

10 CONTINUE

В данном случае требуются четыре индекса и четыре цикла. Значительно более эффективным решением этой задачи является такое:

ФОРТРАН:

DIMENSION А(2,3,4,5), В(120) EQUIVALENCE (А(1,1,1,1), В(1) )

DO 10 1 = 1,120 В(1)=0.0 10 CONTINUE

Операторы устанавливают эквивалентность четырехмерного массива А одномерному массиву В. Теперь требуются только один индекс и один цикл для присвоения нулевых значений элементам этого массива. Преимущества этого метода состоят в сохранении памяти, ускорении компилирования и более быстром выполнении программы. Недостаток заключается в снижении удобочитаемости: читающий должен заметить, что два массива эквивалентны. Ухудшение удобочитаемости может быть серьезным недостатком, если оно приводит к путанице или затрудняет модификацию программы.

Внутри циклов следует избегать вычислений со сложной индексацией. Например,

ФОРТРАН:

DO 6 1 = 1,110

Х(3*1,+ 4)=Y(3*I -f 4) + С 6 CONTINUE

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

ФОРТРАН:

DO 6 1 = 1, 10 IK=3*I + 4 X(IK) = Y(IK) + С 6 CONTINUE

Хотя программа и улучшилась, ее можно сделать более совершенной, есди переписать заново, используя цикл с приращением.

ФОРТРАН:

DO 6 1 = 7, 34, 3 X(I)=Y(I)+C 6 CONTINUE

Ссылка на переменную с постоянным индексом обычно не требует проведения оптимизации программистом. Большинство компиляторов вычисляет адрес арифметического выражения с постоянными индексами [такого, как А(7)=] во время компилирования, благодаря чему нет необходимости в индексации во время выполнения.

Некоторые языки, такие, как ПЛ/1, допускают выражения над массивами, т. е. операторы

ПЛ/1:

DO I = 1 ТО 100

А(1)=В(1) END;

могут быть заменены на

А=В

Если указывается только имя массива, будет обрабатываться весь массив. Когда используют выражения над массивами, как в этом примере, компилятор выбирает самый эффективный метод для работы с массивом.

Большинство компиляторов создает команды для ввода-вывода всего массива, если в списке входных-выходных данных указано только имя массива (без индекса). Хотя это самый эффективный способ ввода-вывода массивов, он используется только в том случае, когда должен быть обработан весь массив и когда порядок ввода-вывода массивов известен.

3.17.1. ТИП ИНДЕКСА

Каждый язык программирования имеет определенный тип данных, наиболее предпочтительный при индексации. Его следует использовать всегда, когда это возможно, поскольку при этом ускоряется обработка. Использование другого типа индексов заставит машину выполнить несколько преобразований при каждом обращении к индексу. Легко оценить разницу в эффективности. Нужно просто выполнить программу дважды: с предпочтительным и другим типом индексов.

Разница во времени выполнения обычно довольно заметна. Наиболее эффективны индексы, представленные в двоичной форме.

> Используйте для индексации наиболее

*~4 предпочтительный тип данных.

3.17.2. ФОРМА ЗАПИСИ ИНДЕКСА -

Большинство компиляторов допускает использование в качестве индексов различные арифметические выражения. Однако только при некоторых конструкциях индексных выражений возможна оптимизация. К таким конструкциям относятся следующие:

1. V — целая переменная.

2. С —целая константа.

3. У±С — целая переменная плюс/минус целая положительная константа.

.4. С*У — целая положительная константа, умноженная на целую переменную.

5. С1*У±С2 — целая положительная константа, умноженная на Целую переменную, плюс/минус целая положительная константа.

Некоторые из более ранних компиляторов (ФОРТРАН II) фактически ограничивали индексы только вышеуказанными типами записи. Индексы всегда должны были записываться только в виде, показанном выше. Алгебраический эквивалент такой записи индекса обычно не допускает такую же оптимизацию. Так, при записи вида А (1+3) оптимизация возможна, в то время как запись А(3+1) может ее не допускать.

Для вышеприведенных видов записи индексов возможны по крайней мере частичные вычисления во время компилирования. Например, адрес А (2) может быть определен во время компилирования, что позволит не производить необходимых вычислений индекса во время выполнения программы.