Студопедия

Главная страница Случайная страница

Разделы сайта

АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника






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






    //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;

    }






    © 2023 :: MyLektsii.ru :: Мои Лекции
    Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав.
    Копирование текстов разрешено только с указанием индексируемой ссылки на источник.