Методические указания алгоритмы и структуры данных. Методические указания к лабораторным работам, практическим занятиям и курсовому проектированию Часть 2 Выпуск 1606

• Название: Методические указания к лабораторным работам, практическим занятиям и курсовому проектированию Часть 2 Выпуск 1606
• Анкор: Методические указания алгоритмы и структуры данных
• Дата: 03.10.2019
• Размер: 429.85 Kb.
• Имя файла: task_180930.docx
• Тип: Методические указания; #88422
• страница: 7 из 8

7. КУРСОВАЯ РАБОТА. Измерение временной сложности алгоритма

Выполнить статистический эксперимент по измерению временной сложности алгоритма обработки данных, использующего стандартную библиотеку шаблонов (тема 6).

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

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

7.1. Пример программы для эксперимента

//Demo_01.cpp: Измерение времени обращением к счётчику тактов // процессора.

// Эксперимент по сбору статистики для оценки временной сложности

// Демонстрационная программа--------------- (c) Clgn, 17.05.13

#include "stdafx.h"

#include

#include

#include

#include

#include

#include

#include

using namespace std;
typedef set MySet;

typedef set::const_iterator MyIt;

int set_make(const int p, MySet & A)

{

A.clear( );

for (int i = 0; i < p; i++)

A.insert(rand( )%1000);

//sort(A.begin( ), A.end( ));

return A.size();

}

void set_out(char N, MySet & A)

{ size_t p = A.size( );

cout << "\n" << N << '(' << p << ")=[ ";

for(MyIt i = A.begin(); i != A.end( ); ++i) cout << *i << ' ';

cout << ']';

}

int set_and(const MySet & A, const MySet & B, MySet & C)

{

set_intersection >(A.begin( ), A.end( ), B.begin( ), B.end( ), inserter(C, C.begin()));

/* Вариант: MyIt a = A.begin( ), b = B.begin( );

C.clear( );

while( (a != A.end( )) && (b != B.end( )) )

{ if(*a < *b) ++a;

else if (*b < *a) ++b;

else C.insert(*a), ++a, ++b;

}

*/

return C.size();

}

int set_or(const MySet & A, const MySet & B, MySet & C)

{

set_union >(A.begin( ), A.end( ), B.begin( ), B.end( ), inserter(C, C.begin( )));
/* Вариант: MyIt a = A.begin( ), b = B.begin( );

C.clear( );

while( (a != A.end( )) && (b != B.end( )) )

{ if(*a < *b) C.insert(*a), ++a;

else if(*b < *a) C.insert(*b), ++b;

else C.insert(*a), ++a, ++b;

}

while( a != A.end( ) )C.insert(*a), ++a;

while( b != B.end( ) )C.insert(*b), ++b;

*/

return C.size();

}

void set_sub(const MySet & A, const MySet & B, MySet & C)

{ set_difference >(A.begin( ), A.end( ), B.begin( ), B.end( ), inserter(C, C.begin( )));

/* MyIt a = A.begin( ), b = B.begin( );

C.clear( );

while( (a != A.end( )) && (b != B.end( )) )

{ if (*a < *b) C.insert(*a), ++a;

else if(*b < *a) ++b;

else ++a, ++b;

}

while( a != A.end( ) ) C.insert(*a), ++a;

*/

}

int main( )

{

ofstream out("in.txt"); // Выходной файл in.txt

if(!out) { cout << "\nОшибка открытия выходного файла!"; return(1); }

unsigned __int64 t1, t2;

int p=5, q=205, dp=2; //Параметры эксперимента

MySet A, B, C, D, E;

out << static_cast((q - p) / dp + 1); // Количество опытов

do { // Операции над множествами мощностью p

try {

size_t k = 0, sets = 0;

k += set_make(p, A); sets++;

k += set_make(p, B); sets++;

k += set_make(p, C); sets++;

k += set_make(p, D); sets++;

set_out('A', A);

set_out('B', B);

set_out('C', C);

set_out('D', D);

// A.clear();

// A.insert :: iterator>(Q.begin( ), Q.end( ));

t1 = __rdtsc( );
k += set_and(A, B, E); sets++;

// set_out('E', E);

k += set_or(C, E, A); sets++;

// set_out('E', A);

k += set_sub(A, D, E); sets++;

//...

t2 = __rdtsc( );

set_out('E', E);

k /= sets;

cout << "\np=" << p << " k=" << k << " Dt=" << t2 - t1;
out << '\n' << k << ' ' << t2 - t1 ;

}

catch(...) { cout << "\nСбой"; }

} while ((p += dp) <= q);

cout << "\n\n=== The End ===\n"); system("pause");

