Array Wrapping / Filtering / Sampling Speed Ideas

[kevin]

      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.  

PlayBASIC Code: [Select]

/*
 *=-----------------------------------------------------------------------------=*
               >>   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) <<---------------------------------------

Login required to view complete source code

Related Optimization Links:

    - A Crash Course In BASIC program Optimization
    - Global / Local Animation
    - Optimzation Ideas - Manually Finding The Closest Object
     - PlayBasic Optimization Tutorial  - Cross fade Methods
     - Kaleidoscope (optimized)

[kevin]

  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

PlayBASIC Code: [Select]

/*
 *=-----------------------------------------------------------------------------=*
               >>   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   

Login required to view complete source code

PlayBASIC Live: Array Filtering optimization Ideas (2017-08-09)

 

Related Optimization Links:

    - A Crash Course In BASIC program Optimization
    - Global / Local Animation
    - Optimzation Ideas - Manually Finding The Closest Object
    - PlayBasic Optimization Tutorial  - Cross fade Methods
    - Kaleidoscope (optimized)
     - Scan / filter 2d Array