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

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

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

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

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

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

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

7.4. Выводы

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

Список литературы

1. Седжвик Р. Алгоритмы на С++ / пер. с англ. — М.: И. Д. Вильямс, 2011. — 1156 с.: ил.

2. Седжвик Р. Фундаментальные алгоритмы С++. — К.: Диасофт, 2001. — 484 с.

3. Ахо Дж., Хопкрофт А., Ульман Дж. Построение и анализ вычислительных алгоритмов. — М.: Мир, 1979.

4. Кнут Д. Искусство программирования для ЭВМ. Т. 3: Сортировка и поиск. — М.: Мир, 2013.

5. Новиков Ф. А. Дискретная математика: учеб. для вузов. 2-е изд. Стандарт третьего поколения. — СПб.: Питер, 2013. — 432 с.: ил.

6. Страуструп Б. Язык программирования С++. 2‑е доп. изд. — М.: Бином-пресс, 2001. – 1098 с.

7. Павловская Т. А. С/С++. Программирование на языке высокого уровня. — СПб.: Питер, 2013. — 461 с.: ил.

8. Шилдт Г. Полный справочник по С++. 4-е изд. / пер. с англ. — М.: И. Д. Вильямс, 2004. — 800 с.: ил.

9. Страуструп Б. Программирование: принципы и практика использования С++. Испр. изд. / пер. с англ. — М.: И. Д. Вильямс, 2013. —1248 с.: ил.

10. Прата С. Язык программирования C++. 6‑е изд. — М.: И. Д. Вильямс, 2011. — 1244 с.: ил.

11. Рао, Сиддхартха. Освой самостоятельно С++ за двадцать один день. 7‑е изд. — М.: И. Д. Вильямс, 2013. — 688 с.: ил.

12. Дьюхэрст Стефан К. Скользкие места С++. Как избежать проблем при проектировании и компиляции ваших программ. — М.: ДМК Пресс, 2012. — 264 с.: ил.

13. Мейерс С. Наиболее эффективное использование С++. 35 новых рекомендаций по улучшению ваших программ и проектов. — М.: ДМК Пресс, 2012. — 294 с.: ил.

Приложение Измерение времени запросом внутреннего счётчика тактов процессора

Современные процессоры (начиная с Pentium II последних серий) поддерживают команду RDTSC, возвращающую 64-битное значение внутреннего счётчика тактов. Это достойная альтернатива применению функции clock( ): можно измерить время выполнения даже одной команды процессора. Надёжный способ добраться до счётчика тактов состоит в применении ассемблерной вставки в код на С++. Можно написать функцию, аналогичную clock( ). В программе под Borland C++ 3.1 эта функция может возвращать отсчёт в формате double, как наиболее информативном, и дублировать его массивом из 8 байт, содержащим само значение отсчёта для дополнительного контроля. Функция может выглядеть так:

#include <dos.h>

#include <mem.h>

double Ti (unsigned char *u) // u – массив из 8 байт для контроля

{ struct W { unsigned long P, Q; }; // Структура из двух длинных целых

union { unsigned char tb[8]; // Объединение структуры и массива байтов

W tt; } T;

asm { // Ассемблерная вставка:

// команда RTDSC не поддерживается, задана кодом

db 0x0f, 0x31, 0x66; mov WORD PTR T.tt.P, AX; // Младшие 32 бита

db 0x66; mov WORD PTR T.tt.Q, DX; // Старшие 32 бита

}

memcpy(u, T.tb, 8); // Копирование в контрольный массив

return (double) T.tt.P/65536 + T.tt.Q*65536; // Вычисление результата

}

В оболочках Visual C++ 6.0 и более современных (32-битных) ассемблерная вставка будет выглядеть иначе: нет нужды задавать команду RTDSC кодом и использовать префиксы 32-битной операции.

asm { // Ассемблерная вставка для 32-битной программной оболочки

RTDSC; mov DWORD PTR T.tt.P, EAX; // Младшие 32 бита

mov DWORD PTR T.tt.Q, EDX; // Старшие 32 бита

}

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

В системах программирования Visual С++ от Microsoft можно также воспользоваться функцией QueryPerformanceCounter( ) из библиотеки windows.h (подробности — в справочнике MSDN). Ещё один способ использован в примере программы для статистического эксперимента.