P: n/a

Hello,
I understand that an easy way to make the standard std::priority_queue
stable is by including an integer stamp with each node that is
incremented each time a new node is pushed into the queue. However, no
matter what reasonablysized type I use for the stamp, eventually the
stamp will 'wrap around' and possibly cause incorrect ordering of
elements. For my application, which queues elements very quickly and
runs for an indefinite amount of time, this scenario is a real concern,
and will eventually cause incorrect results.
Is there any easy and painless way of correcting this orderstamp
wraparound problem?
Aaron W. LaFramboise  
Share this Question
P: n/a

"Aaron W. LaFramboise" <aa********@coxinternet.com> wrote in message
news:10*************@corp.supernews.com... Hello,
I understand that an easy way to make the standard std::priority_queue stable is by including an integer stamp with each node that is incremented each time a new node is pushed into the queue. However, no matter what reasonablysized type I use for the stamp, eventually the stamp will 'wrap around' and possibly cause incorrect ordering of elements. For my application, which queues elements very quickly and runs for an indefinite amount of time, this scenario is a real concern, and will eventually cause incorrect results.
Is there any easy and painless way of correcting this orderstamp wraparound problem?
Aaron W. LaFramboise
I don't know if this will help you but...
In a server application I helped write, we got the local date/time info and
created a string from that which identified the ordering of the queue. We
set the string to be the following format:
YYYYMMDDHHNNSSTTT
where
YYYY=year
MM=month
DD=day
HH=hours
NN=minutes
SS=seconds
TTT=milliseconds
(If you are queuing faster than that will allow for, then you can add an
integer count to the end of that, which can be free to wrap since you're not
likely to exceed THAT limit! :))
That's worked fine for three years now. Wel, the system's been rebooted
several times in that time (it is Windows, after all :)), but the queue is
restored on startup, so the ordering is still preserved properly.
Howard  
P: n/a

"Aaron W. LaFramboise" <aa********@coxinternet.com> wrote in message
news:10*************@corp.supernews.com... Hello,
I understand that an easy way to make the standard std::priority_queue stable is by including an integer stamp with each node that is incremented each time a new node is pushed into the queue. However, no matter what reasonablysized type I use for the stamp, eventually the stamp will 'wrap around' and possibly cause incorrect ordering of elements. For my application, which queues elements very quickly and runs for an indefinite amount of time, this scenario is a real concern, and will eventually cause incorrect results.
Is there any easy and painless way of correcting this orderstamp wraparound problem?
Aaron W. LaFramboise
I don't know if this will help you but...
In a server application I helped write, we got the local date/time info and
created a string from that which identified the ordering of the queue. We
set the string to be the following format:
YYYYMMDDHHNNSSTTT
where
YYYY=year
MM=month
DD=day
HH=hours
NN=minutes
SS=seconds
TTT=milliseconds
(If you are queuing faster than that will allow for, then you can add an
integer count to the end of that, which can be free to wrap since you're not
likely to exceed THAT limit! :))
That's worked fine for three years now. Wel, the system's been rebooted
several times in that time (it is Windows, after all :)), but the queue is
restored on startup, so the ordering is still preserved properly.
Howard  
P: n/a

"Aaron W. LaFramboise" <aa********@coxinternet.com> wrote in message I understand that an easy way to make the standard std::priority_queue stable is by including an integer stamp with each node that is incremented each time a new node is pushed into the queue. However, no matter what reasonablysized type I use for the stamp, eventually the stamp will 'wrap around' and possibly cause incorrect ordering of elements. For my application, which queues elements very quickly and runs for an indefinite amount of time, this scenario is a real concern, and will eventually cause incorrect results.
Is there any easy and painless way of correcting this orderstamp wraparound problem?
What is a stable priority queue?  
P: n/a

"Aaron W. LaFramboise" <aa********@coxinternet.com> wrote in message I understand that an easy way to make the standard std::priority_queue stable is by including an integer stamp with each node that is incremented each time a new node is pushed into the queue. However, no matter what reasonablysized type I use for the stamp, eventually the stamp will 'wrap around' and possibly cause incorrect ordering of elements. For my application, which queues elements very quickly and runs for an indefinite amount of time, this scenario is a real concern, and will eventually cause incorrect results.
Is there any easy and painless way of correcting this orderstamp wraparound problem?
What is a stable priority queue?  
P: n/a

Siemel Naran wrote: What is a stable priority queue?
I'm guessing items of the same priority come out in the order they were
inserted.
Kevin

My email address is valid, but changes periodically.
To contact me please use the address from a recent posting.  
P: n/a

Siemel Naran wrote: What is a stable priority queue?
I'm guessing items of the same priority come out in the order they were
inserted.
Kevin

My email address is valid, but changes periodically.
To contact me please use the address from a recent posting.  
P: n/a

On Mon, 05 Apr 2004 14:57:53 0500, "Aaron W. LaFramboise"
<aa********@coxinternet.com> wrote in comp.lang.c++: Hello,
I understand that an easy way to make the standard std::priority_queue stable is by including an integer stamp with each node that is incremented each time a new node is pushed into the queue. However, no matter what reasonablysized type I use for the stamp, eventually the stamp will 'wrap around' and possibly cause incorrect ordering of elements. For my application, which queues elements very quickly and runs for an indefinite amount of time, this scenario is a real concern, and will eventually cause incorrect results.
Is there any easy and painless way of correcting this orderstamp wraparound problem?
Aaron W. LaFramboise
Define the time stamp as an unsigned long (or unsigned long long, if
your compiler supports this extension from C), and do the increment
like this:
if (timestamp < ULONG_MAX) /* ULLONG_MAX */
++timestamp;
Don't forget to include <limits.h> or <climits>.
If you are really likely to exceed 0xffffffff, the minimum possible
value for ULONG_MAX, and your implementation doesn't support 64 bit
integer types (long long or __int64), you could always use a double or
long double.

Jack Klein
Home: http://JKTechnology.Com
FAQs for
comp.lang.c http://www.eskimo.com/~scs/Cfaq/top.html
comp.lang.c++ http://www.parashift.com/c++faqlite/
alt.comp.lang.learn.cc++ http://www.contrib.andrew.cmu.edu/~a...FAQacllc.html  
P: n/a

On Mon, 05 Apr 2004 14:57:53 0500, "Aaron W. LaFramboise"
<aa********@coxinternet.com> wrote in comp.lang.c++: Hello,
I understand that an easy way to make the standard std::priority_queue stable is by including an integer stamp with each node that is incremented each time a new node is pushed into the queue. However, no matter what reasonablysized type I use for the stamp, eventually the stamp will 'wrap around' and possibly cause incorrect ordering of elements. For my application, which queues elements very quickly and runs for an indefinite amount of time, this scenario is a real concern, and will eventually cause incorrect results.
Is there any easy and painless way of correcting this orderstamp wraparound problem?
Aaron W. LaFramboise
Define the time stamp as an unsigned long (or unsigned long long, if
your compiler supports this extension from C), and do the increment
like this:
if (timestamp < ULONG_MAX) /* ULLONG_MAX */
++timestamp;
Don't forget to include <limits.h> or <climits>.
If you are really likely to exceed 0xffffffff, the minimum possible
value for ULONG_MAX, and your implementation doesn't support 64 bit
integer types (long long or __int64), you could always use a double or
long double.

Jack Klein
Home: http://JKTechnology.Com
FAQs for
comp.lang.c http://www.eskimo.com/~scs/Cfaq/top.html
comp.lang.c++ http://www.parashift.com/c++faqlite/
alt.comp.lang.learn.cc++ http://www.contrib.andrew.cmu.edu/~a...FAQacllc.html  
P: n/a

