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

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

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

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

#include " stdafx.h"

#include < stdlib.h>

#include < conio.h>

#include < fstream>

#include < iostream>

#include < intrin.h>

#include < algorithm>

#include < set>

using namespace std;

typedef set< int> MySet;

typedef set< int>:: 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< MyIt, MyIt, insert_iterator< MySet> > (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< MyIt, MyIt, insert_iterator< MySet> > (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< MyIt, MyIt, insert_iterator< MySet> > (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< int> ((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< vector< int>:: 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;

}