[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: [ipchat-devel] pqueue
Re: [ipchat-devel] pqueue
Sat, 19 Mar 2005 09:41:20 -0300
On Sat, 12 Mar 2005 21:12:24 +0100, Maximiliano Pin <address@hidden> wrote:
> I've been studying the priority queue. It's a good algorithm.
> I took some annotations:
Congratulations for looking at the priority queue, as you say it's a
good algorithm, and really nice when you take hands on it.
> * I think I found a case where the sorting fails:
You are right and wrong, the sorting fails but it works fine, if you
keep using the queue (like a priority queue must be used) you will see
that the nodes come in the correct sequence. But I agree that it's
better an intelligent (direction select) sorting (like pq_chpri do).
Thanks for noting this.
> * The function pq_requeue could be simplified and optimized a lot.
> I suggest something like:
I already have a little fight with the realloc function, and as you
can see it was the winner (don't repet please, jeje). But I have
already seen that the code produced by usign this function was really
nice. As far I can see you won the fight, now the pqueue will use
> * There is a nice trick I learned from the autobook. You may increase the
> efficiency a lot, and reduce the code size, by removing one level of
> indirection in the nodes. Here it is:
The *trick* is a great idea, but it's a good idea to improve
efficiency in ipchat. I'm agree with the idea of took some source and
modify it to work in the better way for my program.
> * I'd change DEFAULT_SZ to 127 so a power of 2 is reserved ((127+1)*4 =
> 512). Also, in pq_requeue, put "+1" in: q->heap=new_heap(q->size*2);
> so the new size is also power of 2.
Yes it's nice, I defined it to 100 in some moment of pqueue life, and
never saw it again.
> * If I understood the algorithm well, it is impossible to have a hole (a
> NULL pointer) among heap and heap[csize]. So, there are a few functions
> which could be optimized. For example, I'd change pos() to:
Yes, it looks like it's impossible to have a hole, and yes it's a bug.
> * I noted the macro
My mmacro's (and variable's) names are the worst in the programming
history, so any rename are welcome.
> * In new_heap(), you initialize all the pointers to NULL, but calloc()
> already initializes the whole buffer to zero, so this is not needed.
> * I think I will make timer_id's be timer_pq_node pointers, and remove the
> current sequential identifiers (which may overflow). This will make it
> unnecesary to create a temporal node for comparisons, and the timer_eq
> function will be reduced to a comparison of pointers.
I'ts a good idea, so there musn't be to make the timer_id managment, and it's e
> Nice job!! See you soon.