return 0;

}

7.2. Обработка результатов эксперимента

По результатам эксперимента выполняется регрессионный анализ: подбор уравнения регрессии, наиболее соответствующего полученным данным. Для выполнения этого пункта следует получить у преподавателя набор данных «stat», состоящий из программы RG32, файлов с примерами её входа и выхода (in.txt, out.txt) и заготовки электронной таблицы EXAMPLE.

Программа RG32 представляет собой консольное Windows-приложение и запускается из-под интерфейса командной строки (CMD). В качестве аргумента программа принимает имя файла с результатами измерений. Имя и расширение этого файла могут быть любыми. Рекомендуется поместить программу и файл измерений в один каталог. Если файл назван «IN.txt», строка запуска будет выглядеть так:

RG32 in.txt

В программе RG32 имя входа «in.txt» принято по умолчанию и его можно опустить. В этом случае программу RG32 можно запускать и в окне проводника.

Первая строка текста с данными измерений содержит общее количество опытов. Каждая из последующих строк содержит результат одного опыта: размер входа и время, разделённые хотя бы одним пробелом. Упорядочивать данные по размеру входа необязательно. Можно выполнить по несколько опытов для некоторых или для всех размеров входа. Если общее количество опытов окажется меньше указанного в первой строке, будет сделано предупреждение об этом, и программа использует фактически имеющееся количество. Если данных окажется больше – лишние игнорируются. Программа откажется работать, если опытов менее 10.

Программа RG32 выдаст на экран значения коэффициентов регрессии для набора функций, начиная от константы (отсутствие регрессии) и кончая полиномом четвёртой степени. Общий вид уравнения регрессии выводится программой в первой строке. Далее выводятся результаты подбора с поочерёдным подключением коэффициентов слева направо. Не используемые в уравнении коэффициенты выводятся нулями. Кроме коэффициентов даётся значение выборочной дисперсии (и среднеквадратичного отклонения —СКО). Результат работы программы следует включить в отчёт в виде таблицы.

Одновременно с выводом на экран программа RG32 создаёт текстовый файл OUT.txt, пригодный для импорта в электронную таблицу EXCEL.

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

Вся необходимая обработка данных уже заложена в таблицу EXAMPLE. Содержимое файла с измерениями и файла OUT.txt нужно импортировать на свободное место в таблице (закладка «Данные», команда «Из текста»), а затем скопировать на штатное: измерения — в две крайние левые колонки, а коэффициенты уравнений регрессии — на соответствующее место в правой части.

Для корректного построения графиков измерения должны быть упорядочены по возрастанию мощности (выделить область с измерениями, в закладке «Данные» выполнить команду «А->Я»).

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

Поскольку выборочные дисперсии являются случайными величинами. значения дисперсий можно считать различными только в том случае, если их отношение превосходит значение квантиля распределения Фишера (рис. 7.1).

Рис. 7.1. Квантили распределения Фишера

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

Если с учётом уровня значимости из всех полученных уравнений регрессии невозможно однозначно указать наиболее подходящее, следует попробовать увеличить количество опытов.

7.3. Оформление результатов эксперимента

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

— точки, соответствующие измеренным значениям;

— кривая регрессии для уравнения, отобранного по результатам сравнения выборочных дисперсий;

— границы доверительного интервала (регрессия ±3 СКО).

Значения СКО выдаются программой RG32. Ожидается, что все измеренные значения попадут в доверительную область (с вероятностью 99,7 %), а кривая регрессии будет усреднять их.

График можно взять из таблицы EXAMPLE. Возможно, таблицу придётся подкорректировать под фактический объём обработанных измерений (размножить строки в расчётной части и исправить диапазоны данных в графиках. Достаточно доработать только тот график, который пойдёт в отчёт.

7.4. Выводы

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