1 = -1
if (х[511] <t) 1 - 1000 - 512
/* утверждение: х[1] <t && х[1+512] >= t */ if (х[1+256] < t) 1 += 256
/* утверждение: х[1] < t && х[1+256] >= t */ if (х[1+128] < t) 1 += 128 i f (x[1+64] < t) 1 +=64 if (x[1+32] < t) 1 += 32 if (хП + 16] < t) 1 += 16 if ( x [ 1 +8 ] < t) 1 += 8 if (x[ 1 +4] < t) 1 += 4 if (x [ 1 +2 ] < t) 1 += 2
/* утверждение: x[1] < t && x[1+ 2] >= t */ if (x[]+l] < t) 1 += 1
/* утверждение. x[l] < t && x[1+1] >= t */ p = 1+1
if p>1000 || x[p] != t p = -1
Утверждения позволяют лучше понять работу программы. Проведя анализ одного оператора if и поняв, что происходит в обоих случаях, вы легко разберетесь и со всем остальным.
Я сравнивал «простой» двоичный поиск из раздела 4.2 (глава 4) с этой оптимизированной версией в разных системах. В первом издании этой книги приводилось время работы программ с различными уровнями оптимизации на четырех компьютерах и пяти языках программирования. Коэффициент ускорения менялся от 1,38 до 5 (что соответствует сокращению времени работы на 80%). Когда я измерил скорость работы исходной и оптимизированной программ на моем нынешнем компьютере, я с удивлением обнаружил, что время работы для п = 1000 сократилось с 350 до 125 не (сокращение времени работы на 64%).
Результат показался мне слишком хорошим, и вскоре обнаружилось, что он действительно не был вполне корректным. Тестовая программа осуществляла последовательный поиск элементов (сначала х[0], затем х[1] и так далее), что давало подпрограмме двоичного поиска преимущество, поскольку допускало предсказание ветвления алгоритма. Изменив тестовую программу так, чтобы поиск элементов производился случайным образом, я получил новый результат: 418 не для основной версии и 266 не — для оптимизированной (36% сокращение времени).
Мы разобрали предельный случай оптимизации. Очевидная версия программы двоичного поиска (которая казалась достаточно стройной) была заменена оптимизированной, в которой нет уж совсем ничего лишнего. (Эта функция была написана впервые в начале 60-х. Я услышал о ней от Гая Стила (Guy Steele) в начале 80-х, а он изучал ее в MIT. Вик Высоцкий использовал этот код в Bell Labs в 1961 году. Каждый оператор if псевдокода можно было реализовать тремя командами IBM 7090.)
Средства верификации программ из главы 4 оказались в этой задаче жизненно необходимыми. Их использование обеспечило нам уверенность в правильности получившейся программы. Когда я в первый раз увидел последний вариант программы без утверждений и вывода, он показался мне чем-то сверхъестественным.
Опубликовал vovan666
April 17 2013 00:01:16 ·
0 Комментариев ·
3294 Прочтений ·
• Не нашли ответ на свой вопрос? Тогда задайте вопрос в комментариях или на форуме! •
Комментарии
Нет комментариев.
Добавить комментарий
Рейтинги
Рейтинг доступен только для пользователей.
Пожалуйста, залогиньтесь или зарегистрируйтесь для голосования.
Нет данных для оценки.
Гость
Вы не зарегистрированны? Нажмите здесь для регистрации.
Главная
Каталог файлов
