|
|
|
|
Subject: RE: quickest algorithm for calculating buffer area
From: Christophe LE PAGE (christophe.le_page@cirad.fr)
Date: Fri Mar 05 2010 - 01:20:58 CET
Hi Nico,
IMO, your algo is already running reasonably fast!
Below the code I used to test it (I removed instructions related to
dictionary and assumed that by “x” and “y” you meant “numCol” and “numLine”.
buffer2CellsAt: dist
|aa bb cc cells|
cc := dist * dist.
cells := Set new.
self spaceModel cormasModel theCells do:[:c|
c ~= self ifTrue:[
aa := (c numCol - self numCol).
bb := (self numLine - c numLine).
((aa * aa ) + (bb * bb )) < cc ifTrue:[cells add:c]]].
^cells
I did some testing in a 150*150 grid and collected data plotted in the chart
below (red curve) through this instruction:
1 to: 75
do:
[:i |
(Time millisecondsToRun: [self buffer2CellsAt: i]) printOn:
Transcript.
Transcript cr]
The point is that your algorithm is consuming the same amount of time (about
40-50 ms in a grid 150*150 according to my testing) whatever the size of the
buffer. This is because it systematically tests all the cells of the grid.
For small buffer sizes it is faster (see blue curve) to test a reduced
squared block (size = dist) you can obtain directly through indexes of cells
from intervals based on numLine and numCol (see code below).
buffer1CellsAt: dist
| aa bb cc cells i c |
cc := dist * dist.
cells := Set new.
(self numLine - dist max: 1)
to: (self numLine + dist min: self spaceModel line)
do:
[:y |
(self numCol - dist max: 1)
to: (self numCol + dist min: self spaceModel
column)
do:
[:x |
i := x + ((y - 1) * self spaceModel
column).
c := self spaceModel elementaryEntities
at: i.
aa := c numCol - self numCol.
bb := self numLine - c numLine.
aa * aa + (bb * bb) < cc ifTrue: [cells
add: c]]].
cells remove: self.
^cells
It may be only advantageous to replace your algorithm by this one if the
buffers are relatively small compared to the size of the grid.
HTH, clp
> -----Message d'origine-----
> De : owner-cormas@cirad.cirad.fr [mailto:owner-cormas@cirad.cirad.fr] De
la
> part de Becu Nicolas
> Envoyé : jeudi 4 mars 2010 16:10
> À : Cormas
> Objet : quickest algorithm for calculating buffer area
>
> Hello everyone,
>
> On a model I have an extensive use of buffer areas (the cells that are
> at a maximum distance X of another cell).
> I need to use this so much that I'm trying to reduce as much as possible
> the calculation time required for this method.
>
> I manage to gain time since the first method I used but it's still quiet
> long and I would like to ask you if you have quicker solution than the
> one I'm using.
>
> //some details on the model// the grid I'm using is 129*129 and the
> buffers are 23 cells around the central cell.Most of the cells have to
> calculate their buffer once or more during a simulation
>
> At first I had try using ""allLayersTo: radius "" or
> ""recursiveNeighbourhood"" but I found out the calculation was quicker
> when I use the x and y coordinates of the cells (in top of that using
> the x and y cordinates to calculate the circle around a cell, allows me
> to have a circular buffer instead of quadrilateral buffer when using
> neighborhood calculation // I have squared shape cells)
>
> This is the algorithm I'm currently using.
> Any idea how this algorithm could be improve ?
>
> bufferCellsAt: dist
> |aa bb cc cells|
> "I use at the Cell level a dictionary that stores the results of the
> buffers that have already been calculated so that if I need to get the
> same buffer a second time, it is not calculated it again and the result
> is just fecth in the dictionary"
> (self dicoBufferCells includesKey: dist) ifFalse:
> ["this is the algorithm for identifying the cells that
> compose the buffer area"
> cc := dist * dist.
> cells := Set new.
> self spaceModel cormasModel theCells do:[:c|
> c ~= self ifTrue:[
> aa := (c x - self x).
> bb := (self y - c y).
> ((aa * aa ) + (bb * bb )) < cc ifTrue:[cells
> add:c]]].
> self dicoBufferCells at: dist put:cells ].
> ^self dicoBufferCells at: dist
>
>
> Thanks,
> Nicolas
