ЛР. Проведение серийных экспериментов

Post date: Mar 15, 2011 10:33:33 PM

Лабораторная работа направлена на изучение основ языка C/C++ и основ проведения серийных экспериментов.

Постановка задачи

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

Программа, выполняющая замеры времени работы сортировки, должна обязательно принимать следующие значения через аргументы командной строки: количество элементов для сортировки и seed, инициализирующий генератор случайных чисел. Пример запуска программы: "Exp.exe 1000 666", где Exp.exe - программа, выполняющая замеры времени работы сортировки.

Требования к программе выполняющей замеры времени сортировки:

• организовывать разбор командной строки (в случае не правильного ввода аргументов командной строки, сообщать пользователю правила их ввода);
• для выделения/освобождения памяти под массивы необходимо использовать функции malloc/free;
• для генерации массивов необходимо использовать функцию rand() (при этом сгенерированные числа должны прнимать все допустимые значения из диапазона, который позволяет хранить тип данных для сортировки);
• программа должна быть реализована в более чем двух файлах (в одном .cpp файле функция main, в другом - функции сортировки);
• для проверки корректности необходимо сравнить результат сортировки с тем, который получается при использовании функции qsort из библиотеки std;
• для замеров времени использовать функцию QueryPerformanceCounter();
• программа должна выводить на экран два числа: время сортировки и элемент, расположенный в отсортированном массиве на позиции size/13, где size - количество элементов массива.

Каждому студенту необходимо реализовать две сортировки и использовать сортировку qsort из библиотеки std. Реализовать это можно в виде трёх программ (Exp1, Exp2, Exp3) или добавив ещё один аргумент в командную строку, указывающий какую сортировку использовать (этот вариант предпочтительнее). Всего должно быть получено 3 графика по времени работы сортировок (две сортировки из списка ниже и qsort).

Ищите свою фамилию в списке (81-02, 81-12), порядковый номер - соответствует сортировкам, которые необходимо реализовать:

1. Сортировка выбором. Сортировка Хоара. Сортировка элементов типа double.
2. Сортировка пузырьком. Сортировка Шелла. Сортировка элементов типа double.
3. Сортировка вставками. Сортировка Слиянием. Сортировка элементов типа double.
4. Сортировка выбором. Сортировка Шелла. Сортировка элементов типа float.
5. Сортировка пузырьком. Сортировка Слиянием. Сортировка элементов типа float.
6. Сортировка вставками. Сортировка Хоара. Сортировка элементов типа float.
7. Сортировка выбором. Сортировка Слиянием. Сортировка элементов типа double.
8. Сортировка пузырьком. Сортировка Хоара. Сортировка элементов типа double.
9. Сортировка вставками. Сортировка Шелла. Сортировка элементов типа double.
10. Сортировка выбором. Сортировка Хоара. Сортировка элементов типа float.
11. Сортировка пузырьком. Сортировка Шелла. Сортировка элементов типа float.
12. Сортировка вставками. Сортировка Слиянием. Сортировка элементов типа float.

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

Например: "Tests.exe Exp.exe 0 1000000 1000 666", где Tests.exe - программа, выполняющая серийные запуски. В данном примере программа Tests.exe будет запускать программу Exp.exe с параметрами "0 666", "1000 666", "2000 666", ..., "1000000 666", при этом запуск каждой программы должен выполняться три раза и должно выбираться минимальное время работы сортировки из этих трёх запусков (т.е. сначала запускается 3 раза "Exp.exe 0 666", потом 3 раза "Exp.exe 1000 666" и т.д.).

В результате работы программы, проводящей серийные запуски, должны создаваться два файла:

1. Текстовый файл, содержащий времена сортировок (в каждой строке файла должно быть два числа, разделённые точкой с запятой (csv формат): количество сортируемых элементов, время сортировки).
2. Текстовый файл, содержащий элементы в отсортированных массивах на позиции size/13 (в каждой строке файла должно быть два числа, разделённые точкой с запятой (csv формат): количество сортируемых элементов, элемент в отсортированном массиве на позиции size/13).

Для построения графиков по трём сортировкам необходимо получить три файла со временами работы сортировок. Для этого необходимо три раза запустить программу Tests.exe с трёмя разными параметрами в зависимости от вашей реализации программы Exp.exe. Если реализовано три разные программы для проведения сортировок (Exp1, Exp2, Exp3), то запуски должны быть такими: "Tests.exe Exp1.exe ...", "Tests.exe Exp2.exe ...", "Tests.exe Exp3.exe ...". Начальное количество элементов для сортировки, конечное количество элементов для сортировки и шаг эксперимента должны быть выбраны таким образом, чтобы получить представительные данные для построения графиков (минимальное количество сортируемых элементов должно быть не больше 100, максимальное время работы сортировки должно быть не меньше 1 с, количество точек для построения графика должно быть не меньше 1500).

Пример солюшена для Microsoft Visual Studio 2008, содержащего два проекта можно скачать в приложении (эти проекты содержат примеры работы с командной строкой, замеров времени, запуска программы и получения стандартного вывода запускаемой программы). Проект Exp содержит реализацию программы, которая принимает два аргумента командной строки и выводит на экран три числа (одно из которых - время работы программы). Пример запуска программы: "Exp.exe 10 100". Проект Tests принимает два аргумента командной строки (названием запускаемого приложения и количество запусков) и выводит на экран стандартный вывод запускаемой программы. Пример запуска программы: "Tests.exe Exp.exe 100" (программы Tests.exe и Exp.exe должны быть в одной директории).

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

Сдача отчёта должна быть осуществлена не позднее, чем через неделю после сдачи программ.

На выполнение лабораторной работы отводится 3 недели.

Dead Line: 23:59 05.04.2011