[GRASS-dev] [GRASS GIS] #237: r.watershed: speed improvement

[GRASS GIS]

#237: r.watershed: speed improvement
-------------------------------+--------------------------------------------
 Reporter:  mmetz              |       Owner:  grass-dev at lists.osgeo.org
     Type:  enhancement        |      Status:  new                      
 Priority:  minor              |   Milestone:  6.4.0                    
Component:  Raster             |     Version:  6.3.0                    
 Keywords:  r.watershed speed  |    Platform:  Unspecified              
      Cpu:  Unspecified        |  
-------------------------------+--------------------------------------------
 I want to suggest a new sorting algorithm for <SECTION 2: A * Search> in
 r.watershed.

 The A * Search is only interested in the cell with the lowest elevation
 within the list of candidates, in case of several cells with equal
 elevation, in the cell that was added earliest to the list. This can be
 done with a binary min-heap and would not change the A * algorithm, it
 would provide near identical results with a substantial increase in speed.

 Using a binary min-heap, r.watershed is faster than r.terraflow. Compared
 to the currently used linear array, speed improvement with a binary heap
 as sorting method is not constant, but increases with the number of cells
 analysed.

-- 
Ticket URL: <http://trac.osgeo.org/grass/ticket/237>
GRASS GIS <http://grass.osgeo.org>