Priority Queue - very slow

[uiiihr]

Hello! I am trying to use priority queue to store my nodes, and I need to insert and retrieve elements very frequently. The size of the queue increases dramatically at the beginning and starts to reduce after the queue reaches its maximum size in the process.

The queue contains objects with three data members, i.e., row number, column number, elevation. The object with the smallest elevation will be the first element in the queue.

I am trying to implement an algorithm proposed by a published research paper, the authored wrote "The algorithm could process a gird with 500 * 1000 cells in 2 seconds", while it seems that it took my code 2 hours to finish the task. I observed the intermediate output and found that the maximum size of my queue was about 200,000.

The following is my code, please help, thanks a lot!

********************************************************
while( !theQueue.empty())
{
// get the first element from the queue
tempNode = theQueue.top();
row = tempNode.row;
col = tempNode.col;
theQueue.pop();

z = DEMFill.get_cellValue(row, col);
for(i = 0; i < 8; i++)
{
irow = Get_rowTo(i, row);
icol = Get_colTo(i, col);
if(DEM.is_inGrid(irow, icol) && DEM.is_InternalCell(irow, icol) && DEMFill.is_nodataCell(irow, icol))
{
double iz = DEM.get_cellValue(irow, icol);
if( iz < z) { iz = z; }
DEMFill.set_cellValue(irow, icol, iz);
progress++;

tempNode.row = irow;
tempNode.col = icol;
tempNode.spill = iz;
// insert the neighbors of the current cell into the queue
theQueue.push( tempNode );
}
}
}

[ne555]

[code] Your code goes here [/code]
What is it supposed to do?

irow = Get_rowTo(i, row); //complexity?
icol = Get_colTo(i, col);
if( 
    DEM.is_inGrid(irow, icol) 
    && DEM.is_InternalCell(irow, icol) //what is this?
    && DEMFill.is_nodataCell(irow, icol) 
  ) //how hard is it to pass? 

[uiiihr]

Thanks for your response! You helped to release my pressure, because this is my first post and I was anxious waiting for people's help!

The first two lines are to locate the cursor on the neighbor of the center cell. (8- connected neighbors)

"DEM" is the name of an object belonged to class grid defined by myself, "Is_internalCell", "Is_Ingrid", and "Is_nodataCell" are methods. To check if a cell is an internal cell, is in grid, and is no data, I just need to check the value of the of a 2d vector "border"(see the definition of the grid class).

following is my grid class definition:

class Grid
{
private:
unsigned nrows;
unsigned ncols;
double xllcorner;
double yllcorner;
double cellsize;
double cellArea;
double nodataValue;
unsigned nInternalCells;
unsigned nBorderCells;
unsigned nNodataCells;
unsigned nValidCells;
// a 2D vector that contains the grid data set
vector<vector<double>> data;
//a 2D vector as identifier of the grid data set
// this vector is fill with values of -1, 1, 2
// -1: nodata cell(outside of the effective region); 1: cells on the border
// 2: internal cellsize
vector<vector<int>> border;

public:
// methods.
}

In my project, the size of the grid is 415 * 1273 (nrows = 415, ncols = 1273).

[ne555]

Please, put the code in code tags.

Describe a little your algorithm:
_ Take the cell with less elevation
_ Traverse the neighbours
_ Put the neighbours in the queue (infinite loop?). When a neighbour is not added?

double iz = DEM.get_cellValue(irow, icol);
if( iz < z) { iz = z; }
DEMFill.set_cellValue(irow, icol, iz); //Does this affect is_nodataCell ? 

I think that you want to update the values, but you are just adding (the queue has the old and new element versions)

[uiiihr]

No, it will not. I did an experiment, the code finish the loop in a second if I did not insert any new node into the queue[common out the "theQueue.push( tempNode ); " line], and under this situation the queue had about 3000 elements loaded in previous steps.