Opened 16 years ago

Closed 16 years ago

#237 closed enhancement (fixed)

r.watershed: speed improvement

Reported by: mmetz Owned by: grass-dev@…
Priority: minor Milestone: 6.4.0
Component: Raster Version: 6.3.0
Keywords: r.watershed speed Cc:
CPU: All Platform: All

Description

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.

Attachments (1)

r.watershed.diff (13.1 KB ) - added by mmetz 16 years ago.

Download all attachments as: .zip

Change History (7)

comment:1 by msieczka, 16 years ago

CPU: UnspecifiedAll
Platform: UnspecifiedAll

Please attach the code.

in reply to:  1 ; comment:2 by mmetz, 16 years ago

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

in reply to:  2 comment:3 by msieczka, 16 years ago

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 ;).

comment:4 by neteler, 16 years ago

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

Markus

comment:5 by mmetz, 16 years ago

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

by mmetz, 16 years ago

Attachment: r.watershed.diff added

comment:6 by hamish, 16 years ago

Resolution: fixed
Status: newclosed
Note: See TracTickets for help on using tickets.