- •Введение
- •Стиль
- •Имена
- •Выражения
- •Стилевое единство и идиомы
- •Макрофункции
- •Загадочные числа
- •Комментарии
- •Стоит ли так беспокоиться?
- •Дополнительная литература
- •Алгоритмы и структуры данных
- •Поиск
- •Сортировка
- •Библиотеки
- •Быстрая сортировка на языке Java
- •"О большое"
- •Динамически расширяемые массивы
- •Списки
- •Деревья
- •Хэш-таблицы
- •Заключение
- •Дополнительная литература
- •Проектирование и реализация
- •Алгоритм цепей Маркова
- •Варианты структуры данных
- •Создание структуры данных в языке С
- •Генерация вывода
- •Java
- •AWK и PERL
- •Производительность
- •Уроки
- •Дополнительная литература
- •Интерфейсы
- •Значения, разделенные запятой
- •Прототип библиотеки
- •Библиотека для распространения
- •Реализация на C++
- •Принципы интерфейса
- •Управление ресурсами
- •Abort, Retry, Fail?
- •Пользовательские интерфейсы
- •Дополнительная литература
- •Отладка
- •Отладчики
- •Хорошие подсказки, простые ошибки
- •Трудные ошибки, нет зацепок
- •Последняя надежда
- •Невоспроизводимые ошибки
- •Средства отладки
- •Чужие ошибки
- •Заключение
- •Дополнительная литература
- •Тестирование
- •Тестируйте при написании кода
- •Систематическое тестирование
- •Автоматизация тестирования
- •Тестовые оснастки
- •Стрессовое тестирование
- •Полезные советы
- •Кто осуществляет тестирование?
- •Тестирование программы markov
- •Заключение
- •Дополнительная литература
- •Производительность
- •Узкое место
- •Замеры времени и профилирование
- •Стратегии ускорения
- •Настройка кода
- •Эффективное использование памяти
- •Предварительная оценка
- •Заключение
- •Дополнительная литература
- •Переносимость
- •Язык
- •Заголовочные файлы и библиотеки
- •Организация программы
- •Изоляция
- •Обмен данными
- •Порядок байтов
- •Переносимость и внесение усовершенствований
- •Интернационализация
- •Заключение
- •Дополнительная литература
- •Нотация
- •Форматирование данных
- •Регулярные выражения
- •Программируемые инструменты
- •Интерпретаторы, компиляторы и виртуальные машины
- •Программы, которые пишут программы
- •Использование макросов для генерации кода
- •Компиляция "на лету"
- •Дополнительная литература
- •Эпилог
- •Приложение: свод правил
- •Стиль
- •Интерфейсы
- •Отладка
- •Тестирование
- •Производительность
- •Переносимость
STL. Это упражнение не имеет фиксированного завершения, так что сосредоточьтесь на небольшом репрезентативном наборе операций.
Упражнение 7-8
Повторите предыдущее упражнение для Java.
Заключение
Если вы выбрали верный алгоритм, то, как правило, об оптимизации его производительности можно уже особо и не задумываться. Однако, если необходимость в ней все же возникла, основной цикл процесса должен выглядеть так: выполните замеры; займитесь местами, изменения в которых дадут максимальный эффект; проверьте корректность изменений и выполните замеры снова. Останавливайтесь сразу же, как только достигнете приемлемых показателей; не забывайте сохранить первоначальную версию как эталон для проверки новых версий на корректность и быстродействие.
Улучшая скорость программы и ее потребность в памяти, создайте для себя набор эталонных тестов, чтобы было проще оценить и впоследствии отслеживать быстродействие программы. При наличии стандарных тестов используйте и их тоже. Если программа получается достаточно изолированной, самодостаточной, то нередко создают набор "типичных" вариантов ввода — такой подход является основой тестов быстродействия коммерческих и академических систем вроде компиляторов, вычислительных программ и т. п. Так, для Awk создан набор примерно из 20 маленьких программ, которые в совокупности перекрывают большую часть широко используемых конструкций языка. Эти программы применяются для того, чтобы удостовериться, что результаты работы верны и нет сбоев в производительности. Кроме того, у нас есть набор больших стандартных файлов ввода, которые мы также используем для тестирования времени исполнения программ. Полезно придать таким файлам какие-то легко проверяемые свойства, например размер их может быть степенью двух или десяти.
Замеры и шаблонные сравнения можно осуществлять с помощью оснасток того же типа, что $h>i использовали в главе 6 для тестирования: замеры времени запускаются автоматически; в выводимых результатах достаточно информации для того, чтобы они были понятны и воспроизводимы; записи ведутся аккуратно, чтобы можно было отследить основные тенденции и наиболее значительные изменения.
На самом деле создать хорошие тесты-замеры весьма непросто, и об этом прекрасно осведомлены компании, которые специально настраивают свои продукты так, чтобы те показывали как можно более высокие результаты именно на подобных тестах. Так что к их результатам надо относиться с известной долей скептицизма.
Дополнительная литература
Наше обсуждение спам-фильтра основывалось на работе Боба Флан-дрены (Bob Flandrena) и Кена Томпсона (Ken Thompson). Их фильтр включает в себя регулярные выражения для выполнения более осмысленных проверок и автоматической классификации сообщений ("точно спам", "возможный спам", "не спам") в соответствии со строками, которые были обнаружены.
Профилировочная статья Кнута "An Empirical Study of FORTRAN Programs" появилась в журнале Software — Practice and Experience (1, 2, p. 105-133, 1971). Ее
основой стал статистический анализ ряда программ, раскопанных в мусорных корзинах и общедоступных каталогах машин компьютерного центра.
Ион Бентли в своих книгах "Программирование на Pearls" и "Еще программирование на Pearls" (Jon Bentley. Programming Pearls. Addison-Wesley, 1986;Jon Bentley.More Programming Pearls. Addison-Wesley, 1988) приводит ряд хороших примеров улучшений программ, основанных на изменении алгоритма или настройке кода; очень неплохо описано создание оснасток для улучшения производительности и использование профилирования.
Книга Рика Буфа "Внутренние циклы" (Rick Booth. Inner Loops. Addison-Wesley, 1997)
— хорошее руководство по настройке программ для PC. Правда, процессоры эволюционируют так быстро, что специфические детали стремительно устаревают.
Серия книг Джона Хеннеси и Дэвида Паттерсона по архитектуре компьютеров
(например: John Hennessy, David Patterson. Computer Organization and Design: The Hardware/Software Interface. Morgan Kaufmann, 1997) содер жит вдумчивые рассуждения о вопросах производительности современных компьютеров.