|
|
|
|
Subject: Re: quickest algorithm for calculating buffer area
From: Serge Stinckwich (serge.stinckwich@gmail.com)
Date: Mon Mar 08 2010 - 04:28:01 CET
Did you try to do a pre-calculation of buffers ? Something like :
for each cells of the environment, store in a array :
8 von neuman neighbors at distance 1 + 16 von neumann neighbors at distance
2 + 32 von neumann neighbors at distance 3 + ...
This is a very huge array (maybe only suitable for neighbors at a distance
less than 10), but after you did that, you could find the neighbors of a
cell very easily (the cells between two indices in the array).
BTW, you could also use the Smalltalk profiler in order to understand how
the time is use in your code.
Best regards,
On Sun, Mar 7, 2010 at 9:31 PM, Nicolas Becu <nicolas.becu@gmail.com> wrote:
> Thanks Jean-Pierre and Christophe for your help.
>
>
> The algo you propose Christophe is just great. It's really going to save me
> a lot of time ;).
>
>
> I tried improve it a bit more, first by saving in a temporary variable the
> maximum numCol and numLine of the cells already accepted as being in the
> buffer and then testing the candidates to see if their numLine and numCol
> are below these values (in which case they are in the buffer and no need to
> calculate the aa * aa + (bb * bb) < cc
> Yet, it didn't really save time.
>
> Surprisingly I found a "variant' of your code that is almost twice quicker,
> and which only consists in replacing the access methods ("self numLine",
> "self spaceModel elementaryEntities", etc...) by temporary variables (pink
> curve in the attached file)
>
> Here it is
>
> buffer6CellsAt: dist
> | aa bb cc cells i c sx sy spcol elemEnt|
> cc := dist * dist.
> cells := Set new.
> sx := self numLine.
> sy := self numCol.
> spcol := self spaceModel column.
> elemEnt := self spaceModel elementaryEntities.
> (sx - dist max: 1)
> to: (sx + dist min: self spaceModel line)
> do: [:y | (sy - dist max: 1)
> to: (sy + dist min: spcol)
> do: [:x |
> i := x + ((y - 1) * spcol).
> c := elemEnt at: i.
> aa := c numCol -sy.
> bb := sx - c numLine.
> aa * aa + (bb * bb) < cc ifTrue: [cells add: c]]].
> cells remove: self.
> ^cells
>
>
>
> Thanks again for your help.
>
> Nicolas
>
>
>
> 010/3/5 Christophe LE PAGE <christophe.le_page@cirad.fr>
>
>>
>>
>> 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
>>
>>
>>
>
>
-- Serge Stinckwich UMI UMMISCO 209 (IRD/UPMC), Hanoi, Vietnam Smalltalkers do: [:it | All with: Class, (And love: it)] http://doesnotunderstand.org/
