Займемся теперь реализацией цикла FOR без вспомогательной переменной-счетчика. Вместо нее будем использовать саму переменную цикла. Очевидно, что эта оптимизация имеет смысл только в случаях 4 и 5. В случаях 1-3 этой вспомогательной переменной уже нет.
Флажком служит переменная
t. Если
t=id, то вспомогательной переменной нет, вместо нее применяется
id (сам параметр цикла). Если
t#id, то эта переменная
t как раз и указывает на вспомогательную переменную-счетчик.
Однако, в каких случаях возможна эта оптимизация и в какие операторы должен транслироваться FOR?
Будем считать, что на любой платформе сравнение параметра цикла с нулем является эффективной операцией. Ну, в крайнем случае, настолько эффективной, чтобы оправдать отбрасывание вспомогательной переменной. Значит мы можем применить такую оптимизацию, если условие выхода из цикла удастся записать как «
UNTIL n ? 0», где операция «
?» - любая из операций сравнения (=, #, < ,> ,<= ,>= ). Изменение переменной цикла лучше делать после тела цикла, тогда условие «
UNTIL n ? 0» означает «
n вышло за пределы диапазона A..B», вернее даже «
n впервые вышло за пределы этого диапазона».
Код: "OBERON"
REPEAT
тело цикла
INC(n, Step);
UNTIL n ? 0;
В крайнем случае можно делать инкремент и до тела цикла. В этом случае перед циклом понадобится дополнительный декремент, чтобы «впрыгнуть внутрь» - к телу цикла. Этот декремент можно спрятать в присваивание
n:=A,если
A – константа (правда тогда усложнится условие IF A <=B , что можно также подправить, если и В-константа). Это менее эффективно, но даст возможноть выполнить отбрасывание вспомогательной переменной для условия «
n – это последнее значение в диапазоне, которое должно быть обработано», если такое условие можно записать как сравнение с нулем.
Код: "OBERON"
DEC(n,Step);
REPEAT
INC(n, Step);
тело цикла
UNTIL n ? 0;
Что нам известно к моменту выполнения цикла REPEAT UNTIL? Мы знаем, что тело цикла выполнится по крайней мере 1 раз. Знаем, что цикл может выполнится 2 или более раз (а может только 1), потому что случаи, когда цикл выполняется заведомо 1 раз, разобраны в предыдущем посте.
Можно ли отбросить вспомогательную переменную, если обе величины
А и В вычисляются динамически? Очевидно нет. По значению шага мы можем найти
MaxIters, которое равно самое меньшее 2 (случай
MaxIters=1 рассмотрен ранее). Мы можем заключить из этого, что
А и
А+Step должны иметь разные знаки. Но мы не знаем 1 или 2 раза должен быть выполнен цикл, а значит не можем записать условие для обеспечения этого количества выполнений. При меньшем значении шага информации еще меньше.
Если заранее известна величина
А, но не известно
В, мы знаем начало цикла, но не знаем, где он закончится. Возможно
А=В и цикл выполнится 1 раз, а возможно
А+Step тоже входит в диапазон, тогда цикл выполняется более 1 раза (по величине шага можно оценить количество выполнений сверху). Как и в предыдущем случае оптимизация неприменима.
Если
А и В известны, то нам известно о цикле всё! В частности мы можем вычислить не только точное количество итераций
NumIters, но и последнее значение, для которого должно быть исполнено тело цикла
Nlast=B-(B-A) MOD Step (
Nlast=B+(A-B) MOD (-Step), для
Step <0). Если мы производим инкремент переменной после тела цикла, то это число
Nlast не должно удовлетворять искомому условию, в то время как
Nlast+Step должно. Тут нужно быть осторожным, т. к.
Nlast+Step может выйти за пределы не только
В, но и
MAX(T), что нужно учитывать в рассуждениях.
Из
NumIters>=2 следует
A < Nlast. Для положительно шага
Step>0 имеем:
1.1 Если
Nlast=0, то
A<=Nlast-Step <0. Следующее за последним значение
Nlast+Step =Step>0, если только не произойдет переполнение. Пока мы не ввели больший шаг, чем
MAX(T), переполнения не произойдет. Если шаг будет в диапазоне
1..MAX(T)-MIN(T) необходимо дополнительно проверить условие
Step<=MAX(T). Искомое условие UNTIL
n>0.
1.2 Если
Nlast>0, то смена знака может произойти только в результате переполнения, т.е
Nlast+Step после переполнения должно быть
<=0 (
Nlast>MAX(T)-Step, если
1<=Step<=MAX(T)). Но нужно не выскочить из цикла досрочно, ведь элементы до
Nlast могут быть неположительны! Для
n=A цикл заведомо выполнится, поэтому нужно проверить величину
A+Step.
При
Nlast+Step<0 должно выполняться
либо A+Step>0 ( тогда искомое условие n<0 (а можно взять n<=0))
либо A+Step=0 (тогда искомое условие n<0)
иначе оптимизация неприменима
При
Nlast+Step=0 (а это будет только при расширенном шаге
Step>MAX(T)) может существовать только одно предшествующее
Nlast значение, это
А=Nlast-Step. Следовательно следующее значение
A+Step = Nlast>0 и это можно не проверять . Искомое условие
n=0 (а можно взять
n<=0).
1.3 Если
Nlast<0, то
Nlast+Step должно быть >=0. За искомое условие можно взять либо
n=0 (если
Nlast+Step=0), либо
n>0 (если
Nlast+Step>0), либо
n>=0 в любом из этих случаев. При
Nlast+Step<0 оптимизация неприменима.
Для шага
Step<0 аналогично. Необходимо только учесть, что отрицательных чисел на одно больше, чем положительных.
2.1 Если
Nlast=0, то
A>=Nlast-Step >0. Следующее за последним значение
Nlast+Step =Step<0, если только не произойдет переполнение. Пока мы не ввели расширенный шаг, переполнения не произойдет. Если
ABS(Step) будет в диапазоне
1..MAX(T)-MIN(T) необходимо дополнительно проверить условие
Step>=MIN(T). Искомое условие
UNTIL n<0.
2.2 Если
Nlast<0, то смена знака может произойти только в результате переполнения, т.е
Nlast+Step после переполнения должно быть
>=0 (
Nlast<MIN(T)-Step, если
-1>=Step>=MIN(T)). Но нужно не выскочить из цикла досрочно, ведь элементы до
Nlast могут быть неотрицательны ! Для
n=A цикл заведомо выполнится, поэтому нужно проверить величину
A+Step.
При
Nlast+Step>0 должно выполняться
либо A+Step<0 ( тогда искомое условие n>0 (а можно взять n>=0))
либо A+Step=0 (тогда искомое условие n>0)
иначе оптимизация неприменима
При
Nlast+Step=0 (а это будет не только при расширенном шаге, но и если
Step=MIN(T)) может существовать только одно предшествующее
Nlast значение, это
А=Nlast-Step. Следовательно следующее значение
A+Step = Nlast<0 и это можно не проверять . Искомое условие
n=0 (а можно взять
n>=0).
2.3 Если
Nlast>0, то
Nlast+Step должно быть
<=0. За искомое условие можно взять либо
n=0 (если
Nlast+Step=0), либо
n<0 (если
Nlast+Step<0), либо
n<=0 в любом из этих случаев. При
Nlast+Step>0 оптимизация неприменима.
В следующий раз займемся поиском условий для цикла
REPEAT INC(n, Step);тело цикла UNTIL n ? 0;