アルゴリズムのC++実行時間

Question

私はNaive Approach/Finite Automata検索アルゴリズムを宿題として作っています。教授はまた、各アルゴリズムの実行時間を印刷するように私たちに依頼しました。私は試した;

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

編集：ナイーブアプローチ検索アルゴリズムと有限オートマトン検索アルゴリズムの時間を計算する方法について助けが必要です。

Answer 1

質問は完全には明らかではないが、ただやってからあなたを停止しているもの：

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>ヘッダーを参照すると、タイミング機能が向上します。

Answer 2

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