C ++ Время выполнения алгоритмов

Я сделал алгоритмы поиска Наивный подход / Конечные автоматы в качестве домашней работы. Профессор также попросил нас напечатать время выполнения каждого алгоритма. Я старался;

int start_s=clock();
// the code you wish to time goes here
int stop_s=clock();
cout << "time: " << (stop_s-start_s)/double(CLOCKS_PER_SEC)*1000 << endl;

этот материал, но он не может вычислить вне основного … я думаю.
Вот мой код;

#include <iostream>
#include <sstream>
#include <fstream>
#include<stdio.h>
#include<string.h>
#include <ctime>
#define NO_OF_CHARS 256
using namespace std;

//Naive Approach search starts here:
void naive_search(string pat, string txt)
{
int M = pat.length();
int N = txt.length();

/* A loop to slide pat[] one by one */
for (int i = 0; i <= N - M; i++)
{
int j;

/* For current index i, check for pattern match */
for (j = 0; j < M; j++)
{
if (txt[i + j] != pat[j])
break;
}
if (j == M) // if pat[0...M-1] = txt[i, i+1, ...i+M-1]
{
printf("Found pattern at index: %d \n", i);
}
}
}

//Finite Autoama starts here:
int goNextState(string pattern, int num_total_state, int state, int given_character) {

// If our character match with the pattern

if (state < num_total_state && given_character == pattern[state])

return state + 1;

int nextstate, index;

//If dont match, search the maximum legth of matched pattern

// For example pattern is = aabb and our index is aabc , start to match first character of pattern and last character of given index increasingly and decreasingly..

for (nextstate = state; nextstate > 0; nextstate--)
{
if (pattern[nextstate - 1] == given_character) // start to find longest matched substring
{
for (index = 0; index < nextstate - 1; index++) {
if (pattern[index] != pattern[state - nextstate + 1 + index])
break;
}
if (index == nextstate - 1)
return  nextstate;
}
}
return 0;
}

void Transition_Table(string pattern, int lengt_of_pattern, int  Table_Array[][NO_OF_CHARS])
{
int given_character;
int state;

for (state = 0; state <= lengt_of_pattern; state++)
for (given_character = 0; given_character<NO_OF_CHARS; ++given_character)
Table_Array[state][given_character] = goNextState(pattern, lengt_of_pattern, state, given_character);
}

void Automata_Compute(string pattern, string given_text) {
int numberOfLine = 0;

int count = 0;
int A = pattern.length();
int B = given_text.length();

int Table_Array[1000][NO_OF_CHARS];

Transition_Table(pattern, A, Table_Array);

int i, state = 0;

for (i = 0; i<B; i++) {
// get input ...
state = Table_Array[state][given_text[i]];
if (state == A) {
count++;
printf("Found pattern at index: %d \n",i - A + 1);
}
}
}

// Driver program to test above function
int main()
{
ifstream ifile("Text.txt"); // open
string text(istreambuf_iterator<char>(ifile), {});
string pat = ("AABA");
//string text = ("AABABBABABAAABABBABAAABABBBBBBBAAAAAAABBAABA\nABABABAAABAAAABBBBBAABA\nABABABAABABBBBAAAAABA");

cout << "Naive Approach:" << endl;
naive_search(pat, text);
cout << "\nFinite Automata:" << endl;
Automata_Compute(pat, text);

return 0;
}

Изменить: мне нужна помощь о том, как рассчитать время алгоритма поиска наивного подхода и конечного алгоритма поиска Autoamata.

-4

Решение

Вопрос не совсем понятен, но что мешает вам просто делать:

std::clock_t start = std::clock();
method_to_time();
std::clock_t end = std::clock();

std::cout << "Time taken to compute method_to_time() = "<< static_cast<double)((end-start))/CLOCKS_PER_SEC << " seconds.";

Обратите внимание, что с помощью <ctime> как указано выше, это не лучший способ точно рассчитать время работы алгоритмов, поскольку тактовая частота работает на основе цикла процессора, поэтому может давать разные результаты в зависимости от того, находится ли он на высоких или низких нагрузках. Однако, если точность не является большой проблемой, то вышеприведенное «хорошо».

Для лучшего выбора времени загляните в <chrono> заголовок.

0

Другие решения

@ArchbishopOfBanterbury спасибо за вашу помощь! Я сделал это, как вы предложили, и это сработало;

int main()
{
ifstream ifile("Example.txt"); // open
string text(istreambuf_iterator<char>(ifile), {});
string pat = ("nut");
//string text = ("AABABBABABAAABABBABAAABABBBBBBBAAAAAAABBAABA\nABABABAAABAAAABBBBBAABA\nABABABAABABBBBAAAAABA");

cout << "Naive Approach:" << endl;
high_resolution_clock::time_point t1 = high_resolution_clock::now();
naive_search(pat, text);
high_resolution_clock::time_point t2 = high_resolution_clock::now();
auto nduration = duration_cast<microseconds>(t2 - t1).count();

cout << "\nFinite Automata:" << endl;
high_resolution_clock::time_point t3 = high_resolution_clock::now();
Automata_Compute(pat, text);
high_resolution_clock::time_point t4 = high_resolution_clock::now();
auto fduration = duration_cast<microseconds>(t4 - t3).count();

cout << "\nNaive Approach Duration: ";
cout << nduration;
cout << "\nFinite Automata Duration: ";
cout << fduration << endl;
cout << "\n";

return 0;
}
0

По вопросам рекламы [email protected]