[Top][All Lists]

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: [ipchat-devel] pqueue

From: Matías Aguirre
Subject: Re: [ipchat-devel] pqueue
Date: 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
realloc, jeje.

> * 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:
> http://sourceware.org/autobook/autobook/autobook_56.html
> ...

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[1] 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.



Matías Aguirre

reply via email to

[Prev in Thread] Current Thread [Next in Thread]