III Международный конкурс научно-исследовательских и творческих работ учащихся

Старт в науке

ОЦЕНКА ЭФФЕКТИВНОСТИ РАБОТЫ ПРОГРАММ

• Авторы
• Руководители
• Файлы работы
• Наградные документы

Игнатьев М.А. 1

---

1

Романова Е.И. 1

---

1

Работа в формате PDF

1.9 MB

Автор работы награжден дипломом победителя II степени

Диплом школьникаСвидетельство руководителя

12

Научно-исследовательская работа

Оценка эффективности работы программ

(информатика)

Выполнил:

Игнатьев Михаил Александрович

учащийся __6__ класса

МБОУ СШ №5, г. Кстово Нижегородской области

Руководитель:

Романова Елена Ивановна,

учитель информатики

МБОУ СШ №5, г. Кстово Нижегородской области

Оглавление

Введение…….….…………………………………………………………………….4

Материалы и методика исследований

1. Определение критериев оценки эффективности программ………...…...6

2. Вычисление точного времени выполнения конкретного блока

программы……………………………………..……………………………8

3. Проверка рекомендаций по улучшению эффективности программ……8

4. Проверка влияния используемых алгоритмов на эффективность

программ…………………...……………………………….……………10

Заключение………………………………………………………………………...10

Список источников информации………………………………………………….12

Приложения………………………………………………...……………………….13

Введение

При программировании вопрос об эффективности работы программ встает только при нехватке каких-либо ресурсов. Например, памяти при работе с большими массивами данных или времени при сложных громоздких расчетах или интенсивной работе с данными. При технических характеристиках современных компьютеров многие программы выполняются практически мгновенно. Тем не менее задачи написания эффективных программ встречаются на олимпиадах. Кроме этого четвёртую задачу ЕГЭ второй части с развёрнутым ответом также предлагается решить с учётом эффективности выполнения. Поэтому вопрос о написании эффективных программах актуален и для школьников.

Цельюмоей работыстали определение критериев оценки эффективности работы программ и проверка их на практике. Исходя из этого я поставил перед собой следующие задачи:

1. Определить критерии оценки эффективности программ.

2. Определить методы оптимизации программ.

3. Проверить на практике правильность найденных методов оптимизации программ.

4. Систематизировать найденные методы оценки эффективности работы программ в форме рекомендаций.

План реализации проекта:

1. На основе литературы определить факторы, снижающие эффективность работы программ.

2. Повторить и изучить новые понятия языка программирования Паскаль, необходимые для реализации поставленной задачи (циклы, массивы).

3. Найти способ вычисления точного времени выполнения конкретного блока программы.

4. Составить программы, доказывающие правильность найденных методов оптимизации.

5. Освоить два метод сортировки: «метод пузырька» и «метод выбора» – составить и отладить программы. Определить наиболее эффективный алгоритм.

6. Сделать выводы об оценке эффективности работы программ.

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

Материалы и методика исследования

1. Определение критериев оценки эффективности программ

Определение критериев оценки эффективности программ было составлено на основании двух источников [2], [3]. Эффективность программы оценивается отдельно по каждому ресурсу вычислительной машины. Критериями оценки являются:

• время выполнения программы;

• объем используемой оперативной или внешней памяти.

Выбор критерия оценки эффективности программы зависит от выполняемых ею функций. Оптимизация, под которой понимаетсямодификация программы для улучшения её эффективности, обычно требует компромиссов — один параметр оптимизируется за счёт других. Например, увеличение размера памяти улучшает производительность времени выполнения. Другим компромиссом может быть понятность программы, которая почти всегда достигается ценой снижения эффективности.

Способы повышения эффективности программ

