Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > C++ > Priority Queue - very slow

Reply
Thread Tools

Priority Queue - very slow

 
 
chenbo09@gmail.com
Guest
Posts: n/a
 
      12-20-2010
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 20,000.

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

************************************************** ******
while( !theQueue.empty())
{
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;
//theQueue.push( tempNode );
}
}

if ((progress % 5000) == 0)
{
cout << theQueue.size() << " " << progress << " " <<
DEMFill.get_nValidCells() << endl;
}
if (progress == DEMFill.get_nValidCells())
{
cout << "Finished!" << endl;
break;
}
}
 
Reply With Quote
 
 
 
 
Jorgen Grahn
Guest
Posts: n/a
 
      12-20-2010
On Mon, 2010-12-20, http://www.velocityreviews.com/forums/(E-Mail Removed) wrote:
> 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.


A factor 3600 -- that's a HUGE difference. My gut feeling is that
there's a difference in algorithm, not just overhead from the priority
queue, a badly implemented operator< () etc.

I haven't read the code. Try to run your code through a profiler
(gprof if you're running GCC) and it will tell you where the algorithm
spends its time. The results from profiling often surprise you.

[snip code]

/Jorgen

--
// Jorgen Grahn <grahn@ Oo o. . .
\X/ snipabacken.se> O o .
 
Reply With Quote
 
 
 
 
Joshua Maurice
Guest
Posts: n/a
 
      12-21-2010
On Dec 20, 9:21*am, "(E-Mail Removed)" <(E-Mail Removed)> wrote:
> 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 20,000.
>
> The following is my code, please help, thanks a lot!
>
> ************************************************** ******
> * * * * while( !theQueue.empty())
> * * * * {
> * * * * * * * * 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;
> * * * * * * * * * * * * * * * * //theQueue.push( tempNode );
> * * * * * * * * * * * * }
> * * * * * * * * }
>
> * * * * * * * * if ((progress % 5000) == 0)
> * * * * * * * * {
> * * * * * * * * * * * * cout << theQueue.size() << " * " << progress << " * * * *" <<
> DEMFill.get_nValidCells() << endl;
> * * * * * * * * }
> * * * * * * * * if (progress == DEMFill.get_nValidCells())
> * * * * * * * * {
> * * * * * * * * * * * * cout << "Finished!" << endl;
> * * * * * * * * * * * * break;
> * * * * * * * * }
> * * * * }


Compiler options? Did you turn optimization on? Also, always please
post a complete compileable / linkable / executable code sample.
 
Reply With Quote
 
chenbo09@gmail.com
Guest
Posts: n/a
 
      12-21-2010
On Dec 20, 4:40*pm, Jorgen Grahn <(E-Mail Removed)> wrote:
> On Mon, 2010-12-20, (E-Mail Removed) wrote:
> > 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.

>
> A factor 3600 -- that's a HUGE difference. My gut feeling is that
> there's a difference in algorithm, not just overhead from the priority
> queue, a badly implemented operator< () etc.
>
> I haven't read the code. Try to run your code through a profiler
> (gprof if you're running GCC) and it will tell you where the algorithm
> spends its time. *The results from profiling often surprise you.
>
> [snip code]
>
> /Jorgen
>
> --
> * // Jorgen Grahn <grahn@ *Oo *o. * . *.
> \X/ * * snipabacken.se> * O *o * .

Hello Jorgen & Joshua,

Thanks for your help!

I am new to C++, so I don't know what a profiler is! But for your
information, I think I should provide more information about my code:

I defined a Grid class, among the data members, two dynamic 2D
vectors of size nrows * ncols are defined. one is used to contain the
elevation data, and the other is an identifier matrix indicating if a
cell is on the border, is an internal cell, or is no data value. I
think these two might consume a lot of memory. I am wondering if there
are ways to handle huge arrays.

Regarding the implementation of the operator <, here is my code:
class SpillNode
{
public:
unsigned row;
unsigned col;
double spill;

struct Greater : public binary_function <SpillNode, SpillNode, bool>
{
bool operator ()(const SpillNode& lhs, SpillNode& rhs) const
{
return lhs.spill > rhs.spill;
}
};
};


Joshua, can you tell me how to turn on optimization? Yes, I would like
to post my code here, but it is a relatively long multiple-file
project.

BTW, the code finished in a second if I common out the line
"theQueue.push( tempNode );". While if I don't then it is time
consuming, and this is the reason why I think it might be because of
the slow speed a priority queue. Probably my guess is wrong, and I am
not trying to offend C++ lovers.

 
Reply With Quote
 
Jorgen Grahn
Guest
Posts: n/a
 
      12-29-2010
On Tue, 2010-12-21, (E-Mail Removed) wrote:
> On Dec 20, 4:40*pm, Jorgen Grahn <(E-Mail Removed)> wrote:
>> On Mon, 2010-12-20, (E-Mail Removed) wrote:
>> > 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.

>>
>> A factor 3600 -- that's a HUGE difference. My gut feeling is that
>> there's a difference in algorithm, not just overhead from the priority
>> queue, a badly implemented operator< () etc.
>>
>> I haven't read the code. Try to run your code through a profiler
>> (gprof if you're running GCC) and it will tell you where the algorithm
>> spends its time. *The results from profiling often surprise you.
>>
>> [snip code]

....

> I am new to C++, so I don't know what a profiler is!


<http://en.wikipedia.org/wiki/Profiling_(computer_programming)>

Compile your program with extra profiling flags, run it, and get a
listing of how much time was spent in the different functions. That's
how gprof works, but I assume your compiler environment (whatever it
is) works in more or less the same way. The documentation will tell
you the details.

....
> Joshua, can you tell me how to turn on optimization? Yes, I would like
> to post my code here, but it is a relatively long multiple-file
> project.


No need to post the code. Just read the documentation for your compiler.
It will surely describe how to turn on optimization.

> BTW, the code finished in a second if I common out the line
> "theQueue.push( tempNode );". While if I don't then it is time
> consuming, and this is the reason why I think it might be because of
> the slow speed a priority queue.


It's probably mostly because your code (which I still haven't read)
does something completely different when you don't populate theQueue.
You can do no work, on an empty queue, really fast ...

/Jorgen

--
// Jorgen Grahn <grahn@ Oo o. . .
\X/ snipabacken.se> O o .
 
Reply With Quote
 
 
 
Reply

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
Program blocked in Queue.Queue.get and Queue.Queue.put Kris Python 0 01-04-2012 03:46 PM
efficient priority queue for a few descrete priority levels Marcel Müller C++ 3 04-27-2009 03:22 PM
Re: Slow Queue.queue? (was: slow network) Laszlo Nagy Python 2 01-15-2009 12:08 PM
Slow Queue.queue? (was: slow network) Laszlo Nagy Python 0 01-15-2009 08:33 AM
Is Queue.Queue.queue.clear() thread-safe? Russell Warren Python 4 06-27-2006 03:03 PM



Advertisments