priority queues (was: Configuration file parser)

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']

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.
.

Relevant Pages

  • Re: priority queues (was: Configuration file parser)
    ... This is a more expensive algorithm than it would need to be. ... If you don't care, don't care. ... I'm all for writing fast code. ...
    (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)