CODEWITHSUNDEEP
c++optimizationprofiling
dakillakan
dakillakan

Reputation: 260

Why is this code running so slowly?

I am seriously stumped by this code, I have run gprof and found that the program spends 40% of the time in the contains() function which runs about 8000 times. The program itself takes a total of 15 seconds to run. Does anyone have any idea why it takes so long, or what else it could be?

// Check a list to see if it contains a tile object at x,y
bool contains(std::list<struct Tile>* list, int x, int y){
  std::list<struct Tile>::iterator it;
  for(it = list->begin(); it != list->end(); it++){
    if((*it).x == x && (*it).y == y){
      return true;
    }
  }
  return false;
}

Upvotes: 1

Views: 133

Answers (1)

Aleksandr Pakhomov
Aleksandr Pakhomov

Reputation: 753

Use std::vector, it is about 100 times faster to traverse since it is cache-friendly. Vector push_back has O(1) amortized difficulty, just like list. Vectors are bad for middle insert anyhow. Also std::map and std::unordered_map are designed for fast search.

Upvotes: 3

Related Questions