Re: priority queues (was: Configuration file parser)

Rainer Weikusat <rweikusat@xxxxxxxxxxx> writes:

Måns Rullgård <mans@xxxxxxxxx> writes:

[...]

This is of course nothing but a shameless plug for my library,

extern int
tcprioq_add(tcprioq_t *pq, void *data)
{
int i, r = 0;

[...]

i = pq->count;
pq->qt[i] = data;

while(i > 1 && pq->cmp(pq->qt[i/2], pq->qt[i]) > 0){
void *tmp = pq->qt[i];
pq->qt[i] = pq->qt[i/2];
pq->qt[i/2] = tmp;
i /= 2;
}

This is a more expensive algorithm than it would need to be. As
R. Sedgewick has written in his various 'algorithms and data
structures' books, it is not necessary to have two 'moving
assignments' in the loop, because one of them always assigns the same
value. An example of this (in Perl, because that was where I needed it
last) would be:

sub put
{
our @q;
local *q = $_[0];
local *pred = $q[PRED];

my $item = $_[1];
my ($ndx, $pred_ndx, $pred_item);

$ndx = $#q + 1;
while ($ndx > OFS) { # OFS is the 'start index'
$pred_ndx = $ndx >> 1;

$pred_item = $q[$pred_ndx];
last if pred($pred_item, $item);

$q[$ndx] = $pred_item;
$ndx = $pred_ndx;
}

$q[$ndx] = $item;
}

[ pred is unfortunately used for both 'predicate' and
'predecessor']

Thanks. I wrote that code years ago, and apparently didn't consult
the right books first.

This is not an invitation to start a 'but the computers are sooo fast
today and I CERTAINLY DON'T CARE, so YOU are CLEARLY AN IDIOT!!1'
flamewar. If you don't care, don't care.

I'm all for writing fast code. My day job is on embedded systems
where we really do care about every cycle.

--
Måns Rullgård
mans@xxxxxxxxx
.

Relevant Pages

  • priority queues (was: Configuration file parser)
    ... This is a more expensive algorithm than it would need to be. ... This is not an invitation to start a 'but the computers are sooo fast ... If you don't care, don't care. ...
    (comp.os.linux.development.apps)
  • Re: Major qla2xxx regression on sparc64
    ... On Mon, 16 Apr 2007, Andrew Vasquez wrote: ... Now I'm happy to code up the sparc OFW property bits but your attitude ... to take care of your system configurations? ... extern int ql2xextended_error_logging; ...
    (Linux-Kernel)