Историки об Елизавете Петровне: Елизавета попала между двумя встречными культурными течениями, воспитывалась среди новых европейских веяний и преданий...
Наброски и зарисовки растений, плодов, цветов: Освоить конструктивное построение структуры дерева через зарисовки отдельных деревьев, группы деревьев...
Топ:
Установка замедленного коксования: Чем выше температура и ниже давление, тем место разрыва углеродной цепи всё больше смещается к её концу и значительно возрастает...
Определение места расположения распределительного центра: Фирма реализует продукцию на рынках сбыта и имеет постоянных поставщиков в разных регионах. Увеличение объема продаж...
Особенности труда и отдыха в условиях низких температур: К работам при низких температурах на открытом воздухе и в не отапливаемых помещениях допускаются лица не моложе 18 лет, прошедшие...
Интересное:
Подходы к решению темы фильма: Существует три основных типа исторического фильма, имеющих между собой много общего...
Средства для ингаляционного наркоза: Наркоз наступает в результате вдыхания (ингаляции) средств, которое осуществляют или с помощью маски...
Аура как энергетическое поле: многослойную ауру человека можно представить себе подобным...
Дисциплины:
2023-01-01 | 32 |
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);
Под рекурсией понимается метод программирования, связанный с последовательным разбиением задачи на подзадачи меньшего размера до тех пор, пока подзадачи не станут элементарными. Если функция вызывает себя непосредственно – прямая рекурсия. Если функция вызывает себя через другую функцию – косвенная рекурсия.
Задача: нужно выкопать траншею. Обычный порядок мысли: последовательно копаем от начала до конца. Рекурсивный порядок мысли: сначала копаем левую половину, потом правую. При этом при раскопках левой половины вновь копаем ее левую половину, потом правую...
|
|
Своеобразие русской архитектуры: Основной материал – дерево – быстрота постройки, но недолговечность и необходимость деления...
Двойное оплодотворение у цветковых растений: Оплодотворение - это процесс слияния мужской и женской половых клеток с образованием зиготы...
Археология об основании Рима: Новые раскопки проясняют и такой острый дискуссионный вопрос, как дата самого возникновения Рима...
Наброски и зарисовки растений, плодов, цветов: Освоить конструктивное построение структуры дерева через зарисовки отдельных деревьев, группы деревьев...
© cyberpedia.su 2017-2024 - Не является автором материалов. Исключительное право сохранено за автором текста.
Если вы не хотите, чтобы данный материал был у нас на сайте, перейдите по ссылке: Нарушение авторских прав. Мы поможем в написании вашей работы!