1. Способы уменьшения времени выполнения

   1. Время выполнения программы в первую очередь зависит от используемых в ней методов – нужно использовать более эффективные алгоритмы.

   2. В том случае, когда в программе выполняется большое количество арифметических вычислений, для повышения скорости работы программы необходимо правильно программировать арифметические выражения. Различные арифметические операции различаются по быстродействию. Самыми быстрыми являются операции сложения и вычитания. Более медленным является умножение, затем идёт деление. Поэтому операция x/a выполняется медленнее, чем x*b, где b=1/a, операция 2*x выполняется медленнее, чем x+x.

   3. Программируя арифметические выражения, следует выбирать такую форму их записи, чтобы количество «медленных» операций было сведено к минимуму. Например, пусть необходимо вычислить: ax⁴+bx³+cx²+dx+e, где содержится 10 умножений («медленных» операций) и 4 сложения («быстрых» операций). Это же самое выражение можно записать в виде: (((ax+b)x+c)x+d)x+e. Такая форма записи называется схемой Горнера. В этом выражении 4 умножения и 4 сложения. Общее количество операций сократилось почти в два раза, соответственно уменьшится и время вычисления выражения. Подобные оптимизации являются алгоритмическими.

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

   5. При использовании вложенных циклов следует иметь в виду, что затраты процессорного времени на обработку такой конструкции могут зависеть от порядка следования вложенных циклов. При программировании вложенных циклов по возможности следует делать цикл с наименьшим числом повторений самым внешним, а цикл с наибольшим числом повторений — самым внутренним.

2. Способы экономии памяти(представлены ознакомительно и в работе не анализировались)

   1. Следует выбирать алгоритмы обработки, не требующие дублирования исходных данных структурных типов. Например, не использовать дополнительные массивы.

   2. По возможности использовать динамическую память. При необходимости выделять память, а потом освобождать.

   3. При передаче структурных данных в подпрограмму по значению, копии этих данных размещаются в стеке. Избежать копирования можно, если передавать данные не по значению, а как неизменяемые (описанные const). В последнем случае в стеке размещается только адрес данных.

1. Вычисление точного времени выполнения конкретного блока программы

Для экспериментальной проверки найденных способов повышения эффективности программ, то есть их оптимизации, необходимо было найти способ вычисления времени выполнения отдельных фрагментов программы. Трудность заключалась в том, что в среде программирования PascalABC.NET нет процедуры вычисления времени. Поэтому в работе использовалась небольшая программа (см. Приложение 1), найденная в Интернете [4]. В программу вставлялись контрольные точки, например, фиксировалось время начала выполнения цикла и время его окончания с помощью этой программы, а затем определялось время выполнения нужного фрагмента программы.

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

1. Проверка рекомендаций по улучшению эффективности программ

Для проверки найденных способов оптимизации программ мною были составлены сначала не оптимизированные программы и вычислено время их выполнения. Затем с учетом найденных рекомендаций эти программы были оптимизированы и вновь рассчитано время их выполнения.

3.1 Замена деления на умножение (см. Приложения 2, 3)

3.2 Замена умножения на сложение (см. Приложения 4, 5)

3.3 Уменьшение «медленных» операций при вычислении выражения (см. Приложения 6, 7)

3.4 Оптимизация циклов, содержащих фрагмент, не зависящий от параметров цикла (см. Приложения 8, 9)

3.5 Оптимизация вложенных циклов (см. Приложения 10, 11)

1. Проверка влияния используемых алгоритмов на эффективность программ

Для проверки влияния алгоритмов на эффективность программ мною были отлажены два способа сортировки массивов по возрастанию: «метод пузырька» и «метод выбора» и рассчитано время их выполнения (см. Приложения 12, 13).

Метод пузырька заключается в сравнении двух соседних элементов массива и их перестановки местами, если они расположены не по возрастанию. То есть максимальный элемент постепенно «всплывает» в конец массива. Просмотр массива проводится n-1 раз, где n – количество элементов в массиве, но при каждом следующем просмотре количество просматриваемых элементов уменьшается на единицу за счет одного «всплывшего» элемента.

Метод выбора заключается в поиске номера минимального элемента массива за один просмотр и перестановки его в начало массива. Просмотр массива проводится также n-1 раз, где n – количество элементов в массиве, и также при каждом следующем просмотре количество просматриваемых элементов уменьшается на единицу за счет перемещения минимального элемента в начало массива.

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

Заключение

Таким образом найденные критерии оценки эффективности программ и способы оптимизации были подтверждены практически. Результаты представлены в таблице (см. Приложение 14). Изучение различных источников показало, что:

1. Оценка эффективности работы программ и способов их оптимизации является важной и сложной задачей.

2. Оптимизации программ достигается не всегда и не по всем параметрам. Поэтому используют компромиссные решения для оптимизации только ключевых параметров.