"Kevin Goodsell" <us*********************@neverbox.com> wrote in message Siemel Naran wrote: What is a stable priority queue?
I'm guessing items of the same priority come out in the order they were inserted.
Then maybe we can use the protected member 'c'. The standard says
template <class T, class Container = std::vector<T>, ...>
class priority_queue {
protected:
Container c;
...
};
So we could derive our own class from priority_queue, and add read and write
functions that read directly into and out of 'c'. If deriving from a
nonpolymorphic class bothers us, we can use private inheritance with using
declarations.
We could get stable queue's and stacks too.
Anyway, what is a priority_queue? Is it just like a queue, except that
items with the highest priority get retrieved by top() and pop() first? How
do they achieve O(lg(N)) for both push and pop (ie. how does the heap
work?).  
P: n/a

"Kevin Goodsell" <us*********************@neverbox.com> wrote in message Siemel Naran wrote: What is a stable priority queue?
I'm guessing items of the same priority come out in the order they were inserted.
Then maybe we can use the protected member 'c'. The standard says
template <class T, class Container = std::vector<T>, ...>
class priority_queue {
protected:
Container c;
...
};
So we could derive our own class from priority_queue, and add read and write
functions that read directly into and out of 'c'. If deriving from a
nonpolymorphic class bothers us, we can use private inheritance with using
declarations.
We could get stable queue's and stacks too.
Anyway, what is a priority_queue? Is it just like a queue, except that
items with the highest priority get retrieved by top() and pop() first? How
do they achieve O(lg(N)) for both push and pop (ie. how does the heap
work?).  
P: n/a

"Aaron W. LaFramboise" <aa********@coxinternet.com> wrote: I understand that an easy way to make the standard std::priority_queue stable is by including an integer stamp with each node that is incremented each time a new node is pushed into the queue. However, no matter what reasonablysized type I use for the stamp, eventually the stamp will 'wrap around' and possibly cause incorrect ordering of elements.
Use a 128bit integer (eg. made out of four longs): I doubt that this one
will overflow on any currently available machine before the sun (note, not
the SUN) cheases to exist. Even if you account for faster processors you
should be on the safe side.
Is there any easy and painless way of correcting this orderstamp wraparound problem?
It is hard to tell what you are really doing. If a O(log n) insert and
extract is all you need, in particular if you don't need to modify
priorities, a simple alternative is to use a map rather than a proper
priority queue: the map's key is the priority and the value is a queue
of items with the same priority. All you need to do is to provide a
suitable interface:
 empty() > 'm.empty()'
 top() > 'm.begin()>second.front()'
 pop() > 'm.begin()>second.pop();
if (m.begin()>second.empty()) m.erase(m.begin())'
 push(e) > 'm[e.priority].push(e)'
I don't think that any of the approach to priority queues is capable to
deal stability. At least, a vanilla implementation of all priority queues
I know (dheap, priority queue, radix heap, splay heap) will not be stable.
I don't think that any of those heaps can be made inherently stable based
only on its operation, ie. you would always need some additional hack like
the sequence number.

<mailto:di***********@yahoo.com> <http://www.dietmarkuehl.de/>
<www.contendix.com>  Software Development & Consulting  
P: n/a

"Aaron W. LaFramboise" <aa********@coxinternet.com> wrote: I understand that an easy way to make the standard std::priority_queue stable is by including an integer stamp with each node that is incremented each time a new node is pushed into the queue. However, no matter what reasonablysized type I use for the stamp, eventually the stamp will 'wrap around' and possibly cause incorrect ordering of elements.
Use a 128bit integer (eg. made out of four longs): I doubt that this one
will overflow on any currently available machine before the sun (note, not
the SUN) cheases to exist. Even if you account for faster processors you
should be on the safe side.
Is there any easy and painless way of correcting this orderstamp wraparound problem?
It is hard to tell what you are really doing. If a O(log n) insert and
extract is all you need, in particular if you don't need to modify
priorities, a simple alternative is to use a map rather than a proper
priority queue: the map's key is the priority and the value is a queue
of items with the same priority. All you need to do is to provide a
suitable interface:
 empty() > 'm.empty()'
 top() > 'm.begin()>second.front()'
 pop() > 'm.begin()>second.pop();
if (m.begin()>second.empty()) m.erase(m.begin())'
 push(e) > 'm[e.priority].push(e)'
I don't think that any of the approach to priority queues is capable to
deal stability. At least, a vanilla implementation of all priority queues
I know (dheap, priority queue, radix heap, splay heap) will not be stable.
I don't think that any of those heaps can be made inherently stable based
only on its operation, ie. you would always need some additional hack like
the sequence number.

<mailto:di***********@yahoo.com> <http://www.dietmarkuehl.de/>
<www.contendix.com>  Software Development & Consulting  
P: n/a

"Dietmar Kuehl" <di***********@yahoo.com> wrote Use a 128bit integer (eg. made out of four longs): I doubt that this one will overflow on any currently available machine before the sun (note, not the SUN) cheases to exist. Even if you account for faster processors you should be on the safe side.
Gaa! Do people no longer do basic backofthe envelope calculations?
If a 5GHz computer had an integer increment that took only one CPU cycle and
did NOTHING but increment a 64bit int 5 billion times per second 24hours a
day without interruption, it would take 117 _YEARS_ before you ran out of
numbers!!! If you throw in the obligatory jump to implement the loop and
made the jump also take a single CPU cycle, the duration leaps to a whopping
234 years.
The most generous thing I can say about using a 128bit integer for this
purpose is that it's absurdly overengineered. There's a lot worse that
could be said about the idea.
Claudio Puviani  
P: n/a

"Dietmar Kuehl" <di***********@yahoo.com> wrote Use a 128bit integer (eg. made out of four longs): I doubt that this one will overflow on any currently available machine before the sun (note, not the SUN) cheases to exist. Even if you account for faster processors you should be on the safe side.
Gaa! Do people no longer do basic backofthe envelope calculations?
If a 5GHz computer had an integer increment that took only one CPU cycle and
did NOTHING but increment a 64bit int 5 billion times per second 24hours a
day without interruption, it would take 117 _YEARS_ before you ran out of
numbers!!! If you throw in the obligatory jump to implement the loop and
made the jump also take a single CPU cycle, the duration leaps to a whopping
234 years.
The most generous thing I can say about using a 128bit integer for this
purpose is that it's absurdly overengineered. There's a lot worse that
could be said about the idea.
Claudio Puviani  
P: n/a

"Claudio Puviani" <pu*****@hotmail.com> wrote in message
news:0i*********************@news4.srv.hcvlny.cv.n et... "Dietmar Kuehl" <di***********@yahoo.com> wrote Use a 128bit integer (eg. made out of four longs): I doubt that this one will overflow on any currently available machine before the sun (note, not the SUN) cheases to exist. Even if you account for faster processors you should be on the safe side. Gaa! Do people no longer do basic backofthe envelope calculations?
If a 5GHz computer had an integer increment that took only one CPU cycle
and did NOTHING but increment a 64bit int 5 billion times per second 24hours
a day without interruption, it would take 117 _YEARS_ before you ran out of numbers!!! If you throw in the obligatory jump to implement the loop and made the jump also take a single CPU cycle, the duration leaps to a
whopping 234 years.
The most generous thing I can say about using a 128bit integer for this purpose is that it's absurdly overengineered. There's a lot worse that could be said about the idea.
Claudio Puviani
My envelopes must be old. They only support 32bit math. :)
Howard  
P: n/a

"Claudio Puviani" <pu*****@hotmail.com> wrote in message
news:0i*********************@news4.srv.hcvlny.cv.n et... "Dietmar Kuehl" <di***********@yahoo.com> wrote Use a 128bit integer (eg. made out of four longs): I doubt that this one will overflow on any currently available machine before the sun (note, not the SUN) cheases to exist. Even if you account for faster processors you should be on the safe side. Gaa! Do people no longer do basic backofthe envelope calculations?
If a 5GHz computer had an integer increment that took only one CPU cycle
and did NOTHING but increment a 64bit int 5 billion times per second 24hours
a day without interruption, it would take 117 _YEARS_ before you ran out of numbers!!! If you throw in the obligatory jump to implement the loop and made the jump also take a single CPU cycle, the duration leaps to a
whopping 234 years.
The most generous thing I can say about using a 128bit integer for this purpose is that it's absurdly overengineered. There's a lot worse that could be said about the idea.
Claudio Puviani
My envelopes must be old. They only support 32bit math. :)
Howard  
P: n/a

