PureBasic

Bonjour,
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

Dans ton cas, tu n'as aucune variable à initialiser à donc le recursif parait plus optimisé (surtout que ton non-recursif fait des Add/DeleteElement()..)

Donc, quand on veut faire du récursif en PB, un conseil d'optimisation consiste à réduire au maximum les variables "Protected" et à préférer des "Global", c'est ça?
Merci de la réponse

; ça va me permettre de booster un peu certains de mes traitements.

Bonjour

J'obtiens une erreur ici:

Code : Tout sélectionner

While(ListSize(cell()) > 0)

Message erreur: ListSize() is not a fonction, array, macro etc...

??

; je ne crois pas que c'est ce que voulait dire Fred

il te dit que ton mode procedure normal (non-recursif)
est plus lent parceque tu utilises une liste chainée !!

pour ajouter un element dans une liste en interne il faut qu'il y ai un parcours de la liste ..
plus il y a d'elements dans une liste plus ça prends du temp d'ajouter un element ...(du moins je crois)

dans ta version Recursif , tu n'utilises pas de liste chainée ... donc ça semble plus rapide

car poser le context de l'appel sur la pile, est plus rapide que de poser une valeur dans la liste chainée..

du point de vue théorique , l'appel reccursif sera toujours plus lent qu'un traitement Standard ..
a cause du depot du context sur la pile , et du depillage en fin de procedure

tout comme l'utilisation d'une procedure sera toujours plus lent qu'un appel a un sou prg ( label: ----- Return )
plus tu fais effectuer de traitements plus c'est lent .. l'utilisation d'une liste sera plus lent que l'utilisation d'une variable structuré
l'utilisation d'une variable structuré sera plus lent que l'utilisation d'une variable standard ... etc ...

précalculer sera plus rapide que de faire effectuer les calculs ...
bref , des exemples comme ça on peut en trouver plein

l'utilisation de variable global dans le context d'appel recursif , n'a pas de sens , et va meme a l'encontre du principe

kelebrindae a écrit :Donc, quand on veut faire du récursif en PB, un conseil d'optimisation consiste à réduire au maximum les variables "Protected" et à préférer des "Global", c'est ça?
Merci de la réponse ; ça va me permettre de booster un peu certains de mes traitements.

De plus l'initialisation des variables locales est souvent négligeable comparé au reste de la procédure, donc ca ne devrait pas etre une facteur de préoccupation. Il vaut mieux se pencher sur l'optimisation de l'algo

Merci pour l'explication de texte; j'avais effectivement compris de travers...

Dobro a écrit :pour ajouter un element dans une liste en interne il faut qu'il y ai un parcours de la liste ..
plus il y a d'elements dans une liste plus ça prends du temp d'ajouter un element ...(du moins je crois)

L'ajout/insertion d'un élément dans une liste chainée se fait en O(1) càd en temps constant quelque soit le nombre d'éléments de la liste. (on peut chipoter en considérant la mémoire cache, mais bon, en moyenne...)

PureBasic

Remplissage: récursif vs. procédural

Remplissage: récursif vs. procédural

Re: Remplissage: récursif vs. procédural

Re: Remplissage: récursif vs. procédural

Re: Remplissage: récursif vs. procédural

Re: Remplissage: récursif vs. procédural

Re: Remplissage: récursif vs. procédural

Re: Remplissage: récursif vs. procédural

Re: Remplissage: récursif vs. procédural