voici un post pour les optimiseurs fous
...Il me semble me rappeler avoir lu (il y a longtemps) que PB n'était pas très rapide pour les appels récursifs, à cause de l'initialisation de l'espace mémoire et des variables à chaque appel de la procédure.
Est-ce que c'est toujours vrai ?
Parce que je veux coder une procédure de remplissage (floodfill) pour remplir un petit tableau avec une valeur donnée, un peu comme un remplissage de formes sous Paint, mais en dehors de tout contexte graphique.
Bref: pour comparer récursif et non-récursif, j'ai développé (à l'arrache) les deux méthodes et il se trouve que le récursif est deux fois plus rapide que le procédural.
Je pense que c'est dû au fait que ma procédure non-récursive est mal codée.
Mais est-ce que ça vaut le coup de l'optimiser? Est-ce le gain (en rapidité) sera vraiment conséquent, ou bien est-ce que PB s'est amélioré sur les appels récursifs et que la différence ne sera pas significative ?
Testez ceci (en désactivant le débugger, sinon ça prend des plombes), et donnez-moi votre avis:
Code : Tout sélectionner
Global Dim w.i(12,12)
#BLANK = 0
#FILL = 1
#WALL = 2
Structure cell_struct
x.i
y.i
EndStructure
Global NewList cell.cell_struct()
; Read the datas to create an empty array
Procedure initArray()
Protected x.i,y.i
Protected line.s, char.s
Restore arrayDatas
For y = 0 To 11
Read.s line
For x = 0 To 11
char = Mid(line,x+1,1)
If char = "X"
w(x,y) = #WALL
ElseIf char = " "
w(x,y) = #BLANK
EndIf
Next x
Next y
EndProcedure
; Display the array in the console
Procedure displayArray()
Protected x.i,y.i
Protected disp.s
For y = 0 To 11
For x = 0 To 11
If w(x,y) = #WALL
ConsoleColor(7,3)
ElseIf w(x,y) = #FILL
ConsoleColor(7,12)
Else
ConsoleColor(7,0)
EndIf
Print(" ")
Next x
PrintN("")
Next y
ConsoleColor(7,0)
PrintN("")
EndProcedure
;-
; -------------------------------------------
;- ---------- Recursive flood fill -----------
; -------------------------------------------
Macro RECURSIVE_FILL_CELL(xCell,yCell,blankVal,fillVal)
If w(xCell,yCell) = blankVal
recursiveFill(xCell,yCell,blankVal,fillVal)
EndIf
EndMacro
Procedure recursiveFill(x.i,y.i, blankVal.i, fillVal.i)
w(x,y) = fillVal
RECURSIVE_FILL_CELL(x,y-1,blankVal,fillVal)
RECURSIVE_FILL_CELL(x-1,y-1,blankVal,fillVal)
RECURSIVE_FILL_CELL(x-1,y,blankVal,fillVal)
RECURSIVE_FILL_CELL(x-1,y+1,blankVal,fillVal)
RECURSIVE_FILL_CELL(x,y+1,blankVal,fillVal)
RECURSIVE_FILL_CELL(x+1,y+1,blankVal,fillVal)
RECURSIVE_FILL_CELL(x+1,y,blankVal,fillVal)
RECURSIVE_FILL_CELL(x+1,y-1,blankVal,fillVal)
EndProcedure
;-
; -------------------------------------------
;- ---------- Procedural flood fill ----------
; -------------------------------------------
Macro NON_RECURSIVE_FILL_CELL(xCell,yCell,blankVal,fillVal)
If w(xCell,yCell) = blankVal
AddElement(cell())
cell()\x = xCell
cell()\y = yCell
w(cell()\x,cell()\y) = fillVal
EndIf
EndMacro
Procedure nonRecursiveFill(x.i,y.i, blankVal.i, fillVal.i)
ClearList(cell())
NON_RECURSIVE_FILL_CELL(x,y,blankVal,fillVal)
While(ListSize(cell()) > 0)
ForEach cell()
x = cell()\x
y = cell()\y
DeleteElement(cell())
NON_RECURSIVE_FILL_CELL(x,y-1,blankVal,fillVal)
NON_RECURSIVE_FILL_CELL(x-1,y-1,blankVal,fillVal)
NON_RECURSIVE_FILL_CELL(x-1,y,blankVal,fillVal)
NON_RECURSIVE_FILL_CELL(x-1,y+1,blankVal,fillVal)
NON_RECURSIVE_FILL_CELL(x,y+1,blankVal,fillVal)
NON_RECURSIVE_FILL_CELL(x+1,y+1,blankVal,fillVal)
NON_RECURSIVE_FILL_CELL(x+1,y,blankVal,fillVal)
NON_RECURSIVE_FILL_CELL(x+1,y-1,blankVal,fillVal)
Next cell()
Wend
EndProcedure
; Gain = 15%
Procedure nonRecursiveFill2(x.i,y.i, blankVal.i, fillVal.i)
Protected x2.i
ClearList(cell())
NON_RECURSIVE_FILL_CELL(x,y,blankVal,fillVal)
While(ListSize(cell()) > 0)
ForEach cell()
x = cell()\x
y = cell()\y
DeleteElement(cell())
NON_RECURSIVE_FILL_CELL(x,y-1,blankVal,fillVal)
NON_RECURSIVE_FILL_CELL(x,y+1,blankVal,fillVal)
NON_RECURSIVE_FILL_CELL(x-1,y-1,blankVal,fillVal)
NON_RECURSIVE_FILL_CELL(x-1,y+1,blankVal,fillVal)
NON_RECURSIVE_FILL_CELL(x+1,y-1,blankVal,fillVal)
NON_RECURSIVE_FILL_CELL(x+1,y+1,blankVal,fillVal)
x2 = x+1
While w(x2,y) = blankVal
w(x2,y) = fillVal
NON_RECURSIVE_FILL_CELL(x2+1,y-1,blankVal,fillVal)
NON_RECURSIVE_FILL_CELL(x2+1,y+1,blankVal,fillVal)
x2+1
Wend
x2 = x-1
While w(x2,y) = blankVal
w(x2,y) = fillVal
NON_RECURSIVE_FILL_CELL(x2-1,y-1,blankVal,fillVal)
NON_RECURSIVE_FILL_CELL(x2-1,y+1,blankVal,fillVal)
x2-1
Wend
Next cell()
Wend
EndProcedure
;-
;- *** Main program ***
OpenConsole()
initArray()
PrintN("Empty array:")
displayArray()
PrintN("Recursive Fill:")
recursiveFill(5,5,#BLANK,#FILL)
displayArray()
PrintN("Non Recursive Fill:")
initArray()
nonRecursiveFill2(5,5,#BLANK,#FILL)
displayArray()
#NB_ITER = 100000
; Test 1: Recursive
initArray()
timer.i = ElapsedMilliseconds()
For i = 1 To #NB_ITER
; Fill the array
recursiveFill(5,5,#BLANK,#FILL)
; Empty the array
recursiveFill(5,5,#FILL,#BLANK)
Next i
timer = ElapsedMilliseconds() - timer
; Test 2: Procedural
initArray()
timer2.i = ElapsedMilliseconds()
For i = 1 To #NB_ITER
; Fill the array
nonRecursiveFill(5,5,#BLANK,#FILL)
; Empty the array
nonRecursiveFill(5,5,#FILL,#BLANK)
Next i
timer2 = ElapsedMilliseconds() - timer2
; Test 3: Procedural 2
initArray()
timer3.i = ElapsedMilliseconds()
For i = 1 To #NB_ITER
; Fill the array
nonRecursiveFill2(5,5,#BLANK,#FILL)
; Empty the array
nonRecursiveFill2(5,5,#FILL,#BLANK)
Next i
timer3 = ElapsedMilliseconds() - timer3
MessageRequester("Results", "Recursive : " + Str(timer) + "ms / Procedural : " + Str(timer2) + "ms / Procedural 2 : " + Str(timer3) + "ms")
CloseConsole()
End
DataSection
arrayDatas:
Data.s "XXXXXXXXXXXX"
Data.s "X X"
Data.s "X XX XXX X"
Data.s "X X X X X X"
Data.s "X XXX XXX X"
Data.s "X X"
Data.s "X XXX X"
Data.s "X X X X X"
Data.s "X X X X XXX"
Data.s "X XXX X X X"
Data.s "X X X"
Data.s "XXXXXXXXXXXX"
EndDataSection
; ça va me permettre de booster un peu certains de mes traitements.
; je ne crois pas que c'est ce que voulait dire Fred