Siemel Naran wrote: Then maybe we can use the protected member 'c'.
'std::priority_queue' actually just uses 'std::make_heap', etc. Anyway,
accessing the member directly is no good: the internal organization of
the heap essentially makes immediate stability without some tool
impossible.
Anyway, what is a priority_queue? Is it just like a queue, except that items with the highest priority get retrieved by top() and pop() first?
This is the interface description: It has operations 'empty()', 'top()',
'pop()', and 'push()' like a 'std::stack' and what a 'std::queue' should
have, too (unfortunately, the latter uses 'front()' instead of 'top()').
However, the internal organization of the priority queue is a little bit
more involved.
How do they achieve O(lg(N)) for both push and pop (ie. how does the heap work?).
The essential idea of several heap structure is to maintain the heap
property: the heap is viewed as a tree and each tree has its minimum
element in the root (reverse the comparison and it has the maximum
element in the root; this does not really matter as long as you stick
with one definition  I will use the minimum). In the container stored
in the 'std::priority_queue' a binary tree is implicitly stored: the
element with index '0' is the root. The children of a node with index
'n' are the nodes with '2 * (n + 1)  1' and '2 * (n + 1)'. The parent
of the node 'n' is the node '(n  1) / 2' (I guess, I got the numbers
wrong somewhere; just draw a picture and number the nodes and things
should be relatively easy to work out). In any case, the tree is fully
balanced.
Inserting into a heap is pretty simple: you add a node to the lowest
level and exchange it with its parent if the parent has a bigger key.
This far, the representation of the tree does not at all matter and
other heaps, eg. a Fibonacciheap, use a different structure than an
array to hold a heap although they also maintain the heap property.
Since the heap in the array is balanced, insertion takes at most
O(log n) steps.
Extracting from a heap, is also simple: you simply exchange the root
with the last element and bubble down the root again: check which of
the child nodes is the smaller one and exchange the node with this
child until the node is smaller than both children. This again takes
at most O(log n) steps.
This form of heap is called a "dheap" in its general form where "d"
is the arity of the tree: the same approach works with nonbinary
trees, too, although the computation of child and parent nodes changes
slightly. When I compared different priority queues, I found that
"d == 5" had the best performance for integer values stored in the
heap. An even bigger 'd' is probably better if the nodes itself become
bigger. Of course, this was based on a few tests with my own
implementation and probably does not hold up to a scientific analysis.
Other forms of priority queues provide additional capabilities, eg.
ability to change the key for the priority fast. Of some interest in
this direction are Fibonacciheaps which can do changes of the keys
in such a form that it becomes amortized constant, at least when using
it for Dijkstra's algorithms for finding shortest paths (I don't
remember the details; it is possible that it is amortized constant in
general applications, too).

<mailto:di***********@yahoo.com> <http://www.dietmarkuehl.de/>
<http://www.contendix.com>  Software Development & Consulting  
P: n/a

Siemel Naran wrote: Then maybe we can use the protected member 'c'.
'std::priority_queue' actually just uses 'std::make_heap', etc. Anyway,
accessing the member directly is no good: the internal organization of
the heap essentially makes immediate stability without some tool
impossible.
Anyway, what is a priority_queue? Is it just like a queue, except that items with the highest priority get retrieved by top() and pop() first?
This is the interface description: It has operations 'empty()', 'top()',
'pop()', and 'push()' like a 'std::stack' and what a 'std::queue' should
have, too (unfortunately, the latter uses 'front()' instead of 'top()').
However, the internal organization of the priority queue is a little bit
more involved.
How do they achieve O(lg(N)) for both push and pop (ie. how does the heap work?).
The essential idea of several heap structure is to maintain the heap
property: the heap is viewed as a tree and each tree has its minimum
element in the root (reverse the comparison and it has the maximum
element in the root; this does not really matter as long as you stick
with one definition  I will use the minimum). In the container stored
in the 'std::priority_queue' a binary tree is implicitly stored: the
element with index '0' is the root. The children of a node with index
'n' are the nodes with '2 * (n + 1)  1' and '2 * (n + 1)'. The parent
of the node 'n' is the node '(n  1) / 2' (I guess, I got the numbers
wrong somewhere; just draw a picture and number the nodes and things
should be relatively easy to work out). In any case, the tree is fully
balanced.
Inserting into a heap is pretty simple: you add a node to the lowest
level and exchange it with its parent if the parent has a bigger key.
This far, the representation of the tree does not at all matter and
other heaps, eg. a Fibonacciheap, use a different structure than an
array to hold a heap although they also maintain the heap property.
Since the heap in the array is balanced, insertion takes at most
O(log n) steps.
Extracting from a heap, is also simple: you simply exchange the root
with the last element and bubble down the root again: check which of
the child nodes is the smaller one and exchange the node with this
child until the node is smaller than both children. This again takes
at most O(log n) steps.
This form of heap is called a "dheap" in its general form where "d"
is the arity of the tree: the same approach works with nonbinary
trees, too, although the computation of child and parent nodes changes
slightly. When I compared different priority queues, I found that
"d == 5" had the best performance for integer values stored in the
heap. An even bigger 'd' is probably better if the nodes itself become
bigger. Of course, this was based on a few tests with my own
implementation and probably does not hold up to a scientific analysis.
Other forms of priority queues provide additional capabilities, eg.
ability to change the key for the priority fast. Of some interest in
this direction are Fibonacciheaps which can do changes of the keys
in such a form that it becomes amortized constant, at least when using
it for Dijkstra's algorithms for finding shortest paths (I don't
remember the details; it is possible that it is amortized constant in
general applications, too).

<mailto:di***********@yahoo.com> <http://www.dietmarkuehl.de/>
<http://www.contendix.com>  Software Development & Consulting  
P: n/a

Claudio Puviani wrote: "Dietmar Kuehl" <di***********@yahoo.com> wrote Use a 128bit integer (eg. made out of four longs): I doubt that this one will overflow on any currently available machine before the sun (note, not the SUN) cheases to exist. Even if you account for faster processors you should be on the safe side. Gaa! Do people no longer do basic backofthe envelope calculations?
I had to study mathematics because I'm notoriously bad at
calculating things and mathematics is the only more or less
technical topic where you don't need to do calculations  you
only prove that they can be done. With 128bit I'm definitely
on the safe side...
If a 5GHz computer had an integer increment that took only one CPU cycle and did NOTHING but increment a 64bit int 5 billion times per second 24hours a day without interruption, it would take 117 _YEARS_ before you ran out of numbers!!! If you throw in the obligatory jump to implement the loop and made the jump also take a single CPU cycle, the duration leaps to a whopping 234 years.
Well, this computation seems reasonable (even though I'm not fit
to verifying it). Actually, the OP mentioned that this approach
does not work for him and all I wanted to do in this area is to
show that it is just a question of how many bits you spend to
make the approach work.
The most generous thing I can say about using a 128bit integer for this purpose is that it's absurdly overengineered. There's a lot worse that could be said about the idea.
To me, the difference of using 128bits or 64bits is not really
there: yes, I need twice as much memory but who cares? The template
class for doing simple arithmetics does not care how many (unsigned)
longs it takes for its representation and there is no portable
64bit integer. Overengineered? I'd say I was too lazy to do a more
precise computation.

<mailto:di***********@yahoo.com> <http://www.dietmarkuehl.de/>
<http://www.contendix.com>  Software Development & Consulting  
P: n/a

