На протяжении всей главы 8 нам приходилось находить максимальное из двух чисел. Например, в разделе 8.4 мы вычисляли следующие выражения:
maxendinghere = max(maxendinghere , 0),
maxsofar = max(maxsofar . maxendinghere) ,
Функция max возвращает наибольший из двух аргументов:
float max(float a. float b)
{return a > b ? a . b; }
Время выполнения такой программы составляет около 89п не.
Опытные программисты на С почувствуют рефлекторное желание заменить эту функцию макросом:
#define max(a. b) ((а) > (b) ? (а) : (b))
Это некрасиво и может привести к возникновению ошибок. При использовании оптимизирующих компиляторов это вообще не даст никакого результата, поскольку такие компиляторы раскрывают небольшие функции (вставляют их текст в месте вызова). Однако в моей системе это изменение уменьшило время выполнения алгоритма 4 с 89п не до 47л не, то есть ускорило ее работу почти вдвое.
Восторг от такого ускорения пропал, когда я измерил эффект от такого же действия для алгоритма 3 (раздел 8.3 главы 8): для п = 10 ООО время выполнения программы увеличилось с 10 мс до 100 с, то есть в 10 000 раз. Макрос увеличил зависимость времени выполнения алгоритма 3 от размера задачи с 0(п log п) до некоторой нелинейной зависимости, близкой к 0(п2). Вскоре я обнаружил, что семантика макросов приводила к тому, что алгоритм 3 рекурсивно вызывал сам себя большее число раз, чем это было необходимо, что привело к увеличению асимптотического времени выполнения. В задаче 4 приведен еще более яркий пример подобного замедления работы.
Программистам па С приходится выбирать между эффективностью и правильностью программ. На языке C++ мы вкушаем лучшие плоды обоих подходов. Язык C++ позволяет указать компилятору на необходимость раскрытия кода функции в явном виде в месте вызова. При этом совмещается ясная семантика функций и высокая производительность макросов.
Из любопытства я постарался избежать использования и макросов и функций, воспользовавшись операторами if:
1f (maxendinghere < 0) maxendinghere = 0;
if (maxsofar < maxendinghere) maxsofar = maxendinghere.
Время выполнения программы не претерпело существенных изменений.
Последовательный поиск
Обратимся к последовательному поиску в таблице (которая может быть неотсортированной).
Листинг 9.1. Последовательный поиск (версия 1)
1nt ssearchl (t) for i = [0. n) if x[i] t
return 1 return -1
Эта короткая программа находит элемент в массиве х за 4,06л не (в среднем). Поскольку в среднем приходится просматривать примерно половину элементов, на каждый из них приходится около 8,1 не.
Цикл выглядит достаточно стройным, но жирок с него все-таки срезать можно. Во внутреннем цикле выполняется две проверки. Сначала проверяется, достиг ли индекс i конца массива, а затем выясняется, не равен ли элемент x[i] искомому. Первую проверку можно исключить, добавив элемент-метку в конце массива.
Опубликовал vovan666
April 17 2013 00:01:04 ·
0 Комментариев ·
3387 Прочтений ·
• Не нашли ответ на свой вопрос? Тогда задайте вопрос в комментариях или на форуме! •
Комментарии
Нет комментариев.
Добавить комментарий
Рейтинги
Рейтинг доступен только для пользователей.
Пожалуйста, залогиньтесь или зарегистрируйтесь для голосования.
Нет данных для оценки.
Гость
Вы не зарегистрированны? Нажмите здесь для регистрации.
Главная
Каталог файлов
