[GRASS-dev] Re: [GRASS-user] v.dissolve and r.cost problems

[Markus Metz]

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