Механическое удерживание земляных масс: Механическое удерживание земляных масс на склоне обеспечивают контрфорсными сооружениями различных конструкций...
История развития пистолетов-пулеметов: Предпосылкой для возникновения пистолетов-пулеметов послужила давняя тенденция тяготения винтовок...
Топ:
Организация стока поверхностных вод: Наибольшее количество влаги на земном шаре испаряется с поверхности морей и океанов...
Марксистская теория происхождения государства: По мнению Маркса и Энгельса, в основе развития общества, происходящих в нем изменений лежит...
Интересное:
Распространение рака на другие отдаленные от желудка органы: Характерных симптомов рака желудка не существует. Выраженные симптомы появляются, когда опухоль...
Аура как энергетическое поле: многослойную ауру человека можно представить себе подобным...
Инженерная защита территорий, зданий и сооружений от опасных геологических процессов: Изучение оползневых явлений, оценка устойчивости склонов и проектирование противооползневых сооружений — актуальнейшие задачи, стоящие перед отечественными...
Дисциплины:
2023-01-01 | 35 |
5.00
из
|
Заказать работу |
|
|
21. Оптимизация: цель, критерии, требования, методика, средства.
Оптимизация программ не стремится к поиску оптимального варианта, т.е. варианта, который нельзя улучшить. Оптимизация программ – процесс улучшения программы в смысле некоторых критериев.
Цель оптимизации программ: получение из работающего варианта программы другого работающего варианта, обладающего желаемыми показателями в смысле некоторых критериев.
Основными критериями при оптимизации программ являются:
§ Скорость работы
§ Объем используемой памяти
§ Объем места, занимаемого на диске
Если программа работает медленно:
§ ее не удастся применить на практике (пример: Прогноз погоды на завтра нужен сегодня, а не через неделю)
§ с ней откажутся работать потенциальные пользователи (пример: Обработка фотографий – слишком большое время ожидания, и у нас не купят наш графический редактор)
Если программа требует много памяти (ОЗУ):
§ с ней откажутся работать потенциальные пользователи
(пример: Задача о поиске оптимального маршрута между городами – при хранении разреженной матрицы в полном варианте огромный объем требуемой памяти приведет к активному использованию файла подкачки Windows – крайне медленная работа)
Если программа требует много места на жестком диске:
§ ее могут отказаться приобретать потенциальные пользователи
(пример: вспомним наше недовольство при установке программ с 5 компакт-дисков, а также разговоры о том, что каждый новый Windows занимает в 3 раза больше места, чем старый).
Обычно 1 из критериев является основным. В современных условиях это, как правило, скорость работы (память стоит дешево).
Требования:
– Переносимость
|
– Небольшая трудоемкость
– Значимый выигрыш
– Понятность программы
– Возможность развития
Прежде чем оптимизировать программу, убеждаемся в ее работоспособности. Основной прирост производительности приходит от алгоритмической оптимизации, а не от «трюков» (ищем эффективные алгоритмы). Оптимизация кода ≠ Ассемблерная реализация (улучшаем код для увеличения быстродействия в рамках ЯПВУ). Перед переписыванием на Ассемблер изучаем ассемблерный листинг после работы компилятора (знаем ли мы, как сделать лучше?). Если все вышеперечисленное не помогло и мы знаем как улучшить ассемблерный код, только тогда переходим на Ассемблер.
Средства оптимизации:
§ Оптимизирующий компилятор.
§ Средства профилировки.
§ Оптимизирующие библиотеки.
Главное средство: голова программиста, снабженная знаниями основ программирования, теории алгоритмов, архитектуры ЭВМ.
22. Алгоритмическая оптимизация: временная сложность, сравнение алгоритмов, примеры.
Алгоритмическая оптимизация – выбор хорошего в некотором смысле алгоритма для конкретной задачи. Принципиальный момент: алгоритмическая оптимизация дает наибольший прирост производительности по сравнению с другими вариантами (к примеру, программной). Никакая оптимизация под современные архитектуры не позволит исправить ошибок, допущенных при выборе подходящего алгоритма.
Как это делать?
– Анализируем задачу.
– Ищем (литература, Интернет, изобретаем сами) алгоритмы ее решения.
– Сравниваем эти алгоритмы по тем критериями, которые для нас имеют смысл.
– Выбираем лучший алгоритм.
– Думаем, нельзя ли улучшить и его.
Сравнение алгоритмов – теория сложности. Теория сложности игнорирует константы. Для получения реальной картины и выбора путей дальнейшей (не алгоритмической) оптимизации необходимо оценить полученную реализацию.
Задача: Дано прямоугольное поле размера m x n. В каждой ячейке лежит определенное кол-во денег. Буратино начинает свой путь в ячейке (1, 1) и за 1 шаг способен двигаться на 1 клетку вправо, либо на 1 клетку вниз. Требуется найти наибольшее кол-во денег, которое может собрать Буратино на пути из (1, 1) в (m, n) и соответствующий путь.
|
Алгоритм 1. Полный перебор всех путей.
Перебор:
– сгенерировать все пути;
– для каждого найти сумму денег;
– из сумм найти максимум.
1-я разумная модификация: сгенерировав путь, сразу считать сумму и сравнивать с максимумом.
Способы измерения времени. Применение рекурсии. Примеры.
3 способа получения текущего времени в C:
§ Функция clock()
clock_t clock(void); (< time.h >)
§ API функции
В процессоре есть спец. датчик, который отсчитывает такты, начиная с некоторого момента. Можно запрашивать значение этого датчика – команда rdtsc.
§ Ассемблерные вставки
clock_t start, finish;
double d;
unsigned long i = 6000000;
start = clock();
while (i--);
finish = clock();
d = (double)(finish - start)/CLOCKS_PER_SEC;
printf("%2.1lf seconds\n", d);
Под рекурсией понимается метод программирования, связанный с последовательным разбиением задачи на подзадачи меньшего размера до тех пор, пока подзадачи не станут элементарными. Если функция вызывает себя непосредственно – прямая рекурсия. Если функция вызывает себя через другую функцию – косвенная рекурсия.
Задача: нужно выкопать траншею. Обычный порядок мысли: последовательно копаем от начала до конца. Рекурсивный порядок мысли: сначала копаем левую половину, потом правую. При этом при раскопках левой половины вновь копаем ее левую половину, потом правую...
|
|
Типы оградительных сооружений в морском порту: По расположению оградительных сооружений в плане различают волноломы, обе оконечности...
Папиллярные узоры пальцев рук - маркер спортивных способностей: дерматоглифические признаки формируются на 3-5 месяце беременности, не изменяются в течение жизни...
Историки об Елизавете Петровне: Елизавета попала между двумя встречными культурными течениями, воспитывалась среди новых европейских веяний и преданий...
Биохимия спиртового брожения: Основу технологии получения пива составляет спиртовое брожение, - при котором сахар превращается...
© cyberpedia.su 2017-2024 - Не является автором материалов. Исключительное право сохранено за автором текста.
Если вы не хотите, чтобы данный материал был у нас на сайте, перейдите по ссылке: Нарушение авторских прав. Мы поможем в написании вашей работы!