Boost logo

Boost :

From: Jens Müller (jens.mueller_at_[hidden])
Date: 2006-05-30 09:49:43


My questions are concerning this part:

> std::size_t adj_start_row = row == 0? 0 : row - 1;
> std::size_t adj_end_row = row == rows - 1? row : row + 1;
> std::size_t adj_start_column = column == 0? 0 : column - 1;
> std::size_t adj_end_column = column == columns - 1? column : column + 1;
> for (std::size_t other_row = adj_start_row; other_row <= adj_end_row;
> ++other_row)
> for (std::size_t other_column = adj_start_column;
> other_column <= adj_end_column; ++other_column)
> if (other_row != row || other_column != column) {
> // Repulse vertices in this bucket
> bucket_t& other_bucket
> = buckets[other_row * columns + other_column];
> for (v = other_bucket.begin(); v != other_bucket.end(); ++v)
> apply_force(*u, *v);
> }

In the code above, where repelling forces inside a bucket are computed,
each pair of nodes is considered only once, and then

apply_force(*u, *v);
apply_force(*v, *u);

are called.

Wouldn't something like this be more efficient here, too?

We have

+------+------+------+
| | | |
| 1 | 2 | 3 |
| | | |
|------|------|------|
| | | |
| 4 | X | 6 |
| | | |
|------|------|------|
| | | |
| 7 | 8 | 9 |
| | | |
+------+------+------+,

where X is the bucket u resides in, and the others are the adjacent
buckets considered.

For every u, all nodes from all other buckets are considered.

My proposal: Consider only 1, 2, 3 and 4 and
do
 apply_force(*u, *v);
 apply_force(*v, *u);
again

6, 7, 8 and 9 will be considered when those buckets are processed.

Shouldn't this be (at least a bit) more efficient?


Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk