Оценка производительности программ
«Наука начинается с тех пор,
как начинают измерять.
Точная наука немыслима без меры»
Д.И.Менделеев
Измерение производительности программ
Зачем, что и как измерять?
Измерение времени работы программы производится с целью ответа на вопрос: как долго будет работать программа с различными объемами входных данных, какой практический «потолок» использования она имеет. Для этого необходимо установить зависимость времени ее работы от объема входных данных. При этом нужно учитывать следующие важные моменты:
можно измерять время работы программы при помощи имеющихся в библиотеках функций. Если для этого использовать функцию текущего системного времени (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).
Естественно, если ожидаемый вид функциональной зависимости будет другим (например, линейно-логарифмическим для эффективных алгоритмов сортировки), то формулы, где присутствует эта функция, необходимо скорректировать.
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, т.е. примерно N2√N, т.е. хуже, чем квадратичная. Отклонение сначала достигает 30% в лучшую сторону, а затем меняется на 20% в худшую сторону, постепенно снижаясь с увеличением длины файла. Очевидно, что при работе программы имеют место процессы (ввод-вывод, работа с динамической памятью), которые имеют характеристики худшие, чем используемый в программе алгоритм.
