Оценка производительности программ

«Наука начинается с тех пор,
как начинают измерять.
Точная наука немыслима без меры»

Д.И.Менделеев

Измерение производительности программ

Зачем, что и как измерять?

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

можно измерять время работы программы при помощи имеющихся в библиотеках функций. Если для этого использовать функцию текущего системного времени (clock), то мы получим «грязное» время с учетом всех других работ, выполняющихся в операционной системе. Кроме того, это время зависит от аппаратной и программной конфигурации, на которой производится измерение
в 4.1. было введено понятие трудоемкости: зависимость количества массовых операций в программе (например, сравнение, сдвиг, обмен) от размерности входных данных N. При оценке трудоемкости обычно используется грубая оценка степени роста полученной функции трудоемкости T(N), что справедливо при достаточно больших N. Но с какого именно значения N это соблюдается, в общем случае сказать невозможно;
для получения трудоемкости в программу включаются переменные-счетчики, изменяющие свое значение в той точке программы, где присутствует соответствующая операция;
время выполнения программы может меняться при ее работе с различными данными – это называется чувствительностью к данным. Для трудоемкости иногда бывает достаточно просто оценить пределы такой чувствительности, т.е. лучший и худший случаи. В каждом конкретном случае мы будем иметь некоторый случайный процесс, характеризующийся определенным разбросом;
измерения можно проводить разными способами. Можно, например, брать файлы различных размеров и измерять итоговые характеристики, а можно получать значения измеряемых величин на одном большом файле через m равных значений размерности.

В качестве примера посмотрим, как выглядит процесс сбора и обработки данных на программе, читающей пословно файл и включающей слова в динамический массив указателей с сохранением порядка. Сразу же заметим, что трудоемкость по операциям сравнения имеет вид T=N2/4, в лучшем случае, при вставке прямо упорядоченного текста, T=N2/2, в лучшем случае T=N – если входной текст обратно упорядочен. В качестве входного файла используется текст литературного произведения, имеющий достаточно «случайный» вид.

//------------------------------------------------------62-06.cpp

//------- Создание упорядоченного ДМУ из строк файла

 #include <stdio.h>

 #include <string.h>

 #include <malloc.h>

 #include <time.h>                  // Для функции clock

 #include <windows.h>               // Для функции CharToOemA

 #define SIZE0 100                 

 char **loadfile(FILE *fd){

 int cnt=0;                         // Счетчик сравнений

 long T0=clock();                   // Начальное значение времени

 char str[1000];                    // в миллисекундах

 int i,j,n=0,sz=SIZE0;              // Кол-во строк и размерность ДМУ

 char **pp = new char*[sz];         // Создать ДМУ

 while (fscanf(fd,"%s",str)==1){

      for (i=0;i<n;i++){

            cnt++;                  // Увеличение счетчика сравнений

            if (strcmp(str,pp[i])<0) break;

            }

            for (j=n-1;j>=i;j--)

                  pp[j+1]=pp[j];

            pp[i]=strdup(str);      // Копия строки в ДМ

            n++;                    // Вывод статистики на каждые 5000 слов

            if (n%5000==0) printf("%d\t%d\t%ld\n",n,cnt,clock()-T0);

            if (n+1==sz){           // Будет переполнение -

                  sz*=2;            // удвоить размерность

                  pp=(char**)realloc(pp,sizeof(char*)*sz);

                  }}

 pp[n] = NULL;                      // Ограничитель массива указателей

 printf("%d\t%d\t%ld\n",n,cnt,clock()-T0);

 return pp; }

 

 void main(){

 int i;

 FILE *fd=fopen("text.txt","r");

 char cc[80];

 char **pp=loadfile(fd);

 puts("---------------------------------------------");

 gets(cc);

 for (i=0; pp[i]!=NULL; i++){

      CharToOemA(pp[i],cc);         // Преобразование кодировки для вывода

      printf("%s\n",cc);

      }

 for (i=0; pp[i]!=NULL; i++) delete []pp[i];

 delete []pp; fclose(fd);}

Проведение измерений и сохранение результатов

Значения счетчика операций сравнения cnt и «грязного» времени работы программы clock()-T0 выводятся в окно консольного приложения, в принципе, их легко можно было бы перенаправить в тестовый файл. При форматном выводе в качестве разделителей используются знаки табуляции (\t), чтобы облегчить последующий импорт данных в Excel. Для переноса данных из окна консольного приложения необходимо правой кнопкой мыши в левом верхнем углу окна вызвать контекстное меню, в котором последовательно выполнить команды «изменить – пометить(выделить все)» и «изменить-копировать», затем скопированные в буфер обмена данные вставить в окно текстового файла.

Для включения полученных данных в Excel необходимо выполнить последовательность выбором меню и действий мастера:

«Данные»;
«Импорт внешних данных»;
«Импортировать внешние данные»;
Выбор текстового файла в диалоговом окне;
«Формат данных – с разделителями» в мастере импорта;
«Символы-разделители – табуляция и пробел» в мастере импорта;
«Формат данных столбца - общий» в мастере импорта;
Выбрать ячейку диапазона, куда будут импортированы данные.

Оценка полученных зависимостей

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

В первый столбец таблицы вносится размерность входных данных (число слов);
Во второй столбец вносится экспериментальное значение (в первую таблицу – время работы, во вторую – количество операций сравнения).
Идея оценки очень проста. Проверяется, насколько экспериментальные данные F1(N) соответствуют виду степенной функции F(N)=KNP. Показатель степени P подбирается опытным путем, исходя из предварительного анализа трудоемкости программы: в нашем случае простая упорядоченная вставка должны давать квадратичную зависимость. Коэффициент пропорциональности K подбирается таким образом, чтобы значения экспериментальной и математической зависимости совпали в некоторой точке (N0) – можно взять одну из первых точек N0=5000, тогда F1(N0)=F(N0)= KN0P, откуда следует, что K= F1(N0)/( N0P).
Естественно, если ожидаемый вид функциональной зависимости будет другим (например, линейно-логарифмическим для эффективных алгоритмов сортировки), то формулы, где присутствует эта функция, необходимо скорректировать.

cmp(эскп)

cmp*(матем)

отклонение

коэф по N1

Степень

5000

6217209

0,248688

10000

24945611

24868836

15000

57045716

55954881

20000

100133518

99475344

25000

156160970

155430225

30000

225396760

223819524

35000

304565494

304643241

40000

396710798

397901376

45000

501222764

503593929

50000

621272463

621720900

55000

754949505

752282289

60000

897124300

895278096

65000

1049094335

1050708321

70000

1220253187

1218572964

75000

1401604268

1398872025

80000

1597098280

1591605504

85000

1803745315

1796773401

90000

2025588151

2014375716

91479

2088624766

2081125522

Какие же выводы можно сделать из полученных результатов:

Количество операций сравнения практически точно имеет зависимость T(N)=N2/4 (K=0.25 N=2), что соответствует нашим предварительным теоретическим оценкам;
«Грязное» время работы программы подчиняется степенной зависимости с показателем P=2.4, т.е. примерно N2√N, т.е. хуже, чем квадратичная. Отклонение сначала достигает 30% в лучшую сторону, а затем меняется на 20% в худшую сторону, постепенно снижаясь с увеличением длины файла. Очевидно, что при работе программы имеют место процессы (ввод-вывод, работа с динамической памятью), которые имеют характеристики худшие, чем используемый в программе алгоритм.

Star

Edit on GitHub

Лабораторные работы ООП

Курсовые работы и проекты