Листинг 9.6. Двоичный поиск: новое представление границ диапазона
1 = 512 1 = -1
if х[511 ] < t 1 - 1000 - 512 while i != 1
/* инвариант х[Ц < t && x[l+i] >= t && i = 2Aj */ nexti = i / 2 if x[1+ nexti] < t 1=1+ nexti i *= nexti else
i * nexti
/* утверждение, i == 1 && x[1] < t && x[l+i] >= t */ p = 1+1
if p> 1000 || x[p] != t p = -1
Доказательство правильности этой программы проводится так же, как и для предыдущей. Этот вариант обычно работает медленнее предшествующего, но он дает возможность дальнейшего повышения производительности.
Следующая программа является упрощением данной. Она учитывает возможность автоматической оптимизации, обеспечиваемой при компиляции. Упрощается первый оператор if, убирается переменная nexti, и присваивания, где она участвовала, удаляются из внутреннего оператора if.
Листинг 9.7. Двоичный поиск: упрощение предыдущей версии
i = 512 1 = -1
if х[511 ] < t 1 = 1000 - 512 whi1е i != 1
/* инвариант х[1] < t && x[l+i] >= t && i = 2Aj */ i = i/2 if x[l+i] < t 1 = 1 + i
/* утверждение; i == 1 && x[1] < t && x[l+i] >= t */ p = 1 +1
if p>1000 || x[p] '= t p = -1
Хотя корректность алгоритма доказывается тем же путем, что и раньше, мы уже лучше понимаем его работу на интуитивном уровне. Когда первая проверка оказывается неправильной и переменная I остается нулевой, программа находит биты р в порядке убывания значимости.
Последняя версия программы написана не от отчаяния. Она удаляет издержки на структуру цикла и деление i/2 путем раскрытия цикла в явном виде. Поскольку i принимает десять конкретных значений, мы можем закодировать их в нашей программе. Тогда нам не придется их вычислять во время ее выполнения.
Опубликовал vovan666
April 17 2013 00:01:14 ·
0 Комментариев ·
3461 Прочтений ·
• Не нашли ответ на свой вопрос? Тогда задайте вопрос в комментариях или на форуме! •
Комментарии
Нет комментариев.
Добавить комментарий
Рейтинги
Рейтинг доступен только для пользователей.
Пожалуйста, залогиньтесь или зарегистрируйтесь для голосования.
Нет данных для оценки.
Гость
Вы не зарегистрированны? Нажмите здесь для регистрации.
Главная
Каталог файлов
