13.6.5. Оптимизация ветвящихся программ по времени
Сложность ветвящейся программы определяется сложностью условия и сложностью вычислений ветвей. В отличие от неветвящейся программы, время выполнения здесь зависит от ветви, по которой следует процесс выполнения. Поэтому для таких программ имеет смысл понятие сложности программы в худшем случае и сложности программы в среднем.
Пусть Tп – временная сложность программы в худшем случае, Tу – временная сложность условия и Tв1, Tв2 – временные сложности ветвей программы. Тогда имеет место соотношение:
Tп = Tу + Max ( Tв1, Tв2 ) (5)
Временная сложность в среднем определяется формулой
Tп = Tу + PуTв1 + (1 – Pу)Tв2 (6)
где Pу – вероятность выполнения условия.
Поскольку условием является логическое выражение, общие приемы оптимизации выражений применимы и для логических выражений. Время Tл выполнения логических операций And, Or, Not, =, <> существенно меньше времени выполнения аддитивных операций, а время выполнения операций <, >, <=, >= равно времени выполнения аддитивных операций.
Tf >> Tm > Ta > Tл (7)
Рассмотрим пример: требуется выяснить, является ли одно из двух чисел A, B равным нулю.
1 вариант условия: A*B = 0
2 вариант условия: (A = 0) Or (B = 0)
В первом варианте использовано умножение и сравнение, во втором – 3 логических операции. Сложность 2–го варианта меньше.
В программах с многозначным ветвлением, когда в управлении используется несколько условий или вычисления логических выражений, существует возможность оптимизации управления вычислениями. Например, следующие вычисления эквивалентны:
-
If x < 0 then
If y < 0 then z := 1
If (x < 0) And (Y < 0) then z := 1
If x < 0 then Flag := False else Flag := True
Flag := (x >= 0)
В следующем примере условия ветвлений упрощены за счет использования соотношений, выполняющихся после вычисления предыдущего условия:
Пример 2. Программа вычисления значения функции, определенной кусочно:
2x – 1 при x < –1
y = x2 + 1 при –1 <= x < 1
2x + 1 при x >= 1
1 вариант (часто встречающийся у начинающих )
If x < –1 then y := 2*x – 1;
If (–1 <= x) And (x < 1) then y := Sqr(x) + 1;
If x >= 1 then y := 2*x + 1;
2 вариант (оптимальный )
If x < –1 then y := 2*x – 1
else If x < 1 then y := Sqr(x) + 1
else y := 2*x + 1;
Для получения 2–го варианта заметим, что условия x < –1, (–1 <= x) And (x < 1), x >= 1 взаимно исключающие и в совокупности тождественно истинные. Поэтому (–1 <= x) и x >= 1 можно заменить на else.
13.6.6.Выбирающие операторы: оператор варианта
Оператор варианта состоит из выражения, называемого селектором, и списка операторов, каждый из которых отмечен константой того же типа, что и селектор. Селектор должен быть скалярного типа, но не вещественного.
Оператор варианта вычисляет значение селектора и выбирает для исполнения оператор, одна из меток которого равна этому значению. По окончании выполнения выбранного оператора управление передается в начало следующего за оператором варианта оператора.
Если значение селектора не совпадает ни с одной из меток, то выбирается оператор, помеченный ключевым словом else. Этот оператор должен быть последним в списке вариантов. Если значение селектора не совпадает ни с одной из меток и else отсутствует, то оператор варианта игнорируется.
Оператор варианта имеет вид:
Case < выражение {селектор}> of <список меток варианта> : < оператор >;
. . . . . . . . . .
< список меток варианта > : < оператор >
[else < оператор > ]
end
На языке синтаксических диаграмм это выглядит так:
Оператор варианта
|
|
|
Примеры операторов варианта :
а) Select : = Index mod 4;
case Select of
0 : x := y*y + 1;
1 : x := y*y – 2*y;
2,3 : x := 0
end;
В этом примере Select принимает значение 0, 1, 2, 3. Это достигнуто вычислением Select := Index mod 4. Таким образом, вместо имени Select можно использовать выражение Index mod 4:
case Index mod 4 of
0 : x := y*y + 1;
1 : x := y*y – 2*y;
2,3 : x := 0
end;
б) case ch of
‘a’,’b’,’c’ : ch := succ(ch);
‘y’,’z’ : ch := pred(ch);
‘f’,’g’ : {пустой вариант};
else ch := pred(pred(ch)
end;
Программа в следующем примере вычисляет знак одной из тригонометрических функций в зависимости от квадранта декартовой плоскости.
Пример 3.
program Sign_of_Function;
Type Fun = (Unknown, FSin, FCos, Ftg, Fctg);
var FunNumber, Quoter: Integer;
TrigFun : Fun;
Begin
Write(‘Введите номер тригонометрической функции ‘);
Readln(FunNumber);
{ Вычисление имени функции }
Case FunNumber of
1: TrigFun := FSin;
2: TrigFun := FCos;
3: TrigFun := FTg ;
4: TrigFun := FCtg
else begin
TrigFun := Unknown;
Writeln(‘Неизвестная функция’)
end
end;
Write(‘Введите номер квадранта ‘); Readln(Quoter);
{ Вычисление знака функции }
case TrigFun of
FSin: case Quoter of
1, 2: Writeln (‘знак синуса +’);
3, 4: Writeln (‘знак синуса –‘)
end;
FCos: case Quoter of
1, 3: Writeln (‘знак косинуса +’);
2, 4: Writeln (‘знак косинуса –‘)
end;
FTg, FCtg: case Quoter of
1, 4: Writeln (‘знак тангенса и котангенса +’);
2, 3: Writeln (‘знак тангенса и котангенса –‘) end;
Unknown: Writeln(‘Функция не определена’)
end
end.