Colin Nielsen wrote:
Furthermore, I launched r.cost on a 295 rows, 378 cols matrix, and it's
taking > 1h, whereas I did the same previously and it ran in tens of
seconds.
The speed of r.cost depends not just on the number of cells but also
the complexity of the surface. Smoother surfaces seem to take longer
than rough ones, I think because there are more possibilities for the
algorithm to explore.
Could it be that the binary tree implementation in r.cost is not balanced? If yes, the search tree may degenerate on smooth surfaces towards a linked list, search time going from O(log n) to O(n). BTW, there are now three different generic balanced binary search tree implementations in the vector libs, plus sorted heaps. Just an idea.
Markus M
Markus Metz ha scritto:
Could it be that the binary tree implementation in r.cost is not
balanced? If yes, the search tree may degenerate on smooth surfaces
towards a linked list, search time going from O(log n) to O(n). BTW,
there are now three different generic balanced binary search tree
implementations in the vector libs, plus sorted heaps. Just an idea.
Tested on two different machines, (ubuntu+debian) 3 diff surfaces,
always the same result. It seems something more structural.
But, is r.cost working for somebody else?
--
Paolo Cavallini: http://faunalia.it/pc
Paolo Cavallini ha scritto:
Markus Metz ha scritto:
Could it be that the binary tree implementation in r.cost is not
balanced? If yes, the search tree may degenerate on smooth surfaces
towards a linked list, search time going from O(log n) to O(n). BTW,
there are now three different generic balanced binary search tree
implementations in the vector libs, plus sorted heaps. Just an idea.
Tested on two different machines, (ubuntu+debian) 3 diff surfaces,
always the same result. It seems something more structural.
But, is r.cost working for somebody else?
Further info: with very simple maps, everitying goes obviously fast, but
it gets mangled after printing:
Finding cost path
Does this help?
All the best.
--
Paolo Cavallini: http://faunalia.it/pc
On Wed, Apr 1, 2009 at 7:40 PM, Paolo Cavallini <cavallini@faunalia.it> wrote:
Markus Metz ha scritto:
Could it be that the binary tree implementation in r.cost is not
balanced? If yes, the search tree may degenerate on smooth surfaces
towards a linked list, search time going from O(log n) to O(n). BTW,
there are now three different generic balanced binary search tree
implementations in the vector libs, plus sorted heaps. Just an idea.
Tested on two different machines, (ubuntu+debian) 3 diff surfaces,
always the same result. It seems something more structural.
Or 6.3.0 is a bit old?
But, is r.cost working for somebody else?
Yes (example from the manual page):
# Spearfish
GRASS 6.5.svn (spearfish60): > g.region rast=roads -p
projection: 1 (UTM)
zone: 13
datum: nad27
ellipsoid: clark66
north: 4928010
south: 4913700
west: 589980
east: 609000
nsres: 30
ewres: 30
rows: 477
cols: 634
cells: 302418
GRASS 6.5.svn (spearfish60): > r.mapcalc "area.one=1"
100%
GRASS 6.5.svn (spearfish60): > time -p r.cost -k input=area.one
output=distance start_rast=roads
Reading raster map <area.one@neteler>...
100%
Initializing output...
100%
Reading raster map <roads>...
100%
Finding cost path...
100%
No data
Writing raster map <distance>...
100%
r.cost complete. Peak cost value: 87.970583.
real 1.65
user 1.50
sys 0.09
1.7 seconds looks ok...
Relevant post-6.3.0 fix:
2008-07-24 06:32 martinl
* main.c: Fix calculation of number of segments (round up instead of
down) [merged from trunk, r32239]
Please send me a minimalistic location to try here...
Best
Markus
Paolo Cavallini wrote:
Paolo Cavallini ha scritto:
Markus Metz ha scritto:
Could it be that the binary tree implementation in r.cost is not
balanced? If yes, the search tree may degenerate on smooth surfaces
towards a linked list, search time going from O(log n) to O(n). BTW,
there are now three different generic balanced binary search tree
implementations in the vector libs, plus sorted heaps. Just an idea.
Tested on two different machines, (ubuntu+debian) 3 diff surfaces,
always the same result. It seems something more structural.
My comment was a suggestion to Colin Nielson to use another binary tree in r.cost if the current tree is not a balanced tree, and that there are generic balanced binary tree implementations in the vector libs that can be used by other developers in their modules. AFAIKT r.cost uses the same binary tree implementation in all versions, i.e. the results and the speed should be similar on different machines and with different grass versions.