Claudio Puviani wrote: "Dietmar Kuehl" <di***********@yahoo.com> wrote Use a 128bit integer (eg. made out of four longs): I doubt that this one will overflow on any currently available machine before the sun (note, not the SUN) cheases to exist. Even if you account for faster processors you should be on the safe side. Gaa! Do people no longer do basic backofthe envelope calculations?
I had to study mathematics because I'm notoriously bad at
calculating things and mathematics is the only more or less
technical topic where you don't need to do calculations  you
only prove that they can be done. With 128bit I'm definitely
on the safe side...
If a 5GHz computer had an integer increment that took only one CPU cycle and did NOTHING but increment a 64bit int 5 billion times per second 24hours a day without interruption, it would take 117 _YEARS_ before you ran out of numbers!!! If you throw in the obligatory jump to implement the loop and made the jump also take a single CPU cycle, the duration leaps to a whopping 234 years.
Well, this computation seems reasonable (even though I'm not fit
to verifying it). Actually, the OP mentioned that this approach
does not work for him and all I wanted to do in this area is to
show that it is just a question of how many bits you spend to
make the approach work.
The most generous thing I can say about using a 128bit integer for this purpose is that it's absurdly overengineered. There's a lot worse that could be said about the idea.
To me, the difference of using 128bits or 64bits is not really
there: yes, I need twice as much memory but who cares? The template
class for doing simple arithmetics does not care how many (unsigned)
longs it takes for its representation and there is no portable
64bit integer. Overengineered? I'd say I was too lazy to do a more
precise computation.

<mailto:di***********@yahoo.com> <http://www.dietmarkuehl.de/>
<http://www.contendix.com>  Software Development & Consulting  
P: n/a

"Dietmar Kuehl" <di***********@yahoo.com> wrote in message
news:c4upai$2miv4i$1@ID Siemel Naran wrote:
Then maybe we can use the protected member 'c'.
'std::priority_queue' actually just uses 'std::make_heap', etc. Anyway, accessing the member directly is no good: the internal organization of the heap essentially makes immediate stability without some tool impossible.
I don't understand what you mean. The protected member 'c' is already has
the data organized in the exact manner. Thus
void MyPriorityQueue::write() const {
std::ofstream file("MyPriorityQueue.dat");
file << c;
};
void MyPriorityQueue::read() const {
std::ifstream file("MyPriorityQueue.dat");
file >> c;
container_type c2 = c;
std::make_heap(c2.begin(), c2.end());
assert(std::equal(c2.begin(), c2.end(), c.begin());
}; How do they achieve O(lg(N)) for both push and pop (ie. how does the
heap work?).
The essential idea of several heap structure is to maintain the heap property: the heap is viewed as a tree and each tree has its minimum element in the root (reverse the comparison and it has the maximum element in the root; this does not really matter as long as you stick with one definition  I will use the minimum). In the container stored in the 'std::priority_queue' a binary tree is implicitly stored: the element with index '0' is the root. The children of a node with index 'n' are the nodes with '2 * (n + 1)  1' and '2 * (n + 1)'. The parent of the node 'n' is the node '(n  1) / 2' (I guess, I got the numbers wrong somewhere; just draw a picture and number the nodes and things should be relatively easy to work out). In any case, the tree is fully balanced.
Thanks for jogging my memory. I implemented it once. It was an array of
fixed length (2^n)1, and was essentially a perfectly balanced binary tree
stored in a regular C array.
Now out of curiosity, how much faster is a heap implemented through
std::priority_queue<T, std::vector<T>> using make_heap, over one implemented
through std::set<T>.
A related question. Have you or anyone measured the time improvement of
inserting N elements into a std::vector<T> using reserve(N) and
push_back(const value_type&) and calling strd::sort, versus inserting N
elements into a std::multimap<T> by calling insert(const value_type&)?
Inserting into a heap is pretty simple: you add a node to the lowest level and exchange it with its parent if the parent has a bigger key. This far, the representation of the tree does not at all matter and other heaps, eg. a Fibonacciheap, use a different structure than an array to hold a heap although they also maintain the heap property. Since the heap in the array is balanced, insertion takes at most O(log n) steps.
Extracting from a heap, is also simple: you simply exchange the root with the last element and bubble down the root again: check which of the child nodes is the smaller one and exchange the node with this child until the node is smaller than both children. This again takes at most O(log n) steps.
This form of heap is called a "dheap" in its general form where "d" is the arity of the tree: the same approach works with nonbinary trees, too, although the computation of child and parent nodes changes slightly. When I compared different priority queues, I found that "d == 5" had the best performance for integer values stored in the heap. An even bigger 'd' is probably better if the nodes itself become bigger. Of course, this was based on a few tests with my own implementation and probably does not hold up to a scientific analysis.
What does this term "arity" mean? Perhaps the heap I implemented has arity
= 2 because each parent has 2 children? What do you mean by the "nodes
itself become bigger"? Is it that sizeof(T) where T is the object stored in
the heap gets bigger, or that the number of nodes increases?
Other forms of priority queues provide additional capabilities, eg. ability to change the key for the priority fast. Of some interest in this direction are Fibonacciheaps which can do changes of the keys in such a form that it becomes amortized constant, at least when using it for Dijkstra's algorithms for finding shortest paths (I don't remember the details; it is possible that it is amortized constant in general applications, too).
Thanks for the info. Changing a key in O(1) time is fascinating.  
P: n/a

"Dietmar Kuehl" <di***********@yahoo.com> wrote in message
news:c4upai$2miv4i$1@ID Siemel Naran wrote:
Then maybe we can use the protected member 'c'.
'std::priority_queue' actually just uses 'std::make_heap', etc. Anyway, accessing the member directly is no good: the internal organization of the heap essentially makes immediate stability without some tool impossible.
I don't understand what you mean. The protected member 'c' is already has
the data organized in the exact manner. Thus
void MyPriorityQueue::write() const {
std::ofstream file("MyPriorityQueue.dat");
file << c;
};
void MyPriorityQueue::read() const {
std::ifstream file("MyPriorityQueue.dat");
file >> c;
container_type c2 = c;
std::make_heap(c2.begin(), c2.end());
assert(std::equal(c2.begin(), c2.end(), c.begin());
}; How do they achieve O(lg(N)) for both push and pop (ie. how does the
heap work?).
The essential idea of several heap structure is to maintain the heap property: the heap is viewed as a tree and each tree has its minimum element in the root (reverse the comparison and it has the maximum element in the root; this does not really matter as long as you stick with one definition  I will use the minimum). In the container stored in the 'std::priority_queue' a binary tree is implicitly stored: the element with index '0' is the root. The children of a node with index 'n' are the nodes with '2 * (n + 1)  1' and '2 * (n + 1)'. The parent of the node 'n' is the node '(n  1) / 2' (I guess, I got the numbers wrong somewhere; just draw a picture and number the nodes and things should be relatively easy to work out). In any case, the tree is fully balanced.
Thanks for jogging my memory. I implemented it once. It was an array of
fixed length (2^n)1, and was essentially a perfectly balanced binary tree
stored in a regular C array.
Now out of curiosity, how much faster is a heap implemented through
std::priority_queue<T, std::vector<T>> using make_heap, over one implemented
through std::set<T>.
A related question. Have you or anyone measured the time improvement of
inserting N elements into a std::vector<T> using reserve(N) and
push_back(const value_type&) and calling strd::sort, versus inserting N
elements into a std::multimap<T> by calling insert(const value_type&)?
Inserting into a heap is pretty simple: you add a node to the lowest level and exchange it with its parent if the parent has a bigger key. This far, the representation of the tree does not at all matter and other heaps, eg. a Fibonacciheap, use a different structure than an array to hold a heap although they also maintain the heap property. Since the heap in the array is balanced, insertion takes at most O(log n) steps.
Extracting from a heap, is also simple: you simply exchange the root with the last element and bubble down the root again: check which of the child nodes is the smaller one and exchange the node with this child until the node is smaller than both children. This again takes at most O(log n) steps.
This form of heap is called a "dheap" in its general form where "d" is the arity of the tree: the same approach works with nonbinary trees, too, although the computation of child and parent nodes changes slightly. When I compared different priority queues, I found that "d == 5" had the best performance for integer values stored in the heap. An even bigger 'd' is probably better if the nodes itself become bigger. Of course, this was based on a few tests with my own implementation and probably does not hold up to a scientific analysis.
What does this term "arity" mean? Perhaps the heap I implemented has arity
= 2 because each parent has 2 children? What do you mean by the "nodes
itself become bigger"? Is it that sizeof(T) where T is the object stored in
the heap gets bigger, or that the number of nodes increases?
Other forms of priority queues provide additional capabilities, eg. ability to change the key for the priority fast. Of some interest in this direction are Fibonacciheaps which can do changes of the keys in such a form that it becomes amortized constant, at least when using it for Dijkstra's algorithms for finding shortest paths (I don't remember the details; it is possible that it is amortized constant in general applications, too).
Thanks for the info. Changing a key in O(1) time is fascinating.  
P: n/a

