Opened 11 years ago

Closed 11 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 11 years ago.

Download all attachments as: .zip

Change History (7)

comment:1 Changed 11 years ago by msieczka

CPU: UnspecifiedAll
Platform: UnspecifiedAll

Please attach the code.

comment:2 in reply to:  1 ; Changed 11 years ago by 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

comment:3 in reply to:  2 Changed 11 years ago by 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 ;).

comment:4 Changed 11 years ago by neteler

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

Markus

comment:5 Changed 11 years ago by mmetz

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

Changed 11 years ago by mmetz

Attachment: r.watershed.diff added

comment:6 Changed 11 years ago by hamish

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