GUI -приложения: элементы управления.

 

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);

Под рекурсией понимается метод программирования, связанный с последовательным разбиением задачи на подзадачи меньшего размера до тех пор, пока подзадачи не станут элементарными. Если функция вызывает себя непосредственно – прямая рекурсия. Если функция вызывает себя через другую функцию – косвенная рекурсия.

Задача: нужно выкопать траншею. Обычный порядок мысли: последовательно копаем от начала до конца. Рекурсивный порядок мысли: сначала копаем левую половину, потом правую. При этом при раскопках левой половины вновь копаем ее левую половину, потом правую...