"Claudio Puviani" <pu*****@hotmail.com> wrote in message news:0izcc.26080 Gaa! Do people no longer do basic backofthe envelope calculations?
If a 5GHz computer had an integer increment that took only one CPU cycle
and did NOTHING but increment a 64bit int 5 billion times per second 24hours
a day without interruption, it would take 117 _YEARS_ before you ran out of numbers!!! If you throw in the obligatory jump to implement the loop and made the jump also take a single CPU cycle, the duration leaps to a
whopping 234 years.
How do you get 117 years? In a 64 integer there are 2^64 = 1.84... * 10^19
possible numbers. In one year we can perform 86,400 seconds * 5 billion
increments/second = 4.32 * 10^14 increments. I believe 1 billion = 10^9.
Then 2^64 / 4.32e14 = 42700 years. What am I doing wrong in my calculation?
For 32 bit integers, I get 2^32 / 4.32e14 = 9.94e6 years which is less than
one day.
So now the question is how to get a 64 bit integer. On some platforms, this
will be int, on others long, and on others long long. BTW, is long long a
standard type? My compiler Borland 6 accepts long long but not long long
long.
I thought people proposed adding int32, int64 to the standard. Is there any
update on this?
We could also use std::bitset<64>, but it doesn't have an operator++ or
operator+.
We could also use the sizeof trick though, which is a cool use of template
template parameters.
const int CHAR_BITS=8;
template <class T>
struct Eq16
{
static const bool result=((sizeof(T)*CHAR_BITS)==16);
};
void test_find_typelist(ostream& out)
{
typedef typelist<int, typelist<short, typelist<char> > > BasicTypes;
typedef find_typelist<Eq16, BasicTypes>::result int16;
out << sizeof(int16) << '\n'; // print 2
}
where
template <class T, class U=void>
struct typelist
{
typedef T car;
typedef U cdr;
};
template <template <class> class Predicate, class list>
struct typelist_find
{
typedef typename list::car car;
typedef typename list::cdr cdr;
typedef typename
template_if<
Predicate<car>::result,
car,
typename find_typelist<Predicate,cdr>::result :: result
result;
};
template <template <class> class Predicate>
struct typelist_find<Predicate,void>
{
typedef void result;
};
The most generous thing I can say about using a 128bit integer for this purpose is that it's absurdly overengineered. There's a lot worse that could be said about the idea.
Such as?
Anyway, quantum computers of the future may indeed be much faster. But as a
practical matter I'd just use long long.  
P: n/a

"Claudio Puviani" <pu*****@hotmail.com> wrote in message news:0izcc.26080 Gaa! Do people no longer do basic backofthe envelope calculations?
If a 5GHz computer had an integer increment that took only one CPU cycle
and did NOTHING but increment a 64bit int 5 billion times per second 24hours
a day without interruption, it would take 117 _YEARS_ before you ran out of numbers!!! If you throw in the obligatory jump to implement the loop and made the jump also take a single CPU cycle, the duration leaps to a
whopping 234 years.
How do you get 117 years? In a 64 integer there are 2^64 = 1.84... * 10^19
possible numbers. In one year we can perform 86,400 seconds * 5 billion
increments/second = 4.32 * 10^14 increments. I believe 1 billion = 10^9.
Then 2^64 / 4.32e14 = 42700 years. What am I doing wrong in my calculation?
For 32 bit integers, I get 2^32 / 4.32e14 = 9.94e6 years which is less than
one day.
So now the question is how to get a 64 bit integer. On some platforms, this
will be int, on others long, and on others long long. BTW, is long long a
standard type? My compiler Borland 6 accepts long long but not long long
long.
I thought people proposed adding int32, int64 to the standard. Is there any
update on this?
We could also use std::bitset<64>, but it doesn't have an operator++ or
operator+.
We could also use the sizeof trick though, which is a cool use of template
template parameters.
const int CHAR_BITS=8;
template <class T>
struct Eq16
{
static const bool result=((sizeof(T)*CHAR_BITS)==16);
};
void test_find_typelist(ostream& out)
{
typedef typelist<int, typelist<short, typelist<char> > > BasicTypes;
typedef find_typelist<Eq16, BasicTypes>::result int16;
out << sizeof(int16) << '\n'; // print 2
}
where
template <class T, class U=void>
struct typelist
{
typedef T car;
typedef U cdr;
};
template <template <class> class Predicate, class list>
struct typelist_find
{
typedef typename list::car car;
typedef typename list::cdr cdr;
typedef typename
template_if<
Predicate<car>::result,
car,
typename find_typelist<Predicate,cdr>::result :: result
result;
};
template <template <class> class Predicate>
struct typelist_find<Predicate,void>
{
typedef void result;
};
The most generous thing I can say about using a 128bit integer for this purpose is that it's absurdly overengineered. There's a lot worse that could be said about the idea.
Such as?
Anyway, quantum computers of the future may indeed be much faster. But as a
practical matter I'd just use long long.  
P: n/a

Siemel Naran wrote in
news:Fc********************@bgtnsc05news.ops.worldnet.att.net: How do you get 117 years? In a 64 integer there are 2^64 = 1.84... * 10^19 possible numbers. In one year we can perform 86,400 seconds * 5 billion increments/second = 4.32 * 10^14 increments. I believe 1 billion = 10^9. Then 2^64 / 4.32e14 = 42700 years. What am I doing wrong in my calculation?
For 32 bit integers, I get 2^32 / 4.32e14 = 9.94e6 years which is less than one day.
86,400 == 24 * 60 * 60 i.e. the No. of seconds in 1 day *not* 1 year.
I put 'days in a year' into google and got:
1 year = 365.242199 days, following there calculator link I did:
42700 / 365.242199 and got:
42700 / 365.242199 = 116.908726
Rob.
 http://www.victimprime.dsl.pipex.com/  
P: n/a

Siemel Naran wrote in
news:Fc********************@bgtnsc05news.ops.worldnet.att.net: How do you get 117 years? In a 64 integer there are 2^64 = 1.84... * 10^19 possible numbers. In one year we can perform 86,400 seconds * 5 billion increments/second = 4.32 * 10^14 increments. I believe 1 billion = 10^9. Then 2^64 / 4.32e14 = 42700 years. What am I doing wrong in my calculation?
For 32 bit integers, I get 2^32 / 4.32e14 = 9.94e6 years which is less than one day.
86,400 == 24 * 60 * 60 i.e. the No. of seconds in 1 day *not* 1 year.
I put 'days in a year' into google and got:
1 year = 365.242199 days, following there calculator link I did:
42700 / 365.242199 and got:
42700 / 365.242199 = 116.908726
Rob.
 http://www.victimprime.dsl.pipex.com/  
