samedi 28 février 2015

count "empty space" right/left in a 2D vector efficiently

I have a grid of the form std::vector< vector<int> > grid (rows, std::vector<double>(columns)); which is a member variable of a class. The grid has stored values from the set {0,1,2, ... , 9}. Imagine if I go through the grid and at every position where grid[row][col] != 0 I need to know how many zeros are to the left and to the right before again grid[newRow][newCol] != 0 is fulfilled (to the left/right means in this row, so one has to iterate through the column index). For the moment I do it with the following two functions:



int countLeft(unsigned int rowIndex, unsigned int colIndex) {
int left = 0;
for (signed int i = colIndex-1; i >= 0; i--) {
if (this->grid[rowIndex][colIndex] != 0 && this->grid[rowIndex][i] == 0){
left++;
}
else
break;
}
return left;
}

int countRight(unsigned int rowIndex, unsigned int colIndex){
int right = 0;
for (unsigned int i = colIndex + 1; i < this->grid[0].size(); i++) {
if (this->grid[rowIndex][i] == 0 && this->grid[rowIndex][colIndex] != 0) {
right++;
}
else
break;
}
return right;
}


Running the Performance wizard on VS2013 I found out that these two functions are slowing down my program significantly. Therefore my question, how I could improve my method of knowing the zeros to the left/right, without counting every time. Thanks in advance.


Aucun commentaire:

Enregistrer un commentaire