ТЕХНИКА ОПТИМИЗАЦИИ ПРОГРАММ

       

Балансировка логического древа


Оператор множественного выбора switch очень популярен среди программистов (особенно, разработчиков Windows-приложений). Число его ветвей может быть очень велико и их линейная обработка крайне непроизводительна.

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

Но, задумайтесь: чем собственно занимается оператор switch? Если отвлечься от устоявшейся идиомы "оператор SWITCH дает специальный способ выбора одного из многих вариантов, который заключается в проверке совпадения значения данного выражения с одной из заданных констант в соответствующем ветвлении", то можно сказать, что switch – оператор поиска соответствующего значения. В таком случае  линейное switch - дерево представляет собой тривиальный алгоритм последовательного поиска – самый неэффективный алгоритм из всех.

Пусть, например, исходный текст программы выглядел так:

switch (a)

{

case 98 : …;

case 4  : …;

case 3  : …;

case 9  : …;

case 22 : …;

case 0  : …;

case 11 : …;



case 666: …;

case 096: …;

case 777: …;

case 7  : …;

}

Тогда соответствующее ему не оптимизированное логическое дерево будет достигать в высоту одиннадцати гнезд (см. рис. 1 слева). Причем, на левой ветке корневого гнезда окажется аж десять других гнезд, а на правой – вообще ни одного (только соответствующий ему case - обработчик).

Исправить "перекос" можно разрезав одну ветку на две и "привив" образовавшиеся половинки к новому гнезду, содержащему условие, определяющее: в какой из веток следует искать сравниваемую переменную. Например, левая ветка может содержать гнезда с четными значениями, а правая – с нечетными. Но это плохой критерий: четных и нечетных значений редко бывает поровну и вновь образуется перекос (тем не менее никакого произвола нет и для балансировки можно использовать любой подходящий алгоритм).
Гораздо надежнее поступить так: берем наименьшее из всех значений и бросаем его в кучу А, затем берем наибольшее из всех значений и бросаем его в кучу B. Так повторяем до тех пор, пока не рассортируем все, имеющиеся значения.

Поскольку, оператор множественного выбора требует уникальности каждого значения, т.е. каждое число может встречаться в наборе (диапазоне) значений лишь однажды, легко показать, что: а) в обеих кучах будет содержаться равное количество чисел (в худшем случае – в одной куче окажется на одно число больше); б) все числа кучи A меньше наименьшего из чисел кучи B. Следовательно, достаточно выполнить только одно сравнение, чтобы определить: в какой из двух куч следует искать сравниваемое значения.

Высота нового дерева будет равна , где N – количество гнезд старого дерева. Действительно, мы же делим ветвь дерева надвое и добавляем новое гнездо – отсюда и берется и +1, а (N+1) необходимо для округления результата деления в большую сторону. Т.е. если высота не оптимизированного дерева достигала 100 гнезд, то теперь она уменьшилась до 51. Что? Говорите, 51 все равно много? А что нам мешает разбить каждую из двух ветвей еще на две? Это уменьшит высоту дерева до 27 гнезд! Аналогично, последующее уплотнение даст 16 à

12 à

11 à

9 à

8… и все! Более плотная упаковка дерева невозможна (подумайте почему – на худой конец постройте само дерево). Но, согласитесь, восемь гнезд – это не сто! Полное прохождение оптимизированного дерева потребует менее девяти сравнений!



Рисунок 1 0х001 Логическое дерево до утрамбовки (слева) и после (справа)

Из всех трех рассматриваемых компиляторов "трамбовать" switch-и не умеет один лишь WATCOM, а Visual C++ и Borland C++ сполна справляются с этой задачей.


Содержание раздела