P: n/a

Siemel Naran wrote: So now the question is how to get a 64 bit integer. On some platforms, this will be int, on others long, and on others long long. BTW, is long long a standard type? My compiler Borland 6 accepts long long but not long long long.
#include <boost/cstdint.hpp>
uint64_t n;

Regards,
Buster.  
P: n/a

Siemel Naran wrote: So now the question is how to get a 64 bit integer. On some platforms, this will be int, on others long, and on others long long. BTW, is long long a standard type? My compiler Borland 6 accepts long long but not long long long.
#include <boost/cstdint.hpp>
uint64_t n;

Regards,
Buster.  
P: n/a

"Siemel Naran" <Si*********@REMOVE.att.net> wrote: Siemel Naran wrote: Then maybe we can use the protected member 'c'.
'std::priority_queue' actually just uses 'std::make_heap', etc. Anyway, accessing the member directly is no good: the internal organization of the heap essentially makes immediate stability without some tool impossible.
I don't understand what you mean. The protected member 'c' is already has the data organized in the exact manner.
The problem is, that you cannot get stable behavior of the priority queue
through simply manipulating the member 'c' in an 'std::priority_queue'.
The way elements in a priority queue simple does not provide any useful
form of stability  unless you somehow encode the order in the key used
for comparison.
Thanks for jogging my memory. I implemented it once. It was an array of fixed length (2^n)1, and was essentially a perfectly balanced binary tree stored in a regular C array.
I implemented a bunch of heap variations, including two array based version
(one allowing key modification, the other not allowing it; the one allowing
key modifications is a *lot* slower!). The implementation should be available
from <http://www.dietmarkuehl.de/cxxrt/heaps.tar.gz>.
Now out of curiosity, how much faster is a heap implemented through std::priority_queue<T, std::vector<T>> using make_heap, over one implemented through std::set<T>.
It depends somewhat on 'T': if 'T' is expensive to copy or swap, the vector
version will probably eventually become slower with increasing costs. For
'T' being something like 'int' the vector version is something like ten
times faster than typical node based approaches, including sets. At least,
this is what I seem to remember from running very naive tests.
A related question. Have you or anyone measured the time improvement of inserting N elements into a std::vector<T> using reserve(N) and push_back(const value_type&) and calling strd::sort, versus inserting N elements into a std::multimap<T> by calling insert(const value_type&)?
I don't know for the inserts themselves but if the set of elements is fixed,
using an array with binary search is *much* faster than using 'std::map' or
'std::multimap' (again, I don't have current figures...). Likewise, a hash
(see eg. the library TR's 'std::tr1::unordered_map' and
'std::tr1::unordered_multimap') is much faster. Of course, these figure also
depend somewhat on the data types. This form of heap is called a "dheap" in its general form where "d" is the arity of the tree: the same approach works with nonbinary trees, too, although the computation of child and parent nodes changes slightly. When I compared different priority queues, I found that "d == 5" had the best performance for integer values stored in the heap. An even bigger 'd' is probably better if the nodes itself become bigger. Of course, this was based on a few tests with my own implementation and probably does not hold up to a scientific analysis.
What does this term "arity" mean? Perhaps the heap I implemented has arity = 2 because each parent has 2 children?
Yes, this is what I mean with "arity": the [maximum] number of children of a
node. Of course, in a dheap only leaves and at most one other node have less
than 'd' children.
What do you mean by the "nodes itself become bigger"? Is it that sizeof(T) where T is the object stored in the heap gets bigger, or that the number of nodes increases?
I mean 'sizeof(T)', ie. the data stored in a node: with bigger 'd' the number
of necessary moves when modifying the heap becomes smaller. If the type 'T'
is "bigger" or at least more expensive to move, the cost of the moves
are more dominant than the costs of other operations.
[relating to Fibonacciheaps]
Thanks for the info. Changing a key in O(1) time is fascinating.
It is not O(1), it is *amortized* O(1): occasionally a higher costs is
incurred but if this cost can be averaged over multiple operations and
then becomes O(1) again. Of course, changing the key involves reordering
the corresponding node such that the other performance guarantees still
hold. Just the actual change of the key is trivially O(1) but doing the
reordering in amortized O(1) is somewhat tricky.

<mailto:di***********@yahoo.com> <http://www.dietmarkuehl.de/>
<www.contendix.com>  Software Development & Consulting  
P: n/a

"Siemel Naran" <Si*********@REMOVE.att.net> wrote: Siemel Naran wrote: Then maybe we can use the protected member 'c'.
'std::priority_queue' actually just uses 'std::make_heap', etc. Anyway, accessing the member directly is no good: the internal organization of the heap essentially makes immediate stability without some tool impossible.
I don't understand what you mean. The protected member 'c' is already has the data organized in the exact manner.
The problem is, that you cannot get stable behavior of the priority queue
through simply manipulating the member 'c' in an 'std::priority_queue'.
The way elements in a priority queue simple does not provide any useful
form of stability  unless you somehow encode the order in the key used
for comparison.
Thanks for jogging my memory. I implemented it once. It was an array of fixed length (2^n)1, and was essentially a perfectly balanced binary tree stored in a regular C array.
I implemented a bunch of heap variations, including two array based version
(one allowing key modification, the other not allowing it; the one allowing
key modifications is a *lot* slower!). The implementation should be available
from <http://www.dietmarkuehl.de/cxxrt/heaps.tar.gz>.
Now out of curiosity, how much faster is a heap implemented through std::priority_queue<T, std::vector<T>> using make_heap, over one implemented through std::set<T>.
It depends somewhat on 'T': if 'T' is expensive to copy or swap, the vector
version will probably eventually become slower with increasing costs. For
'T' being something like 'int' the vector version is something like ten
times faster than typical node based approaches, including sets. At least,
this is what I seem to remember from running very naive tests.
A related question. Have you or anyone measured the time improvement of inserting N elements into a std::vector<T> using reserve(N) and push_back(const value_type&) and calling strd::sort, versus inserting N elements into a std::multimap<T> by calling insert(const value_type&)?
I don't know for the inserts themselves but if the set of elements is fixed,
using an array with binary search is *much* faster than using 'std::map' or
'std::multimap' (again, I don't have current figures...). Likewise, a hash
(see eg. the library TR's 'std::tr1::unordered_map' and
'std::tr1::unordered_multimap') is much faster. Of course, these figure also
depend somewhat on the data types. This form of heap is called a "dheap" in its general form where "d" is the arity of the tree: the same approach works with nonbinary trees, too, although the computation of child and parent nodes changes slightly. When I compared different priority queues, I found that "d == 5" had the best performance for integer values stored in the heap. An even bigger 'd' is probably better if the nodes itself become bigger. Of course, this was based on a few tests with my own implementation and probably does not hold up to a scientific analysis.
What does this term "arity" mean? Perhaps the heap I implemented has arity = 2 because each parent has 2 children?
Yes, this is what I mean with "arity": the [maximum] number of children of a
node. Of course, in a dheap only leaves and at most one other node have less
than 'd' children.
What do you mean by the "nodes itself become bigger"? Is it that sizeof(T) where T is the object stored in the heap gets bigger, or that the number of nodes increases?
I mean 'sizeof(T)', ie. the data stored in a node: with bigger 'd' the number
of necessary moves when modifying the heap becomes smaller. If the type 'T'
is "bigger" or at least more expensive to move, the cost of the moves
are more dominant than the costs of other operations.
[relating to Fibonacciheaps]
Thanks for the info. Changing a key in O(1) time is fascinating.
It is not O(1), it is *amortized* O(1): occasionally a higher costs is
incurred but if this cost can be averaged over multiple operations and
then becomes O(1) again. Of course, changing the key involves reordering
the corresponding node such that the other performance guarantees still
hold. Just the actual change of the key is trivially O(1) but doing the
reordering in amortized O(1) is somewhat tricky.

<mailto:di***********@yahoo.com> <http://www.dietmarkuehl.de/>
<www.contendix.com>  Software Development & Consulting  
P: n/a

Claudio Puviani wrote: Gaa! Do people no longer do basic backofthe envelope calculations?
Yes, in fact.
If a 5GHz computer had an integer increment that took only one CPU cycle and did NOTHING but increment a 64bit int 5 billion times per second 24hours a day without interruption, it would take 117 _YEARS_ before you ran out of numbers!!! If you throw in the obligatory jump to implement the loop and made the jump also take a single CPU cycle, the duration leaps to a whopping 234 years.
Well, my original question was related to a rewrite of some fairly
critical support code within a library that my organization intends to
reuse for many projects in the future. It is the intent that the code
be written such that its useful lifetime may be maximized. Certainly,
the code is expected to be useful for at least a decade.
Lets say this code is eventually applied to some sort of computer
intended to run for a year without restarting. (Not coincidentally,
this is the goal for some of our present systems.) If a 64bit integer
was used, as I assume you are suggesting, that would mean the processor
or processors handling this queue could handle no more than about
600,000,000,000 elements per second. You are quite right to note that
the best processor availible presently at a reasonable price is safe by
a margin of several orders of magnitude. However, in ten years, do you
think you will still be safe? What about multiprocessor systems, which,
by the way, many are predicting will someday be commonplace in even
ordinary PCs? I don't know about you, but ten years ago, I think I was
using a 32MHz 386.
The most generous thing I can say about using a 128bit integer for this purpose is that it's absurdly overengineered. There's a lot worse that could be said about the idea.
Speaking of absurd engineering:
unsigned long long stamp; /* XXX FIXME hello if you are a programmer
working on this code in 2014, could you please check to make sure this
is still big enough? */
I have been trainedand I beleive the training to be goodto not make
assumptions in code I write that may well not be true in the foreseeable
future. That is largely why I posted to this group.
On the other hand, I would feel a lot better about using 96 bits or 128
bits. By the time those integers would overflow, with any luck, I'll be
a rich, retired man. I was concerned, though, that the stamp portion of
the queue element was a lot larger than the rest of the data, and this
would have an unfortunate effect on efficiency. Oh well. :)
I wonder if people posting concerns about Y2K wraparound in the 1980's
were also flamed?
Aaron W. LaFramboise  
P: n/a

Claudio Puviani wrote: Gaa! Do people no longer do basic backofthe envelope calculations?
Yes, in fact.
If a 5GHz computer had an integer increment that took only one CPU cycle and did NOTHING but increment a 64bit int 5 billion times per second 24hours a day without interruption, it would take 117 _YEARS_ before you ran out of numbers!!! If you throw in the obligatory jump to implement the loop and made the jump also take a single CPU cycle, the duration leaps to a whopping 234 years.
Well, my original question was related to a rewrite of some fairly
critical support code within a library that my organization intends to
reuse for many projects in the future. It is the intent that the code
be written such that its useful lifetime may be maximized. Certainly,
the code is expected to be useful for at least a decade.
Lets say this code is eventually applied to some sort of computer
intended to run for a year without restarting. (Not coincidentally,
this is the goal for some of our present systems.) If a 64bit integer
was used, as I assume you are suggesting, that would mean the processor
or processors handling this queue could handle no more than about
600,000,000,000 elements per second. You are quite right to note that
the best processor availible presently at a reasonable price is safe by
a margin of several orders of magnitude. However, in ten years, do you
think you will still be safe? What about multiprocessor systems, which,
by the way, many are predicting will someday be commonplace in even
ordinary PCs? I don't know about you, but ten years ago, I think I was
using a 32MHz 386.
The most generous thing I can say about using a 128bit integer for this purpose is that it's absurdly overengineered. There's a lot worse that could be said about the idea.
Speaking of absurd engineering:
unsigned long long stamp; /* XXX FIXME hello if you are a programmer
working on this code in 2014, could you please check to make sure this
is still big enough? */
I have been trainedand I beleive the training to be goodto not make
assumptions in code I write that may well not be true in the foreseeable
future. That is largely why I posted to this group.
On the other hand, I would feel a lot better about using 96 bits or 128
bits. By the time those integers would overflow, with any luck, I'll be
a rich, retired man. I was concerned, though, that the stamp portion of
the queue element was a lot larger than the rest of the data, and this
would have an unfortunate effect on efficiency. Oh well. :)
I wonder if people posting concerns about Y2K wraparound in the 1980's
were also flamed?
Aaron W. LaFramboise  
P: n/a