Положительный результат стал основанием для составления рекомендаций. Мною были проверены только несколько способов уменьшения времени выполнения программ. Приёмы уменьшения объема потребляемой программами памяти не были рассмотрены, но так как они важны на практике, было решено включить их в рекомендации.

Итоги исследования: Рекомендации «Оценка эффективности работы программ и несколько методов по их оптимизации» (см. Приложение 15).

Список источников информации

1. Язык программирования Паскаль - встроенный справочник программной среды PascalABC.NET

Список интернет-источников

1. ВИКИПЕДИЯ – [Электронный ресурс]. URL: https://ru.wikipedia.org/wiki/Оптимизация_(информатика) (Дата обращения 15.12.2016 г.)

2. Оценка эффективности и качества программы. Методические указания по выполнению лабораторной работы по дисциплине "Технология разработки программных систем», Московский Государственный Технический Университет имени Н. Э. Баумана, Факультет «Информатика и системы управления», кафедра «Компьютерные системы и сети», Москва, 2013г [Электронный ресурс]. URL: https://e-learning.bmstu.ru/;

https://www.google.ru/url?sa=t&rct=j&q=&esrc=s&source=web&cd=7&ved=0ahUKEwiX-OPvpODSAhXBjywKHWwdAW4QFghBMAY&url=http%3A%2F%2Fe-learning.bmstu.ru%2Fmoodle%2Fpluginfile.php%2F2978%2Fmod_data%2Fcontent%2F976%2F%25D0%25A2%25D0%25A0%25D0%259F%25D0%25A1_4_2013.pdf&usg=AFQjCNFqoVsGhRaejCA4qoGYYBDSAuOusQ&bvm=bv.149760088,d.bGg&cad=rjt (Дата обращения 19.12.2016 г.)

1. Программа определения времени выполнения фрагмента программы в PascalABC.NET [Электронный ресурс]. URL: (https://sites.google.com/site/kustikovavalentina/home/izmerenievremenivpascal) (Дата обращения 20.12.2016 г.)

Приложения

Приложение 1

Программа определения времени выполнения фрагмента программы в PascalABC.NET

(https://sites.google.com/site/kustikovavalentina/home/izmerenievremenivpascal)

Приложение 2

Программа «Операция деления»

Приложение 3

Программа «Замена деления на умножение»

Приложение 4

Программа «Операция умножения»

Приложение 5

Программа «Замены операции умножения на сложение»

Приложение 6

Программа «Вычисление выражения»

Приложение 7

Программа «Уменьшение количества «медленных» операций при вычислении выражения»

Приложение 8

Программа с циклом, содержащим инвариантный, не зависящий от счётчика цикла, фрагмент

Приложение 9

Программа с циклом – из тела цикла вынесена операция умножения на константу, не зависящая от параметров цикла

Приложение 10

Программа с вложенными циклами (внешний цикл максимальный)

Приложение 11

Программа с вложенными циклами (внешний цикл минимальный)

Приложение 12

Программа сортировки массива методом пузырька

Программа сортировки массива методом пузырька (продолжение)

Приложение 13

Программа сортировки массива методом выбора

Программа сортировки массива методом выбора (продолжение)

Приложение 14

Приёмы оптимизации программ по затратам процессорного времени

Приложение 15

Рекомендации «Оценка эффективности работы программ и несколько методов по их оптимизации»

Эффективность программы оценивается отдельно по каждому ресурсу вычислительной машины. Критериями оценки являются:

• время выполнения программы;

• объем используемой оперативной или внешней памяти.

Способы повышения эффективности программ

1. Способы уменьшения времени выполнения

   1. Использовать более эффективные алгоритмы.

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

   3. Программируя арифметические выражения, следует выбирать такую форму их записи, чтобы количество «медленных» операций было сведено к минимуму.

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

   5. При программировании вложенных циклов по возможности следует делать цикл с наименьшим числом повторений самым внешним, а цикл с наибольшим числом повторений — самым внутренним.

2. Способы экономии памяти(представлены ознакомительно и в работе не анализировались)

   1. Следует выбирать алгоритмы обработки с использованием наименьшего количества массивов.

   2. По возможности использовать динамическую память. При необходимости выделять память, а потом освобождать.

   3. При передаче структурных данных в подпрограмму описывать их в разделе констант (const). В этом случае в стеке размещается только адрес данных – память экономится.