r.watershed: speed improvement

[mmetz]

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.

[msieczka]

Please attach the code.

[mmetz]

I have a stupid question: in what form? Only the files I changed, diff output, or the whole directory with modified front and makefiles so that the front will be called r.watershed.fast and call r.watershed.ram.fast instead of r.watershed.ram?

I did not yet attach the code because the mailing list etiquette strongly discourages that and it is publicly available at ​http://markus.metz.giswork.googlepages.com/r.watershed_fast_version.tar.gz

[msieczka]

Replying to mmetz:

I have a stupid question: in what form?

Hmm, really don't know. Anybody? (At worst, if nobody replies, please attach the whole dir.)

it is publicly available at ​http://markus.metz.giswork.googlepages.com/r.watershed_fast_version.tar.gz

The website might dissapear in some time whereas Trac is here to last forever ;).

[neteler]

trac offers an "attach file" button - it would be best to add here an uncompressed, complete diff.

Markus

[mmetz]

the attached diff would result in program name r.watershed and not r.watershed.fast