C++ Laufzeit von Algorithmen

Question

Ich habe Naive Approach/Finite Automata Suchalgorithmen als Hausaufgabe gemacht. Professor bat uns auch, die Laufzeit jedes Algorithmus zu drucken. Ich habe es versucht;

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; 

dieses Zeug, aber es kann außerhalb der Haupt ... nicht berechnen, denke ich. Hier ist mein Code;

#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; 
} 

Edit: Ich brauche Hilfe, wie Zeit der naiven Ansatz Suchalgorithmus und Finite Autoamata Suchalgorithmus zu berechnen.

Answer 1

Die Frage ist nicht ganz klar, aber was Sie hindert von nur tun:

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."; 

Beachten Sie, dass mit <ctime> wie oben ist nicht der beste Weg, um Zeit-Algorithmen wie die Uhr, um genau laufen auf dem Prozessor-Zyklus basiert Dies kann zu unterschiedlichen Ergebnissen führen, je nachdem, ob es sich um hohe oder niedrige Lasten handelt. Wenn Genauigkeit jedoch kein großes Problem ist, dann ist das obige "in Ordnung".

Für eine bessere Zeiteinteilung Blick in die <chrono> Header.

Answer 2

@ArchisbofOfBanterbury danke für Ihre Hilfe! Ich habe es so gemacht, wie du es vorgeschlagen hast und es hat funktioniert;

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