Défi: optimisation d'une fonction de convertion (Bin = Dec)

Question

Salut!


J'ai besoin dans un programme d'avoir une fonction qui me converti en nombre entier une chaine de caract&#232;res repr&#233;sentative d'un nombre binaire strictement positif compris entre 0 et 511 ex: "100110100" (codage sur 9 bits).


Cette fonction doit &#234;tre appel&#233;e environ 9 000 000 de fois &#224; la suite. Il me faut donc qu'elle soit le plus rapide possible. Je poste la fonction que je me suis programm&#233; mais que je voudrais optimiser. 
Si vous avez des id&#233;e pour augmenter la rapidit&#233; du code je vous serai reconnaissant.
Merci! 


Lo&#239;c






Private Function BinToNum(sBinary As String) As Long
   Dim nValue As Long
   Dim nCpt As Long
   Dim nPow As Byte
   
   nValue = 0
   nCpt = 1
   While nCpt <= Len(sBinary)
       If Mid(sBinary, nCpt, 1) = "1" Then
          nPow = Len(sBinary) - nCpt
          nValue = nValue + (2 ^ nPow)
       End If
       nCpt = nCpt + 1
   Wend
   
   BinToNum = nValue
End Function

K@zuya · Answer

Salut, j'ai d&#233;j&#224; eut exactement le m&#234;me genre de PB et j'ai trouv&#233; une solution pas mal du tout, on ne peut pas faire plus rapide, c'est imposible.

il te faut ecrire une fonction dans ce go&#251;t la:

Private Function BinToNum(sBinary As String) As Long
Select Case sBinary
          Case "000000000"
                    BinToNum = 0
          Case "000000001"
                    BinToNum = 1
          Case "000000010"
                    BinToNum = 2
          Case "000000011"
                    BinToNum = 3

etc.....
End Select
End Function

Oui mais tu va m'dire, hein, fo &#233;crire tout &#231;a, c'est trop long !!!
C'est pourquoi moi, j'ai d'abord &#233;crit un petit programme qui m'&#233;crit la fonction toute faite dans un fichier puis je fais un copier/coller, c'est pas plus compliqu&#233; que &#231;a.

K@zuya

Zigarn · Answer

Et si tu utilisait le m&#234;me algo que pour convertir une chaine repr&#233;sentant un d&#233;cimal en un entier :

tu lis tes caract&#232;res depuis la gauche et &#224; chaque caract&#232;re tu multiplie par 2 et tu ajoute la valeur du caract&#232;re :


Private Function BinToNum(sBinary As String) As Long
   Dim nValue As Long
   Dim nCpt As Long


   Dim  nMax As Long


   

   nMax =
 Len(sBinary)


   nValue = 0
   nCpt = 1
   While nCpt <= nMax

       nValue = 2*nValue
       If Mid(sBinary, nCpt, 1) = "1" Then
          nValue = nValue + 1
       End If
       nCpt = nCpt + 1
   Wend
   
   BinToNum = nValue
End Function



C'est plus "algorithmique" come solution et tu n'utilise pas de calcul de puissance donc plus rapide que ta solution

-------------------------------------------------
D&#233;butant ... mais pas pour longtemps !

Zigarn · Answer

En fait cela utilise le fait que 100110b = ((((1*2+0)*2+0)*2+1)*2+1)*2+0

tout comme 123 = (1*10+2)*10+3

-------------------------------------------------
D&#233;butant ... mais pas pour longtemps !

lcprog · Answer

la solution de  Kazuya me plait bien. je testerai ce soir...
Sinon un gars sur hardware.fr m'a beaucoup aid&#233;. Voici o&#249; on a abouti (presque 50% de gain de temps).

 private nPowerArray(1 to 9) as long 
 
Private Function Bin9BitsToNum(sBinary As String) As Long 
   Dim nValue As Long 
   Dim nCpt As Long 
    
   nValue = 0 
   nCpt = 9 
 
   While nCpt > 0 
       If AscW(Mid$(sBinary, nCpt, 1)) = 49 Then 
          nValue = nValue + nPowerArray(nCpt) 
       End If 
       nCpt = nCpt - 1 
   Wend 
    
   Bin9BitsToNum = nValue 
End Function 
 
 
Private Sub Class_Initialize() 
   nLevel = 1 
   nPowerArray(1) = 256 
   nPowerArray(2) = 128 
   nPowerArray(3) = 64 
   nPowerArray(4) = 32 
   nPowerArray(5) = 16 
   nPowerArray(6) = 8 
   nPowerArray(7) = 4 
   nPowerArray(8) = 2 
   nPowerArray(9) = 1 
End Sub

JoePatent · Answer

"Salut, j'ai d&#233;j&#224; eut exactement le m&#234;me genre de PB et j'ai trouv&#233; une solution pas mal du tout, on ne peut pas faire plus rapide, c'est imposible."

Cette solution n'est pas la plus rapide.  Chaque 'case' sera verifier dans le cas de 511 par exemple.

Tant qu'a proc&#233;der ainsi, fait 9 if ind&#233;pendant pour tester chaque BIT un a un.  Plus rapide, plus simple, plus court, plus stable.  Toujours et uniquement 9 conditions. Aucune boucle, aucune inc&#233;mentation de variable etc etc.

