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

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

 

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

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

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

·        можно измерять время работы программы при помощи имеющихся в библиотеках функций. Если для этого использовать функцию текущего системного времени (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)=K*NP. Показатель степени P подбирается опытным путем, исходя из предварительного анализа трудоемкости программы: в нашем случае простая упорядоченная вставка должны давать квадратичную зависимость. Коэффициент пропорциональности K подбирается таким образом, чтобы значения экспериментальной и математической зависимости совпали в некоторой точке (N0) – можно взять одну из первых точек N0=5000, тогда F1(N0)=F(N0)= K*N0P, откуда следует, что K= F1(N0)/( N0P).

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

 

 


 

N

cmp(эскп)

cmp*(матем)

отклонение

коэф по N1

Степень

5000

6217209

6217209

0%

0,248688

2

10000

24945611

24868836

0%

 

 

15000

57045716

55954881

2%

 

 

20000

100133518

99475344

1%

 

 

25000

156160970

155430225

0%

 

 

30000

225396760

223819524

1%

 

 

35000

304565494

304643241

0%

 

 

40000

396710798

397901376

0%

 

 

45000

501222764

503593929

0%

 

 

50000

621272463

621720900

0%

 

 

55000

754949505

752282289

0%

 

 

60000

897124300

895278096

0%

 

 

65000

1049094335

1050708321

0%

 

 

70000

1220253187

1218572964

0%

 

 

75000

1401604268

1398872025

0%

 

 

80000

1597098280

1591605504

0%

 

 

85000

1803745315

1796773401

0%

 

 

90000

2025588151

2014375716

1%

 

 

91479

2088624766

2081125522

0%

 

 

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

·        Количество операций сравнения практически точно имеет зависимость T(N)=N2/4 (K=0.25 N=2), что соответствует нашим предварительным теоретическим оценкам;

·        «Грязное» время работы программы подчиняется степенной зависимости с показателем P=2.4, т.е. примерно N2N, т.е. хуже, чем квадратичная. Отклонение сначала достигает 30% в лучшую сторону, а затем меняется на 20% в худшую сторону, постепенно снижаясь с увеличением длины файла. Очевидно, что при работе программы имеют место процессы (ввод-вывод, работа с динамической памятью), которые имеют характеристики худшие, чем используемый в программе алгоритм.