Optimize script for speed

[ofLight]

Hello All,

I am trying to increase the speed of the _PixelFindAll function within my script, I believe the major slowdown is occurring because of the For-Next loop comparing each pixel with every other pixel. If anyone has any recommendations on how i can rewrite this to be faster, or even completely change it and still get the desired results I would greatly apreaciate the info.

expandcollapse popup

#include <Array.au3>
#include <Misc.au3>
#include <GUIConstants.au3>


$SearchArea = _DrawRect_Drag("01") ;Define Search area "01"=Left mouse Click
$Array01 = _PixelFindAll(38911,0,0,0,$SearchArea[0],$SearchArea[1],$SearchArea[2],$SearchArea[3]) ;Find all instances of the defined color within
_ArrayDisplay($Array01) ;Display results

;=================================   PixelFindAll   ==============================
; Function Name:    _PixelFindAll
; Description:      Finds all instances of a pixel within a given area and returns array with Total and all locations X and Y.
;                   Allows you to limit results by skiping pixels within a given distance to each other.
; Requires:                         None
; Parameters:       $Pixel          Colour value of pixel to find (in decimal or hex).
;                   $XDist          Horizontal distance from found pixel to skip before continueing search (moving right)
;                   $YDist          Vertical distance from found pixel to skip before continueing search (moving down)
;                   $sv             Shade Varience
;                   $SB_l           left coordinate of total area to search. Default is 0 (far left side of screen)
;                   $SB_t           top coordinate of total area to search. Default is 0 (top most Side of screen)
;                   $SB_r           Right coordinate of total area to search. Default is @DesktopWidth (Far Right side of screen)
;                   $SB_b           Bottom coordinate of total area to search. Default is @DesktopHeight (Bottom most side of screen)
; Syntax:         _PixelFindAll($pixel[, $XDist, $YDist, $sv, $SB_l, $SB_t, $SB_r, $SB_b])
; Author(s):    
; Returns:      $Array[0][0] = 0 on failure
;===============================================================================
Func _PixelFindAll($pixel,$XDist=0,$YDist=0,$sv=0,$SB_l=0,$SB_t=0,$SB_r=@DesktopWidth,$SB_b=@DesktopHeight)
    Dim $Array[2][2], $Count = "0", $SB_l_Max = $SB_l, $SB_b_Max = $SB_b
    $Array[0][0] = "0"

    While 1
        $xy = PixelSearch($SB_l,$SB_t,$SB_r,$SB_b,$pixel,$sv)
        If @error And $SB_b = $SB_b_Max Then
            SetError(1)
            
            Dim $Array2[2][2]
            $Array2[0][0] = "0"
            $Count = "0"

            For $i = 1 to $Array[0][0]
                $Write = 1              
                For $j = $i+1 to $Array[0][0]
                    $VarX = _CompareNumbers($Array[$i][0], $Array[$j][0], $XDist)
                    If $VarX = 0 Then
                        $VarY = _CompareNumbers($Array[$i][1], $Array[$j][1], $YDist)
                        If $VarY = 0 Then $Write = 0
                    EndIf
                Next
                If $Write = 1 Then
                    $Count = $Count+1
                    $Array2[0][0] = $Count
                    ReDim $Array2[$Count+1][2]
                        $Array2[$Count][0] = $Array[$i][0]
                        $Array2[$Count][1] = $Array[$i][1]              
                EndIf
            Next

            Return $Array2
        ElseIf @error Then
            $SB_t = $SB_b + 1
            $SB_b = $SB_b_Max
            $SB_l = $SB_l_Max
        Else
            $Count = $Count+1
            $Array[0][0] = $Count
            ReDim $Array[$Count+1][2]
            $Array[$Count][0] = $xy[0]
            $Array[$Count][1] = $xy[1]

            $SB_t = $xy[1]
            $SB_b = $SB_t
            $SB_l = $xy[0]+1+$YDist 
        EndIf
    WEnd
EndFunc;==========================  PixelFindAll   ===============================

Func _CompareNumbers($Number1, $Number2, $byhowmuch);SUB Function of PixelFindAll
    ;Verify that $Number1 is more than $byhowmuch from $Number2
    ;Returns 0 if within $byhowmuch
    If $Number1 = $Number2 Then
        Return 0
    ElseIf $Number1 > $Number2 Then
        If ($Number1-$byhowmuch) >= $Number2 Then Return 1
    ElseIf $Number1 < $Number2 Then
        If ($Number1+$byhowmuch) <= $Number2 Then Return 1
    EndIf
    Return 0
EndFunc

