vendredi 7 février 2020

c++ getting execution time of specific function

I am currently working on a project where I write the dynamic algorithm and recursive algorithm for the Knapsack problem. I need to compare the times of how long each algorithm takes to run. I'm a bit stuck on how to do this.. Here is what I have tried so far and am currently doing:

for Ex here is my dynamic algorithim :int dynamic(int value[], int weight[], int n, int w){

 // create arrray
  //value per weight too optimize

    //2d matrix



    int matrix[n+1][w+1];
    for(int i = 0; i <=n; i++){
      for(int x = 0; x<=w; x++){
        matrix[i][x] = 0;

      }

    }

    for(int itemIndex = 1; itemIndex<=n; itemIndex++) {
      for(int weightIndex = 1; weightIndex<=w; weightIndex++){

      int currentValue = matrix[itemIndex - 1][weightIndex];
      int itemWeight = weight[itemIndex - 1];
      int potentValue = 0;

      if(itemWeight <=  weightIndex) {
      potentValue = value[itemIndex - 1];
      int weightLeft = weightIndex - itemWeight;
      potentValue += matrix[itemIndex -1][weightLeft];
      }

      matrix[itemIndex][weightIndex] = max(potentValue, currentValue);

      }


    }

return matrix[n][w];


}

I then have a random function that randmozies a bunch of things inside my program so I do all of the time functunatily in here as well. here is what it looks like :

clock_t StartTime = clock();
recursive(vals, wts, n, w);
   clock_t EndTime = clock();
   cout << "Time for dynamic: " << (float)(EndTime- StartTime)/ CLOCKS_PER_SEC /   << endl;
  // recursive(vals, wts, n, w);

I get an output of 0 for each algorithim. Should I be calling time inside of each algorithm itself?




Aucun commentaire:

Enregistrer un commentaire