"Dietmar Kuehl" <di***********@yahoo.com> wrote in message "Siemel Naran" <Si*********@REMOVE.att.net> wrote:
Then maybe we can use the protected member 'c'.
'std::priority_queue' actually just uses 'std::make_heap', etc. Anyway, accessing the member directly is no good: the internal organization of the heap essentially makes immediate stability without some tool impossible.
I don't understand what you mean. The protected member 'c' is already
has the data organized in the exact manner. The problem is, that you cannot get stable behavior of the priority queue through simply manipulating the member 'c' in an 'std::priority_queue'. The way elements in a priority queue simple does not provide any useful form of stability  unless you somehow encode the order in the key used for comparison.
Why not? Yes, it could be a problem if we write the container 'c' in one
platform/compiler that implements heaps one way, then read the container 'c'
in another platform/compiler that implements heaps another way. But if we
read and write on the same platform it should be OK, right? Thanks for jogging my memory. I implemented it once. It was an array
of fixed length (2^n)1, and was essentially a perfectly balanced binary
tree stored in a regular C array.
I implemented a bunch of heap variations, including two array based
version (one allowing key modification, the other not allowing it; the one
allowing key modifications is a *lot* slower!). The implementation should be
available from <http://www.dietmarkuehl.de/cxxrt/heaps.tar.gz>.
Thanks for this and all the other info.
I think if T objects get big we could use shared_ptr<T> objects instead. Now out of curiosity, how much faster is a heap implemented through std::priority_queue<T, std::vector<T>> using make_heap, over one
implemented through std::set<T>.
It depends somewhat on 'T': if 'T' is expensive to copy or swap, the
vector version will probably eventually become slower with increasing costs. For 'T' being something like 'int' the vector version is something like ten times faster than typical node based approaches, including sets. At least, this is what I seem to remember from running very naive tests.
A related question. Have you or anyone measured the time improvement of inserting N elements into a std::vector<T> using reserve(N) and push_back(const value_type&) and calling strd::sort, versus inserting N elements into a std::multimap<T> by calling insert(const value_type&)? I don't know for the inserts themselves but if the set of elements is
fixed, using an array with binary search is *much* faster than using 'std::map'
or 'std::multimap' (again, I don't have current figures...). Likewise, a hash (see eg. the library TR's 'std::tr1::unordered_map' and 'std::tr1::unordered_multimap') is much faster. Of course, these figure
also depend somewhat on the data types. This form of heap is called a "dheap" in its general form where "d" is the arity of the tree: the same approach works with nonbinary trees, too, although the computation of child and parent nodes changes slightly. When I compared different priority queues, I found that "d == 5" had the best performance for integer values stored in the heap. An even bigger 'd' is probably better if the nodes itself become bigger. Of course, this was based on a few tests with my own implementation and probably does not hold up to a scientific analysis. What does this term "arity" mean? Perhaps the heap I implemented has
arity = 2 because each parent has 2 children?
Yes, this is what I mean with "arity": the [maximum] number of children of
a node. Of course, in a dheap only leaves and at most one other node have
less than 'd' children.
What do you mean by the "nodes itself become bigger"? Is it that
sizeof(T) where T is the object stored in the heap gets bigger, or that the number
of nodes increases? I mean 'sizeof(T)', ie. the data stored in a node: with bigger 'd' the
number of necessary moves when modifying the heap becomes smaller. If the type
'T' is "bigger" or at least more expensive to move, the cost of the moves are more dominant than the costs of other operations.
[relating to Fibonacciheaps]
Thanks for the info. Changing a key in O(1) time is fascinating.
It is not O(1), it is *amortized* O(1): occasionally a higher costs is incurred but if this cost can be averaged over multiple operations and then becomes O(1) again. Of course, changing the key involves reordering the corresponding node such that the other performance guarantees still hold. Just the actual change of the key is trivially O(1) but doing the reordering in amortized O(1) is somewhat tricky.  
P: n/a

