i nt ssea rch2(t) hold = x[n]
X [ n ] = t
for (i = 0; ,i ++) if x[i] == t break x[n] = hold if i == n return = -1 el se
return i
Время работы уменьшилось до 3,87л не, то есть быстродействие возросло иа 5%. Мы предполагаем, что массив уже выделен, поэтому имеется возможность временно затереть значение х[п]. Нужно быть аккуратным при сохранении значения х[п] и его восстановлении. В большинстве приложений зтого не требуется, так что мы исключим эту операцию из следующей версии программы.
Теперь внутренний цикл содержит только операцию увеличения индекса, обращение к элементу массива и проверку. Можно ли еще что-нибудь урезать? В последней версии нашей программы количество повторов цикла сокращается в 8 раз. Дальнейшее сокращение не ускорило работу программы.
Листинг 9.3. Последовательный поиск (версия 3)
1nt ssearch3(t) x[n] = t
for (i = 0: ; i += 8) if (x[i] == t) { break )
if (X[l+1] — t) { i + = 1. break }
if (x[l+2] — t) { i += 2; break }
i f CxCi+3] = = t) { i + = 3: break }
if i—i +
X — t) { i += 4: break }
if (x[i+5] t) { i += 5. break }
i f (x[i+6] — t) { i += 6; break }
if С x[i+7] = = t) { i + = 7: break }
i f i =» n return -1
else
return i
При этом время поиска сокращается до 1,07 л не, то есть наблюдается 56% ускорение. На старых компьютерах уменьшение дополнительных затрат может дать
ускорение работы на 10 или 20%. На современных машинах раскрытие цикла позволяет избежать остановки конвейера, уменьшить количество ветвей и увеличить параллелизм на уровне инструкций.
Опубликовал vovan666
April 17 2013 00:01:06 ·
0 Комментариев ·
4260 Прочтений ·
• Не нашли ответ на свой вопрос? Тогда задайте вопрос в комментариях или на форуме! •
Комментарии
Нет комментариев.
Добавить комментарий
Рейтинги
Рейтинг доступен только для пользователей.
Пожалуйста, залогиньтесь или зарегистрируйтесь для голосования.
Нет данных для оценки.
Гость
Вы не зарегистрированны? Нажмите здесь для регистрации.
Главная
Каталог файлов
