performance issue in C++ codility challenge -


edit: problem algorithmic ( molbdnilo below answer ) failing case o(n2) --> quadratic. people below trying find true worst case o( n log(n) ) time complexity algorithm.

i took codility challenge month. took me hour have 100% correct o( n log(n) ) time complexity algorithm.

but can see in below got 75% in performance, because 1 of test took 10 times long run. , not why! could point me mistakes ?

  1. https://codility.com/cert/view/
  2. https://codility.com/cert/view/certd6ztbr-rjtnqe24v242yrcv/details

point 2 contains complete problem description , complete reports (test cases , timing) solution.

roughly, add each rope after , update path root (ancestors) added node position, new maximum weight can added "under/below" each ancestors.

here code:

    // can use includes, example:     #include <algorithm>     #include <vector>     #include <map>     #include <iostream>      using namespace std;     // can write stdout debugging purposes, e.g.     // cout << "this debug message" << endl;       struct node     {         int max_to_add;         int id;         node* mummy;     };      std::map< int, node* > nodes;      bool insertrope( int durability, int pos, int id, int weight )     {         node* n = new node;         n->id = id;         nodes[id] = n;          if( pos == -1 )         {             n->max_to_add = durability - weight;             n->mummy = null;             if( n->max_to_add < 0 ) return false;         }         else         {             std::map< int, node* >::iterator = nodes.find(pos);             if( != nodes.end() )             {                 node* parent = (*it).second;                  n->mummy = parent;                 n->max_to_add = std::min( ( parent->max_to_add - weight),  (durability - weight) ) ;                 if( n->max_to_add < 0 ) return false;                  node* current = n;                 while ( (current = current->mummy) != null )                 {                     current->max_to_add = current->max_to_add - weight;                     if( current->max_to_add < 0 )                      {                         return false;                     }                 }             }          }         return true;     }      int solution(vector<int> &a, vector<int> &b, vector<int> &c) {         // write code in c++11          for(int = 0; < a.size() ; ++i)          {             if( insertrope( a[i], c[i],i,b[i] ) == false ) {return i;}          }          return a.size();     }      int main()     {          /*static const int arra[] = {4, 3, 1};         vector<int> veca (arra, arra + sizeof(arra) / sizeof(arra[0]) );          static const int arrb[] = {2, 2, 1};         vector<int> vecb (arrb, arrb + sizeof(arrb) / sizeof(arrb[0]) );           static const int arrc[] = {-1, 0, 1};         vector<int> vecc (arrc, arrc + sizeof(arrc) / sizeof(arrc[0]) );         */           static const int arra[] = {5, 3, 6, 3, 3};         vector<int> veca (arra, arra + sizeof(arra) / sizeof(arra[0]) );          static const int arrb[] = {2, 3, 1, 1, 2};         vector<int> vecb (arrb, arrb + sizeof(arrb) / sizeof(arrb[0]) );           static const int arrc[] = {-1, 0, -1, 0, 3};         vector<int> vecc (arrc, arrc + sizeof(arrc) / sizeof(arrc[0]) );          int sol = solution(veca,vecb,vecc);          system("pause");         return 0;     } 

edit 1: following rafid suggestion used new[], better, still have perf issue: https://codility.com/cert/view/certrt5ydp-w65hgpf28b5rn5ay/details

one performance tip can point out is: avoid using 'new' operator repeatedly expensive. can create large block of memory start , use whenever need don't allocate memory in heap repeatedly.


Comments

Popular posts from this blog

matlab - "Contour not rendered for non-finite ZData" -

delphi - Indy UDP Read Contents of Adata -

javascript - Any ideas when Firefox is likely to implement lengthAdjust and textLength? -