;=================================   _DrawRect_Drag   ============================
; Function Name:    _DrawRect_Drag
; Requires:         <GUIConstants.au3> & <Misc.au3>
; Description:      Gives a visual aid while defineing Top\Left|bottom\Right of a given area
; Parameters:       $ActionKey      Hex code for key to press to begin and end render
;                   $color          Color of the display box
; Syntax:            _DrawRect_Drag([$ActionKey][,$color])
; Author(s):        
; Returns:          $array[4]      $array[0] = Left, $array[1] = Top, $array[2] = Right, $array[3] = Bottom
;===============================================================================
Func _DrawRect_Drag($ActionKey = "2D", $color = 0xFF0000)

    Do
        $pos = MouseGetPos()
        Sleep(25)
    Until _IsPressed($ActionKey)
    
    Local $ScanWidth = 1, $ScanHeight = 1
    Local $positions[4]
    $positions[0] = $pos[0] ;LEFT
    $positions[1] = $pos[1] ;TOP
    $x = $pos[0]
    $y = $pos[1]
    
    $GUI_DR = GUICreate("", 0, 0, $x, $y, $WS_POPUP)
    WinSetTrans($GUI_DR,"",210)
    $Top_DR = GUICreate("Top Line", $ScanWidth, 2, $x, $y, $WS_POPUP, -1, $GUI_DR)
    GUISetBkColor($color)
    WinSetTrans($Top_DR,"",210)
    GUISetState()
    $Left_DR = GUICreate("Left Line", 2, $ScanHeight, $x, $y, $WS_POPUP, -1, $GUI_DR)
    GUISetBkColor($color)
    WinSetTrans($Left_DR,"",210)
    GUISetState()
    $Right_DR = GUICreate("Right Line", 2, $ScanHeight, $x + $ScanWidth - 2, $y, $WS_POPUP, -1, $GUI_DR)
    GUISetBkColor($color)
    WinSetTrans($Right_DR,"",210)
    GUISetState()
    $Bottom_DR = GUICreate("Bottom Line", $ScanWidth, 2, $x, $y + $ScanHeight, $WS_POPUP, -1, $GUI_DR)
    GUISetBkColor($color)
    WinSetTrans($Bottom_DR,"",210)
    GUISetState()
    Sleep(800)
    
    Do
        $MousePos = MouseGetPos()
        WinMove($Top_DR, "", $x, $y, $ScanWidth, 2)
        WinMove($Left_DR, "", $x, $y, 2, $ScanHeight) 
        WinMove($Right_DR, "", $x + $ScanWidth - 2, $y, 2, $ScanHeight)  
        WinMove($Bottom_DR, "", $x, $y + $ScanHeight, $ScanWidth, 2)
        If Not (($MousePos[0] - $x) <= 0) Then
            $ScanWidth = $MousePos[0] - $x + 1
        EndIf
        If Not (($MousePos[1] - $y) <= 0) Then
            $ScanHeight = $MousePos[1] - $y - 1
        EndIf
    Until _IsPressed($ActionKey)
    
    $positions[2] = $MousePos[0] ;RIGHT
    $positions[3] = $MousePos[1] ;BOTTOM
    
    GUISetState(@SW_HIDE,$GUI_DR)
    GUISetState(@SW_HIDE,$Top_DR)
    GUISetState(@SW_HIDE,$Left_DR)
    GUISetState(@SW_HIDE,$Right_DR)
    GUISetState(@SW_HIDE,$Bottom_DR)

    Return $positions
EndFunc;==========================   _DrawRect_Drag   ============================

[Zedna]

1)

replace

If $VarY = 0 Then $Write = 0

by

If $VarY = 0 Then 
  $Write = 0
  ExitLoop
EnDIf

2)

code from function _CompareNumbers() write directly infor your FOR NEXT loops

to avoid function call overhead

EDIT: these are only minor speed optimizations

Edited April 1, 2008 by Zedna

[Siao]

Instead of "$Count = $Count+1" use "$Count += 1" and stuff like that.

But more importantly,

Don't do this: ReDim $Array[$Count+1][2]

ReDim'ing takes progressively more time as your array grows.

Instead, in the beginning, declare the array large enough to fit all possible matches:

Dim $Array[($SB_r-$SB_l+1)*($SB_b-$SB_t+1)+1][2]

and forget about it.

Likewise, don't do: ReDim $Array2[$Count+1][2]

Dim it large enough to fit all possible matches ( $Array2[ $Array[0][0]+1 ][2] ), and then ReDim it one time in the end to shrink it if necessary.

Edited April 1, 2008 by Siao

[ofLight]

Thanks for the response Zedna,

I didnt even know function call overhead existed. I learn something new every day .

I only had it like that because it made the code easier for me to follow, but i would much rather have the little bit of time it saves me. Although it may be very little time that is in actuality saved, i call this function continually, so the time however small will add up.

[Siao]

Although I don't understand the logic of that final rechecking block inside "If @error And $SB_b = $SB_b_Max Then" at all...

If you want to skip pixels, do it with PixelSearch in the main loop and save yourself alot of time.

Edited April 1, 2008 by Siao

[ofLight]

Siao, not re dimming actually sounds like it might save a significant amount of time, very good idea thank you.

The only question i have is, can you foresee any issues with defining an array 1.8 million in size? would not any potential speed increase gained by not re dimming be lost if an array was needed of that size?

[Zedna]

Siao, not re dimming actually sounds like it might save a significant amount of time, very good idea thank you.

The only question i have is, can you foresee any issues with defining an array 1.8 million in size? would not any potential speed increase gained by not re dimming be lost if an array was needed of that size?

Just make some testing scripts based on these ideas and log out time differences into file.

[ofLight]

Although I don't understand the logic of that final rechecking block inside "If @error And $SB_b = $SB_b_Max Then" at all...

If you want to skip pixels, do it with PixelSearch in the main loop and save yourself alot of time.

That is actually something i couldn't figure out how to do and increase the speed.

The problem I ran into when trying to compare the pixels as they are found is, I would end up doing the comparison for each new pixel found, and it would run exponentially slower, as it adds each new pixel to the array it would increase the size of the number its comparing against. you cant just compare against the Last pixel found, you have to compare against all previous pixels. Any ideas on how to do this part will help greatly... .. .I am probably just not seeing the way you mean.

[Siao]

The only question i have is, can you foresee any issues with defining an array 1.8 million in size? would not any potential speed increase gained by not re dimming be lost if an array was needed of that size?

The issues are

hitting AutoIt array size limit, which is not realistic in this case, but you can always check for that;

and some extra memory is needed to keep that array preallocated (I guess it's 4 bytes per element, as empty 2D array for 2048x1536 screen takes ~24 mb of RAM for me, but such amount is not a big issue nowadays), but that's probably #1 trade-off when optimizing for speed in general anyways.

Edited April 1, 2008 by Siao