"Dietmar Kuehl" <di***********@yahoo.com> wrote in message "Siemel Naran" <Si*********@REMOVE.att.net> wrote:
Then maybe we can use the protected member 'c'.
'std::priority_queue' actually just uses 'std::make_heap', etc. Anyway, accessing the member directly is no good: the internal organization of the heap essentially makes immediate stability without some tool impossible.
I don't understand what you mean. The protected member 'c' is already
has the data organized in the exact manner. The problem is, that you cannot get stable behavior of the priority queue through simply manipulating the member 'c' in an 'std::priority_queue'. The way elements in a priority queue simple does not provide any useful form of stability  unless you somehow encode the order in the key used for comparison.
Why not? Yes, it could be a problem if we write the container 'c' in one
platform/compiler that implements heaps one way, then read the container 'c'
in another platform/compiler that implements heaps another way. But if we
read and write on the same platform it should be OK, right? Thanks for jogging my memory. I implemented it once. It was an array
of fixed length (2^n)1, and was essentially a perfectly balanced binary
tree stored in a regular C array.
I implemented a bunch of heap variations, including two array based
version (one allowing key modification, the other not allowing it; the one
allowing key modifications is a *lot* slower!). The implementation should be
available from <http://www.dietmarkuehl.de/cxxrt/heaps.tar.gz>.
Thanks for this and all the other info.
I think if T objects get big we could use shared_ptr<T> objects instead. Now out of curiosity, how much faster is a heap implemented through std::priority_queue<T, std::vector<T>> using make_heap, over one
implemented through std::set<T>.
It depends somewhat on 'T': if 'T' is expensive to copy or swap, the
vector version will probably eventually become slower with increasing costs. For 'T' being something like 'int' the vector version is something like ten times faster than typical node based approaches, including sets. At least, this is what I seem to remember from running very naive tests.
A related question. Have you or anyone measured the time improvement of inserting N elements into a std::vector<T> using reserve(N) and push_back(const value_type&) and calling strd::sort, versus inserting N elements into a std::multimap<T> by calling insert(const value_type&)? I don't know for the inserts themselves but if the set of elements is
fixed, using an array with binary search is *much* faster than using 'std::map'
or 'std::multimap' (again, I don't have current figures...). Likewise, a hash (see eg. the library TR's 'std::tr1::unordered_map' and 'std::tr1::unordered_multimap') is much faster. Of course, these figure
also depend somewhat on the data types. This form of heap is called a "dheap" in its general form where "d" is the arity of the tree: the same approach works with nonbinary trees, too, although the computation of child and parent nodes changes slightly. When I compared different priority queues, I found that "d == 5" had the best performance for integer values stored in the heap. An even bigger 'd' is probably better if the nodes itself become bigger. Of course, this was based on a few tests with my own implementation and probably does not hold up to a scientific analysis. What does this term "arity" mean? Perhaps the heap I implemented has
arity = 2 because each parent has 2 children?
Yes, this is what I mean with "arity": the [maximum] number of children of
a node. Of course, in a dheap only leaves and at most one other node have
less than 'd' children.
What do you mean by the "nodes itself become bigger"? Is it that
sizeof(T) where T is the object stored in the heap gets bigger, or that the number
of nodes increases? I mean 'sizeof(T)', ie. the data stored in a node: with bigger 'd' the
number of necessary moves when modifying the heap becomes smaller. If the type
'T' is "bigger" or at least more expensive to move, the cost of the moves are more dominant than the costs of other operations.
[relating to Fibonacciheaps]
Thanks for the info. Changing a key in O(1) time is fascinating.
It is not O(1), it is *amortized* O(1): occasionally a higher costs is incurred but if this cost can be averaged over multiple operations and then becomes O(1) again. Of course, changing the key involves reordering the corresponding node such that the other performance guarantees still hold. Just the actual change of the key is trivially O(1) but doing the reordering in amortized O(1) is somewhat tricky.  
P: n/a

"Siemel Naran" <Si*********@REMOVE.att.net> wrote in message
news:FcQcc.30166 We could also use std::bitset<64>, but it doesn't have an operator++ or operator+.
Anyway know how to implement a quick operator++ for std::bitset?  
P: n/a

"Siemel Naran" <Si*********@REMOVE.att.net> wrote in message
news:FcQcc.30166 We could also use std::bitset<64>, but it doesn't have an operator++ or operator+.
Anyway know how to implement a quick operator++ for std::bitset?  
P: n/a

"Siemel Naran" <Si*********@REMOVE.att.net> wrote "Claudio Puviani" <pu*****@hotmail.com> wrote
If a 5GHz computer had an integer increment that took only one CPU cycle and did NOTHING but increment a 64bit int 5 billion times per second 24hours a day without interruption, it would take 117 _YEARS_ before you ran out of numbers!!! If you throw in the obligatory jump to implement the loop and made the jump also take a single CPU cycle, the duration leaps to a whopping 234 years.
How do you get 117 years? In a 64 integer there are 2^64 = 1.84... * 10^19 possible numbers. In one year we can perform 86,400 seconds * 5 billion increments/second = 4.32 * 10^14 increments. I believe 1 billion = 10^9. Then 2^64 / 4.32e14 = 42700 years. What am I doing wrong in my calculation?
Ops/sec = 5e9
Ops/min = 5e9 ops/sec * 60 sec/min = 3e11
Ops/hr = 3e11 ops/min * 60 min/hr = 1.8e13
Ops/day = 1.8e13 ops/hr * 24 hr/day = 4.32e14
Ops/yr = 4.32e14 ops/day * 365 day/year = 1.577e17
Ops = 2^64 = 1.84e19
Duration = 1.84e19 ops / 1.577e17 ops/yr = 117 years
It looks like you just forgot to factor in the 365 days per year.
Claudio Puviani  
P: n/a

"Siemel Naran" <Si*********@REMOVE.att.net> wrote "Claudio Puviani" <pu*****@hotmail.com> wrote
If a 5GHz computer had an integer increment that took only one CPU cycle and did NOTHING but increment a 64bit int 5 billion times per second 24hours a day without interruption, it would take 117 _YEARS_ before you ran out of numbers!!! If you throw in the obligatory jump to implement the loop and made the jump also take a single CPU cycle, the duration leaps to a whopping 234 years.
How do you get 117 years? In a 64 integer there are 2^64 = 1.84... * 10^19 possible numbers. In one year we can perform 86,400 seconds * 5 billion increments/second = 4.32 * 10^14 increments. I believe 1 billion = 10^9. Then 2^64 / 4.32e14 = 42700 years. What am I doing wrong in my calculation?
Ops/sec = 5e9
Ops/min = 5e9 ops/sec * 60 sec/min = 3e11
Ops/hr = 3e11 ops/min * 60 min/hr = 1.8e13
Ops/day = 1.8e13 ops/hr * 24 hr/day = 4.32e14
Ops/yr = 4.32e14 ops/day * 365 day/year = 1.577e17
Ops = 2^64 = 1.84e19
Duration = 1.84e19 ops / 1.577e17 ops/yr = 117 years
It looks like you just forgot to factor in the 365 days per year.
Claudio Puviani   This discussion thread is closed Replies have been disabled for this discussion.   Question stats  viewed: 4852
 replies: 38
 date asked: Jul 22 '05
