I've revised my algorithm slightly as per my idea above (see code below). It runs almost twice as fast now :)
As you can see, there are now no variables local to the
while
loop. However, the memory is still not constant, and I am almost positive that the
in
and
frontier
vectors are what's causing the problem, since what else could be happening? Everything else is allocated on the stack.
What bugs me about this is that I did include the lines
1 2
|
in.reserve(rows * cols);
frontier.reserve(rows * cols);
|
What exactly does this do? I was under the impression that it allocated an internal array of size rows*cols for each vector. The vector's size NEVER exceeds this bound (I made extra sure by setting a conditional breakpoint in my debugger), so I don't see why the internal array should ever change throughout the function. By my memory indicator, though, it does. I guess just having vector's around means it's possible that memory paging becomes an issue, even if in theory the memory should never change?
Anyway, let me know if you have any more insights. Your help so far has been invaluable.
EDIT: When I comment out all the
push_back
and
erase
calls, the memory stays constant. In theory, at least as far as I can tell, neither method should be doing any reallocation. But apparently they are. :(
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58
|
void Maze2d::prims2(int r, int c) {
int total_steps = 1;
std::vector<MazeNode *> in;
std::vector<MazeNode *> frontier;
int unvisitedNeighbors[4];
int visitedNeighbors[4];
int numUnvisitedNeighbors = 0, numVisitedNeighbors = 0;
int new_in_index = 0, new_r = 0, new_c = 0;
int rand_visited_neighbor_index = 0;
int i=0;
MazeNode *new_in, *new_frontier, *rand_visited_neighbor;
in.reserve(rows * cols);
frontier.reserve(rows * cols);
nodes[r][c].visited = true;
in.push_back(&nodes[r][c]);
numUnvisitedNeighbors = reGetUnvisitedNeighbors(r, c, unvisitedNeighbors);
for(int i=0; i < numUnvisitedNeighbors; i++) {
int dir = unvisitedNeighbors[i];
MazeNode *new_frontier = nodeTo(r, c, dir);
frontier.push_back(new_frontier);
new_frontier->frontier_visited = true;
}
while(!frontier.empty()) {
new_in_index = rand() % frontier.size();
new_in = frontier[new_in_index];
new_r = new_in->row;
new_c = new_in->col;
new_in->visited = true;
in.push_back(new_in);
frontier.erase(frontier.begin() + new_in_index);
numUnvisitedNeighbors = reGetUnvisitedNeighbors(new_r, new_c, unvisitedNeighbors);
numVisitedNeighbors = reGetVisitedNeighbors(new_r, new_c, visitedNeighbors);
rand_visited_neighbor_index = rand() % numVisitedNeighbors;
rand_visited_neighbor = nodeTo(new_r, new_c, visitedNeighbors[rand_visited_neighbor_index]);
join(new_in, rand_visited_neighbor);
for(i=0; i < numUnvisitedNeighbors; i++) {
new_frontier = nodeTo(new_r, new_c, unvisitedNeighbors[i]);
if (!new_frontier->frontier_visited) {
frontier.push_back(new_frontier);
}
new_frontier->frontier_visited = true;
}
++total_steps;
}
}
|