This example contains a few different ideas for how you might remove some
coordinate wrapping that can occurs writing filtering routines in arrays
The program has a 2D array full of colour values, that array is then
averaged by a filtering each cell with the cells around it. This is done 10
times to get some idea of how long the process takes. So we have the simple
version, which is slow through to a slightly more cumbersome version that's
around 3 times quicker on my test system.
[pbcode]
/*
*=-----------------------------------------------------------------------------=*
>> Array Wrapping / Filtering / Sampling Speed Ideas V001 <<
By Kevin Picone
6th,Aug,2017
*=-----------------------------------------------------------------------------=*
This example contains a few different ideas for how you might remove some
coordinate wrapping that can occurs writing filtering routines in arrays
The program has a 2D array full of colour values, that array is then
averaged by a filtering each cell with the cells around it. This is done 10
times to get some idea of how long the process takes. So we have the simple
version, which is slow through to a slightly more cumbersome version that's
around 3 times quicker on my test system.
*=-----------------------------------------------------------------------------=*
*=-----------------------------------------------------------------------------=*
*=-----------------------------------------------------------------------------=*
*=-----------------------------------------------------------------------------=*
*/
Width =500
Height=500
Dim BackupMap#(Width,Height)
Dim InputMap#(Width,Height)
Dim OutputMap#(Width,Height)
RandomizeArray(InputMap#())
BackupMap#()=InputMap#()
Passes = 10
Method =1
TotalMethods = 10
Dim Results#(TotalMethods)
for Method = 1 to TotalMethods
MethodName$="AverageArray_V"+digits$(Method,4)
if FunctionExist(MethodName$)
InputMap#()=BackupMap#()
for lp=0 to Passes
// time how old this function takes in milliseconds..
// we average out the time later to get a better idea of the result
StartTime=Timer()
CallFunction MethodName$, InputMap#(),OutputMap#()
Results#(Method)+=(Timer()-StartTime)
DrawArray(OutputMap#())
setcursor 0,0
print MethodName$+" Pass:"+Str$(lp)+" of "+str$(Passes)
Sync
swapArray InputMap#(),OutputMap#()
next
endif
next
print "---------------------------------------"
print "Results:"
print "---------------------------------------"
for Method = 1 to TotalMethods
MethodName$="AverageArray_V"+digits$(Method,4)
if FunctionExist(MethodName$)
print MethodName$ +" Time:"+str$(Results#(Method) / Passes)+" Per pass"
endif
next
Sync
waitkey
waitnokey
// --------------------------------------------------------------------------------------
// --------------------------------------------------------------------------------------
// --------------------->> AVERAGE ARRAY V0001 (SLOW BUT FLEXIBLE) <<---------------------------------------
// --------------------------------------------------------------------------------------
// --------------------------------------------------------------------------------------
Function AverageArray_V0001(SrcArray#(),DestArray#())
GridSize=4
// Here we'll assume the SRC and DEST are the sa me size.. to save some time
w=getarrayelements(SrcArray#(),1)
h=getarrayelements(SrcArray#(),2)
for ylp=0 to h
for xlp=0 to w
// Read all the cells around this point
Total#=0
For Sy = ylp-1 to ylp+1
For Sx = xlp-1 to xlp+1
Total#+=SrcArray#(wrapvalue( sx,0,w) ,wrapvalue(sy,0,h))
next
next
// drop the result into the output array
DestArray#(Xlp,ylp)=Total#/9
next
next
EndFunction
// --------------------------------------------------------------------------------------
// --------------------------------------------------------------------------------------
// --------------------->> AVERAGE ARRAY V0002 (LESS WRAPS PER SAMPLE) <<---------------------------------------
// --------------------------------------------------------------------------------------
// --------------------------------------------------------------------------------------
Function AverageArray_V0002(SrcArray#(),DestArray#())
GridSize=4
// Here we'll assume the SRC and DEST are the sa me size.. to save some time
w=getarrayelements(SrcArray#(),1)
h=getarrayelements(SrcArray#(),2)
for ylp=0 to h
Ylp_MinusOne = wrapvalue(ylp-1,0,h)
Ylp_PlusOne = wrapvalue(ylp+1,0,h)
for xlp=0 to w
// Read all the cells around this point
Total#=0
For Sx = xlp-1 to xlp+1
wx=wrapvalue( sx,0,w)
Total#+=SrcArray#(wx ,ylp_MinusOne)
Total#+=SrcArray#(wx ,ylp)
Total#+=SrcArray#(wx ,ylp_PLusOne)
next
// drop the result into the output array
DestArray#(Xlp,ylp)=Total#/9
next
next
EndFunction
// --------------------------------------------------------------------------------------
// --------------------------------------------------------------------------------------
// --------------------->> AVERAGE ARRAY V0002 (Two Passes) <<---------------------------------------
// --------------------------------------------------------------------------------------
// --------------------------------------------------------------------------------------
Function AverageArray_V0003(SrcArray#(),DestArray#())
GridSize=4
// Here we'll assume the SRC and DEST are the sa me size.. to save some time
w=getarrayelements(SrcArray#(),1)
h=getarrayelements(SrcArray#(),2)
// This version of the inner loop, does all the cells that don't need
// the coordinates wrapped, so the sampler doesn't hit the edges of the
// of the array, and we don't need to wrap it
h_minusOne = h-1
w_MinusOne = w-1
for ylp=1 to h_MinusOne
Ylp_MinusOne = wrapvalue(ylp-1,0,h)
Ylp_PlusOne = wrapvalue(ylp+1,0,h)
for xlp=1 to w_MinusOne
// Read all the cells around this point
Total#=0
For Sx = xlp-1 to xlp+1
Total#+=SrcArray#(sx ,ylp_MinusOne)
Total#+=SrcArray#(sx ,ylp)
Total#+=SrcArray#(sx ,ylp_PLusOne)
next
// drop the result into the output array
DestArray#(Xlp,ylp)=Total#/9
next
next
// Do Edges...
for ylp=0 to h
Ylp_MinusOne = wrapvalue(ylp-1,0,h)
Ylp_PlusOne = wrapvalue(ylp+1,0,h)
// Check if we'\re doing the first or last line ?
// if so, we do all cells on this row, otherwise only the first and last
Xstep = W
if Ylp=0 or Ylp=h then Xstep =1
for xlp=0 to w step Xstep
// Read all the cells around this point
Total#=0
For Sx = xlp-1 to xlp+1
wx=wrapvalue( sx,0,w)
Total#+=SrcArray#(wx ,ylp_MinusOne)
Total#+=SrcArray#(wx ,ylp)
Total#+=SrcArray#(wx ,ylp_PLusOne)
next
// drop the result into the output array
DestArray#(Xlp,ylp)=Total#/9
next
next
EndFunction
// --------------------------------------------------------------------------------------
// --------------------------------------------------------------------------------------
// --------------------->> DRAW ARRAY AS TILES <<---------------------------------------
// --------------------------------------------------------------------------------------
// --------------------------------------------------------------------------------------
Function DrawArray(ThisArray#())
GridSize=4
Sw=GetScreenWidth()
w=getarrayelements(ThisArray#(),1)
h=getarrayelements(ThisArray#(),2)
CellsAcross= sw/GridSize
CellsAcross+=((CellsAcross*GridSize)<Sw)
lockbuffer
for ylp=0 to h
Xpos=0
Ypos2=Ypos+GridSize
for xlp=0 to CellsAcross
Col=cliprange#( ThisArray#(xlp,ylp),0,255)
BoxC Xpos,Ypos,Xpos+GridSize,Ypos2,true, rgb(Col,Col,col)
Xpos+=GridSize
next
Ypos+=GridSize
if Ypos=>GetScreenHeight()
exit
endif
next
unlockbuffer
EndFunction
Function RandomizeArray(ThisArray#())
w=getarrayelements(ThisArray#(),1)
h=getarrayelements(ThisArray#(),2)
for ylp=0 to h
for xlp=0 to w
ThisArray#(xlp,ylp)=rnd#(255)
next
next
EndFunction
[/pbcode]
Related Optimization Links:
- A Crash Course In BASIC program Optimization (http://www.underwaredesign.com/forums/index.php?topic=2548.0)
- Global / Local Animation (http://www.underwaredesign.com/forums/index.php?topic=3604.0)
- Optimzation Ideas - Manually Finding The Closest Object (http://www.underwaredesign.com/forums/index.php?topic=3221.0)
- PlayBasic Optimization Tutorial - Cross fade Methods (http://www.underwaredesign.com/forums/index.php?topic=2890.0)
- Kaleidoscope (optimized) (http://www.underwaredesign.com/forums/index.php?topic=4111.0)
This example contains a few different ideas for how you might remove some coordinate wrapping and double reading that occurs writing filtering routines over arrays
The program has a 2D array full of colour values, that array is then averaged by filtering each cell with the cells around it. This is done 10 times to get some idea of how long the process takes. So we have the simple version, which is slow through to a slightly more cumbersome versions. The best way is to not re-read cells over and over so if you cache scan lines it can work a lot quicker. The version runs is around 6 times faster than the naive version... So well worth a little messing around if every need to write filter
[pbcode]
/*
*=-----------------------------------------------------------------------------=*
>> Array Filtering / Sampling Speed Ideas V002 <<
By Kevin Picone
6th,Aug,2017
*=-----------------------------------------------------------------------------=*
*=-----------------------------------------------------------------------------=*
*=-----------------------------------------------------------------------------=*
This example contains a few different ideas for how you might remove some
coordinate wrapping and double reading that occurs writing filtering routines
over arrays
The program has a 2D array full of colour values, that array is then
averaged by filtering each cell with the cells around it. This is done 10
times to get some idea of how long the process takes. So we have the simple
version, which is slow through to a slightly more cumbersome versions. The best
way is to not re-read cells over and over so if you cache scan lines it can
work a lot quicker. The version runs is around 6 times faster than the naive
version... So well worth a little messing around if every need to write filter
*=-----------------------------------------------------------------------------=*
*=-----------------------------------------------------------------------------=*
*=-----------------------------------------------------------------------------=*
*/
Width =500
Height=500
Dim BackupMap#(Width,Height)
Dim InputMap#(Width,Height)
Dim OutputMap#(Width,Height)
RandomizeArray(InputMap#())
BackupMap#()=InputMap#()
Passes = 10
Method =1
TotalMethods = 10
Dim Results#(TotalMethods)
// --------------------------------------------------------------------------
// MAIN TEST LOOP
// --------------------------------------------------------------------------
for Method = 1 to TotalMethods
MethodName$="AverageArray_V"+digits$(Method,4)
if FunctionExist(MethodName$)
// restore the input array with the original pattern
InputMap#()=BackupMap#()
// Run a bunch of average/samplinjg passes over the array
for lp=0 to Passes
// time how old this function takes in milliseconds..
// we average out the time later to get a better idea of the result
StartTime=Timer()
CallFunction MethodName$, InputMap#(),OutputMap#()
Results#(Method)+=(Timer()-StartTime)
DrawArray(OutputMap#())
setcursor 0,0
print MethodName$+" Pass:"+Str$(lp)+" of "+str$(Passes)
Sync
swapArray InputMap#(),OutputMap#()
next
endif
next
print "---------------------------------------"
print "Results:"
print "---------------------------------------"
print "Cells:"+Str$(Width*Height)
print ""
for Method = 1 to TotalMethods
MethodName$="AverageArray_V"+digits$(Method,4)
if FunctionExist(MethodName$)
print MethodName$ +" Time:"+str$(Results#(Method) / Passes)+" Per pass"
endif
next
Sync
waitkey
waitnokey
end
// --------------------------------------------------------------------------------------
// --------------------------------------------------------------------------------------
// --------------------->> AVERAGE ARRAY V0001 (SLOW BUT FLEXIBLE) <<---------------------------------------
// --------------------------------------------------------------------------------------
// --------------------------------------------------------------------------------------
Function AverageArray_V0001(SrcArray#(),DestArray#())
GridSize=4
// Here we'll assume the SRC and DEST are the sa me size.. to save some time
w=getarrayelements(SrcArray#(),1)
h=getarrayelements(SrcArray#(),2)
for ylp=0 to h
for xlp=0 to w
// Read all the cells around this point
Total#=0
For Sy = ylp-1 to ylp+1
For Sx = xlp-1 to xlp+1
Total#+=SrcArray#(wrapvalue( sx,0,w) ,wrapvalue(sy,0,h))
next
next
// drop the result into the output array
DestArray#(Xlp,ylp)=Total#/9
next
next
EndFunction
// --------------------------------------------------------------------------------------
// --------------------------------------------------------------------------------------
// --------------------->> AVERAGE ARRAY V0002 (LESS WRAPS PER SAMPLE) <<---------------------------------------
// --------------------------------------------------------------------------------------
// --------------------------------------------------------------------------------------
Function AverageArray_V0002(SrcArray#(),DestArray#())
GridSize=4
// Here we'll assume the SRC and DEST are the sa me size.. to save some time
w=getarrayelements(SrcArray#(),1)
h=getarrayelements(SrcArray#(),2)
for ylp=0 to h
Ylp_MinusOne = wrapvalue(ylp-1,0,h)
Ylp_PlusOne = wrapvalue(ylp+1,0,h)
for xlp=0 to w
// Read all the cells around this point
Total#=0
For Sx = xlp-1 to xlp+1
wx=wrapvalue( sx,0,w)
Total#+=SrcArray#(wx ,ylp_MinusOne)
Total#+=SrcArray#(wx ,ylp)
Total#+=SrcArray#(wx ,ylp_PLusOne)
next
// drop the result into the output array
DestArray#(Xlp,ylp)=Total#/9
next
next
EndFunction
// --------------------------------------------------------------------------------------
// --------------------------------------------------------------------------------------
// --------------------->> AVERAGE ARRAY V0003 (Two Passes) <<---------------------------------------
// --------------------------------------------------------------------------------------
// --------------------------------------------------------------------------------------
Function AverageArray_V0003(SrcArray#(),DestArray#())
GridSize=4
// Here we'll assume the SRC and DEST are the sa me size.. to save some time
w=getarrayelements(SrcArray#(),1)
h=getarrayelements(SrcArray#(),2)
// This version of the inner loop, does all the cells that don't need
// the coordinates wrapped, so the sampler doesn't hit the edges of the
// of the array, and we don't need to wrap it
h_minusOne = h-1
w_MinusOne = w-1
for ylp=1 to h_MinusOne
Ylp_MinusOne = wrapvalue(ylp-1,0,h)
Ylp_PlusOne = wrapvalue(ylp+1,0,h)
for xlp=1 to w_MinusOne
// Read all the cells around this point
Total#=0
For Sx = xlp-1 to xlp+1
Total#+=SrcArray#(sx ,ylp_MinusOne)
Total#+=SrcArray#(sx ,ylp)
Total#+=SrcArray#(sx ,ylp_PLusOne)
next
// drop the result into the output array
DestArray#(Xlp,ylp)=Total#/9
next
next
// Do Edges...
for ylp=0 to h
Ylp_MinusOne = wrapvalue(ylp-1,0,h)
Ylp_PlusOne = wrapvalue(ylp+1,0,h)
// Check if we'\re doing the first or last line ?
// if so, we do all cells on this row, otherwise only the first and last
Xstep = W
if Ylp=0 or Ylp=h then Xstep =1
for xlp=0 to w step Xstep
// Read all the cells around this point
Total#=0
For Sx = xlp-1 to xlp+1
wx=wrapvalue( sx,0,w)
Total#+=SrcArray#(wx ,ylp_MinusOne)
Total#+=SrcArray#(wx ,ylp)
Total#+=SrcArray#(wx ,ylp_PLusOne)
next
// drop the result into the output array
DestArray#(Xlp,ylp)=Total#/9
next
next
EndFunction
// --------------------------------------------------------------------------------------
// --------------------------------------------------------------------------------------
// --------------------->> AVERAGE ARRAY V0004 (Two Passes Unrolled) <<---------------------------------------
// --------------------------------------------------------------------------------------
// --------------------------------------------------------------------------------------
Function AverageArray_V0004(SrcArray#(),DestArray#())
GridSize=4
// Here we'll assume the SRC and DEST are the sa me size.. to save some time
w=getarrayelements(SrcArray#(),1)
h=getarrayelements(SrcArray#(),2)
// This version of the inner loop, does all the cells that don't need
// the coordinates wrapped, so the sampler doesn't hit the edges of the
// of the array, and we don't need to wrap it
h_minusOne = h-1
w_MinusOne = w-1
for ylp=1 to h_MinusOne
Ylp_MinusOne = ylp-1
Ylp_PlusOne = ylp+1
for xlp=1 to w_MinusOne
// Read all the cells around this point
Total#=SrcArray#(xlp ,ylp_MinusOne)
Total#+=SrcArray#(xlp ,ylp)
Total#+=SrcArray#(xlp ,ylp_PLusOne)
sx=xlp-1
Total#+=SrcArray#(sx ,ylp_MinusOne)
Total#+=SrcArray#(sx ,ylp)
Total#+=SrcArray#(sx ,ylp_PLusOne)
sx=xlp+1
Total#+=SrcArray#(sx ,ylp_MinusOne)
Total#+=SrcArray#(sx ,ylp)
Total#+=SrcArray#(sx ,ylp_PLusOne)
// drop the result into the output array
DestArray#(Xlp,ylp)=Total#/9
next
next
// Do Edges...
for ylp=0 to h
Ylp_MinusOne = wrapvalue(ylp-1,0,h)
Ylp_PlusOne = wrapvalue(ylp+1,0,h)
// Check if we'\re doing the first or last line ?
// if so, we do all cells on this row, otherwise only the first and last
Xstep = W
if Ylp=0 or Ylp=h then Xstep =1
for xlp=0 to w step Xstep
// Read all the cells around this point
Total#=0
For Sx = xlp-1 to xlp+1
wx=wrapvalue( sx,0,w)
Total#+=SrcArray#(wx ,ylp_MinusOne)
Total#+=SrcArray#(wx ,ylp)
Total#+=SrcArray#(wx ,ylp_PLusOne)
next
// drop the result into the output array
DestArray#(Xlp,ylp)=Total#/9
next
next
EndFunction
// --------------------------------------------------------------------------------------
// --------------------------------------------------------------------------------------
// --------------------->> AVERAGE ARRAY V0004 (Two Passes Unrolled) <<---------------------------------------
// --------------------------------------------------------------------------------------
// --------------------------------------------------------------------------------------
Function AverageArray_V0005(SrcArray#(),DestArray#())
GridSize=4
// Here we'll assume the SRC and DEST are the sa me size.. to save some time
w=getarrayelements(SrcArray#(),1)
h=getarrayelements(SrcArray#(),2)
Dim RowPrevious#(w)
Dim RowCurrent#(w)
Dim RowNext#(w)
// grab the previous row
AverageArray_V0005_TallyRow(SrcArray#(), h, RowPrevious#(),w )
// Grad the current row
AverageArray_V0005_TallyRow(SrcArray#(), 0, RowCurrent#(),w )
for ylp=0 to h
// Grab the next row
NextY=WrapValue(ylp+1,0,H)
AverageArray_V0005_TallyRow(SrcArray#(), NextY, RowNext#(),w )
// Add them together
for xlp=0 to w
Tally#=RowPrevious#(xlp)+RowCurrent#(xlp)+RowNext#(xlp)
DestArray#(xlp,ylp) = Tally#/9
next
// Row out the old data
swaparray RowPrevious#(),RowCurrent#()
swaparray RowPrevious#(),RowNext#()
next
EndFunction
Psub AverageArray_V0005_TallyRow(SrcArray#(), SrcY, DestRow#(),w )
// NOTE: here's assuming the SrcArray#() is as least 2 cells wide
// Compute the first cell
Total#=SrcArray#( w ,SrcY)
Total#+=SrcArray#(0 ,SrcY)
Total#+=SrcArray#(1 ,SrcY)
DestRow#(0)=Total#
// Do the middle cells, without wrapping
for xlp=1 to w-1
// Read all the cells around this point
Total# =SrcArray#( xlp-1 ,SrcY)
Total#+=SrcArray#(xlp ,SrcY)
Total#+=SrcArray#(xlp+1 ,SrcY)
// remember the tally at this point
DestRow#(xlp)=Total#
next
// Compute the last cell in the row
Total# =SrcArray#( w-1 ,SrcY)
Total#+=SrcArray#(w ,SrcY)
Total#+=SrcArray#(0 ,SrcY)
DestRow#(w)=Total#
EndPsub
// --------------------------------------------------------------------------------------
// --------------------------------------------------------------------------------------
// --------------------->> DRAW ARRAY AS TILES <<---------------------------------------
// --------------------------------------------------------------------------------------
// --------------------------------------------------------------------------------------
Function DrawArray(ThisArray#())
GridSize=4
Sw=GetScreenWidth()
w=getarrayelements(ThisArray#(),1)
h=getarrayelements(ThisArray#(),2)
CellsAcross= sw/GridSize
CellsAcross+=((CellsAcross*GridSize)<Sw)
lockbuffer
for ylp=0 to h
Xpos=0
Ypos2=Ypos+GridSize
for xlp=0 to CellsAcross
Col=cliprange#( ThisArray#(xlp,ylp),0,255)
BoxC Xpos,Ypos,Xpos+GridSize,Ypos2,true, rgb(Col,Col,col)
Xpos+=GridSize
next
Ypos+=GridSize
if Ypos=>GetScreenHeight()
exit
endif
next
unlockbuffer
EndFunction
Function RandomizeArray(ThisArray#())
w=getarrayelements(ThisArray#(),1)
h=getarrayelements(ThisArray#(),2)
for ylp=0 to h
for xlp=0 to w
ThisArray#(xlp,ylp)=rnd#(255)
next
next
EndFunction
[/pbcode]
PlayBASIC Live: Array Filtering optimization Ideas (2017-08-09) Related Optimization Links: - A Crash Course In BASIC program Optimization (http://www.underwaredesign.com/forums/index.php?topic=2548.0)
- Global / Local Animation (http://www.underwaredesign.com/forums/index.php?topic=3604.0)
- Optimzation Ideas - Manually Finding The Closest Object (http://www.underwaredesign.com/forums/index.php?topic=3221.0)
- PlayBasic Optimization Tutorial - Cross fade Methods (http://www.underwaredesign.com/forums/index.php?topic=2890.0)
- Kaleidoscope (optimized) (http://www.underwaredesign.com/forums/index.php?topic=4111.0)
- Scan / filter 2d Array (http://www.underwaredesign.com/forums/index.php?topic=4134.0)