*****
LCPROG ->  tu semble hardcod&#233; le nombre de bit a 9 si je me fie au vecteur. Donc...
Private Function Bin9BitsToNum(sBinary As String) As Integer
   Dim nValue As Integer ' Prit la libert&#233; de r&#233;duire la taille des variable
   Dim nCpt As Integer  ' Prit la libert&#233; de r&#233;duire la taille des variable

 
   nValue = val(right&(sBinary, 1) ' Tant qu'a initialiser aussi bien couper une it&#233;ration
 
   for nCpt = 8 to 1 step -1 ' Pas convaincu que cette boucle est plus performante
       nValue = nValue + (nPowerArray(nCpt) * val(mid$(sBinary, nCpt, 1)))
   next j
    
   Bin9BitsToNum = nValue 
End Function 
 
Private Sub Class_Initialize() 
   nLevel = 1 ' ???
   nPowerArray(1) = 256 
   nPowerArray(2) = 128 
   nPowerArray(3) = 64 
   nPowerArray(4) = 32 
   nPowerArray(5) = 16 
   nPowerArray(6) = 8 
   nPowerArray(7) = 4 
   nPowerArray(8) = 2 
   nPowerArray(9) = 1 
End Sub 

http://www.joepatent.com

lcprog · Answer

Voil&#224; o&#249; j'en suis. J'ai pas trouv&#233; plus rapide.

Private Function Bin9BitsToNum(sBinary As String) As Long
   Dim nValue As Long
   
   If AscW(Mid$(sBinary, 1, 1)) = 49 Then
      nValue = nValue + 256
   End If
   If AscW(Mid$(sBinary, 2, 1)) = 49 Then
      nValue = nValue + 128
   End If
   If AscW(Mid$(sBinary, 3, 1)) = 49 Then
      nValue = nValue + 64
   End If
   If AscW(Mid$(sBinary, 4, 1)) = 49 Then
      nValue = nValue + 32
   End If
   If AscW(Mid$(sBinary, 5, 1)) = 49 Then
      nValue = nValue + 16
   End If
   If AscW(Mid$(sBinary, 6, 1)) = 49 Then
      nValue = nValue + 8
   End If
   If AscW(Mid$(sBinary, 7, 1)) = 49 Then
      nValue = nValue + 4
   End If
   If AscW(Mid$(sBinary, 8, 1)) = 49 Then
      nValue = nValue + 2
   End If
   If AscW(Mid$(sBinary, 9, 1)) = 49 Then
      nValue = nValue + 1
   End If
 
   Bin9BitsToNum = nValue
End Function

JoePatent, t'es sur pour l'integer ? J'ai lu qu'il fallait de pr&#233;f&#233;rence utiliser le tupe long en vb pour les processeurs 32 bits.  Faut pas regarder la variable nLevel, c'est une propri&#233;t&#233; utilis&#233;e dans les autres m&#233;thodes de ma classe.

lcprog · Answer

je confirme pour le long. ca me fait gagner 1.5 seconde sur un bench qui dure 43 secondes avec un integer

lcprog · Answer

je confirme pour le long. ca me fait gagner 1.5 seconde sur un bench qui dure 43 secondes avec un integer

Gobillot · Answer

l'acc&#232;s direct est toujours le plus rapide, bien s&#251;r &#231;a prend &#233;norm&#233;ment de place mais ensuite les temps sont negligeables.

   Dim s  As String
    Dim i  As Integer
    Dim T() As Integer

    ReDim T(111111111)
    For i = 0 To 511
        s = Byte2String(i)
        T(Val(s)) = i
        Next

Private Function Byte2String(n As Integer) As String
    Dim x As Integer
    Dim R As String
    x = 256
    Do      If (n And x) Then R R + "1" Else R R + "0"
      x = x \ 2
      Loop Until x = 0
    Byte2String = R
    End Function

'pour l'utilsation acc&#232;s directe dans la Table
     Bin9BitsToNum = T(Val(sBinary))

Daniel

JoePatent · Answer

Tr&#232;s imaginatif !

J'ai test&#233; et toutes les autres m&#233;thodes varient entre 29 secondes et 78 secondes (essai &#233;chou&#233; avec VAL() et autres functions)

Ta fonction prend 10 secondes.  Gourmande en memoire mais tres rapide !  :-)

*9 millions d'op&#233;rations.

http://www.joepatent.com

JoePatent · Answer

Voici une autre possibilit&#233; :
L'astuce est d'&#233;liminer les manipulations de cha&#238;ne de caract&#232;re.  Seul le VAL() demeure et est tres tres gourmand.

J'obtiens 20 secondes au lieu de 29.  Toutefois, si je recois un long au lieu d'ue string je descend a 10 secondes.  Mais on a pas le choix j'imagine de recevoir une string :-(

Voici : 
Private Function DBin9BitsToNum(sbinary As String) As Integer
Dim z As Long
   Dim nValue As Integer
 z = Val(sbinary)
      nValue = nValue + (1 * (z Mod 2))
 z = z \ 10
      nValue = nValue + (2 * (z Mod 2))
 z = z \ 10
      nValue = nValue + (4 * (z Mod 2))
 z = z \ 10
      nValue = nValue + (8 * (z Mod 2))
 z = z \ 10
      nValue = nValue + (16 * (z Mod 2))
 z = z \ 10
      nValue = nValue + (32 * (z Mod 2))
 z = z \ 10
      nValue = nValue + (64 * (z Mod 2))
 z = z \ 10
      nValue = nValue + (128 * (z Mod 2))
 z = z \ 10
      nValue = nValue + (256 * (z Mod 2))
 
 
   DBin9BitsToNum = nValue
End Function

http://www.joepatent.com

Défi: optimisation d'une fonction de convertion (Bin => Dec)

11 réponses

Discussions similaires