Обратимся к одному из наиболее ярких примеров оптимизации программ. Мы возьмемся за задачу 8 из главы 4: требуется реализовать двоичный поиск в таблице из тысячи целых чисел. Помните, что обычно оптимизировать двоичный поиск не требуется — алгоритм и так достаточно эффективен. Именно поэтому мы игнорировали возможность микроскопического повышения эффективности в главе 4, когда нашей задачей стояло получение простой и верной программы, которую было бы легко сопровождать. Однако иногда оптимизация поиска оказывает существенное влияние на производительность большой системы в целом.
Разрабатывать быструю версию двоичного поиска мы будем постепенно, в четыре этапа. Промежуточные программы достаточно сложны, но существует веская причина изучить их внимательно: последняя версия программы работает в 2-3 раза быстрее, чем исходная из раздела 4.2 (глава 4). Прежде чем вы продолжите чтение, попробуйте найти в листинге 9.4 явные «излишки», от которых можно избавиться.
Листинг 9,4. Двоичный поиск (исходная программа)
1 - 0; U - П-1
1 оор
/* инвариант: если t есть в массиве, то оно лежит в диапазоне х[1..и]*/
if 1 > и р = -1; break m = (1 + u) /2 case
x[m] < t• 1 = m+1 x[m] == t: p = m; break x[m] > t: и = m-1
Мы начнем работу над оптимизацией двоичного поиска с изменения условия задачи. Пусть требуется найти первое вхождение t в массиве х[0..п-1] (приведенная в листинге 9.4 версия возвращает произвольное вхождение). Именно такое условие будет стоять в разделе 15.3 (глава 15). Основной цикл программы будет выглядеть так же, как и в листинге 9.4. Мы сохраним индексы I и и, ограничивающие область поиска элемента t, но инвариант будет другим: x[l] < t <= x[u] и I < u. Мы предположим, что п >= 0, х[-1] < t и x[n] >= t (но программа никогда не будет обращаться к фиктивным элементам). Новая версия двоичного поиска приведена в листинге 9.5.
Листинг 9-5. Двоичный поиск: возвращение первого вхождения
1 = -1. и = п while 1+1 != и
/* инвариант: х[1] < t && х[и] >= t && 1 < и */ m = (1 + и) / 2 if х[m]<t 1 = m else и = m
/* утверждение 1+1 = u && x[1] < t && x[и] >= t */ p = и
i f p >= n || x[p] != t p = -1
В первой строке мы инициализируем инвариант. При повторных проходах тела цикла инвариант сохраняется при помощи оператора if: легко доказать, что обе ветви сохраняют инвариант. При завершении работы мы можем быть уверены, что если t есть в массиве, то его позиция возвращается в переменной и. Этот факт более формально выражен в утверждении. Последние две строки присваивают р индекс первого вхождения t в массив х или -1 в случае отсутствия t в массиве.
Хотя эта программа решает более сложную задачу, чем предыдущая, она потенциально более эффективна, поскольку на каждой итерации выполняется только одно сравнение t с элементом массива х. Предыдущей программе в некоторых случаях приходилось производить две такие проверки.
Следующая версия программы будет использовать известный нам факт, заключающийся в том, что п -1000. Мы представим диапазон по-другому, используя нижнюю границу I и добавку i вместо нижней и верхней границ (L и и). Код будет гарантировать, что i всегда равно какой-либо степени двойки. Это свойство легко сохранить после того, как оно впервые окажется верным, но сделать его верным достаточно сложно (поскольку размер массива — 1 ООО). Поэтому перед основным циклом программы нужно поставить условный оператор и оператор присваивания, которые сузят начальный диапазон до 512 (наибольшая степень двойки, меньшая 1000). Значения I и l+i позволяют задать диапазон -1..511 или 488. .1000. Переделав программу, получим листинг 9.6.
Опубликовал vovan666
April 17 2013 00:01:12 ·
0 Комментариев ·
3497 Прочтений ·
• Не нашли ответ на свой вопрос? Тогда задайте вопрос в комментариях или на форуме! •
Комментарии
Нет комментариев.
Добавить комментарий
Рейтинги
Рейтинг доступен только для пользователей.
Пожалуйста, залогиньтесь или зарегистрируйтесь для голосования.
Нет данных для оценки.
Гость
Вы не зарегистрированны? Нажмите здесь для регистрации.
Главная
Каталог файлов
