C++ Running Time of Algorithms

Question

I've made Naive Approach/Finite Automata search algorithms as homework. Professor also asked for us to print run time of each algorithm. I tried;

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;

this stuff but it can't compute outside of main... I think. Here is my 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: I need help about how to compute time of Naive Approach Search Algorithm and Finite Autoamata Search Algorithm.

Answer 1

The question is not entirely clear but what is stopping you from just doing:

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

Note that using <ctime> as above is not the best way to accurately time algorithms as the clock runs based on the processor cycle so can give different results based on whether it is at high or low loads. However, if accuracy is not a big issue then the above is "fine".

For a better timing facility look into the <chrono> header.

Answer 2

@ArchbishopOfBanterbury thanks for your help! I did it like you suggested and it worked;

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