quelques algorithmes pour accélérer les calculs

Post en construction 


J'ouvre cette nouvelle catégorie destinée à discuter programmation bien entendue centrée sur les algorithmes ou programmes utiles aux jeux de loterie .

lorsqu'on programme des calculs axés sur des recherches de combinaisons en très grand nombre , on se rend vite compte , surtout sur le keno, qu'on a 2 limites : les capacités mémoire pour accueillir de grands tableaux et les temps de calcul.

je voudrais vous livrer ici quelques astuces qui permettent de résoudre en partie ces problématiques .

A titre d'exemple , je vais vous présenter une vidéo d'un programme en cours de développement qui accélère par un facteur 100 le calcul des meilleures combinaisons et que j'implémenterai  le moment venu sur  LacNeuroKeno .

lien vidéo

[Vous devez être inscrit et connecté pour voir ce lien]

on verra ici comment utiliser des codages binaires et  des calculs de rang lexicographique peuvent résoudre les problèmes évoqués un peu plus haut .


D'abord , le codage binaire . 
un tirage est composé de 20 numéros parmi 70 . pour que le programme passe partout , je vais rester en 32 bits . comme il y en a 70 à coder , il faut 70 bits , donc on va coder les 20 numéros d'un tirage en 3 entiers de 32 bits . 
Cette subroutine va donc coder  ces 3 entiers dans un tableau B(tirage, 3)  au lieu d'un tableau B(tirage,20) comme auparavant . on voit ainsi le gain d'espace mémoire , mais ce n'est pas le principal avantage . En effet le tirage est codé en bits et pour plus tard cela sera intéressant lorsqu'on devra effectuer des calculs sur ces tirages :

' Subroutine pour coder un tirage de 20 numéros parmi 70 en 3 entiers
SUB CodeTirageEnBits(tirageNum AS INTEGER)
    Dim bits1 As Integer, bits2 As Integer, bits3 As Integer
    bits1 = 0
    bits2 = 0
    bits3 = 0
    For numero As Integer = 1 To 20
        Dim n As Integer
        n = A(tirageNum, numero)
        If n <= 32 Then
            bits1 = bits1 Or (1 Shl (n - 1))
        ElseIf n <= 64 Then
            bits2 = bits2 Or (1 Shl (n - 33))
        Else
            bits3 = bits3 Or (1 Shl (n - 65))
        End If
    Next numero
    B(tirageNum, 1) = bits1
    B(tirageNum, 2) = bits2
    B(tirageNum, 3) = bits3
END SUB

ainsi le tirage :
1 3 9 11 13 27 28 29 30 34 35 41 42 47 48 54 62 63 64 67
est codé
1006638341   -534723834     4 

De la même manière on peut coder une combinaison de 10 numéros parmi 70 en binaire :

' Fonction pour coder une combi de nb numéros parmi 70 en 3 entiers
SUB CodecombiEnBits(combiNum AS INTEGER)
    DIM bits1 AS INTEGER, bits2 AS INTEGER, bits3 AS INTEGER

    bits1 = 0
    bits2 = 0
    bits3 = 0
    
    FOR numero AS INTEGER = 1 TO nb
        DIM n AS INTEGER
        n = combi(combiNum, numero)
        IF n <= 32 THEN
            bits1 = bits1 OR (1 SHL (n - 1))
        ELSEIF n <= 64 THEN
            bits2 = bits2 OR (1 SHL (n - 33))
        ELSE
            bits3 = bits3 OR (1 SHL (n - 65))
        END IF
    NEXT numero

    C(combiNum, 1) = bits1
    C(combiNum, 2) = bits2
    C(combiNum, 3) = bits3
    
END SUB

ainsi lorsqu'on souhaitera vérifier si une combinaison est présente parmi les tirages on pourra le faire au moyen d'opérations logique .
Si tous les bits de la combinaison sont exactement présents dans le tirage alors la combinaison est présente et on augmente son compteur de nombre de sorties . Cette comparaison peut être programmée ainsi :

for tirage = 1 to nt
            ' Comparer les 3 entiers de la combinaison avec les 3 entiers du tirage
            if ((C(index_combi, 1) AND B(tirage, 1)) = C(index_combi, 1)) AND _
               ((C(index_combi, 2) AND B(tirage, 2)) = C(index_combi, 2)) AND _
               ((C(index_combi, 3) AND B(tirage, 3)) = C(index_combi, 3)) AND _
               ((B(tirage, 1) AND C(index_combi, 1)) = C(index_combi, 1)) AND _
               ((B(tirage, 2) AND C(index_combi, 2)) = C(index_combi, 2)) AND _
               ((B(tirage, 3) AND C(index_combi, 3)) = C(index_combi, 3)) then

                ' Si tous les bits de la combinaison sont exactement présents dans le tirage
                occurences(index_combi) += 1
            end if
        next tirage



De la même façon , il faut pouvoir revenir d'un tirage ou d'une combinaison codé en binaire vers un tirage ou une combinaison contenant leur numéros propres . Pour cela :

' Extraire les numéros d'un tirage codé
SUB ExtraireCombinaisonsDe20(bits1 As Integer, bits2 As Integer, bits3 As Integer)
    totalNums = 0
    DIM n AS INTEGER
    For n = 1 To 32
        If (bits1 And (1 Shl (n - 1))) Then
            totalNums += 1
            nums(totalNums) = n
        End If
    Next n
    For n = 33 To 64
        If (bits2 And (1 Shl (n - 33))) Then
            totalNums += 1
            nums(totalNums) = n
        End If
    Next n
    For n = 65 To 70
        If (bits3 And (1 Shl (n - 65))) Then
            totalNums += 1
            nums(totalNums) = n
        End If
    Next n
END SUB

ou 

SUB ExtraireCombinaisons(bits1 AS INTEGER, bits2 AS INTEGER, bits3 AS INTEGER)
    
    dim as integer totalNums = 0
    DIM n AS INTEGER

    ' Extraire les numéros communs à partir des bits
    FOR n = 1 TO 32
        IF (bits1 AND (1 SHL (n - 1))) THEN
            totalNums += 1
            nums(totalNums) = n
        END IF
    NEXT n

    FOR n = 33 TO 64
        IF (bits2 AND (1 SHL (n - 33))) THEN
            totalNums += 1
            nums(totalNums) = n
        END IF
    NEXT n

    FOR n = 65 TO 70
        IF (bits3 AND (1 SHL (n - 65))) THEN
            totalNums += 1
            nums(totalNums) = n
        END IF
    NEXT n
end sub


Le Rang Lexicographique :


Le rang lexicographique d'une combinaison représente sa position dans l'ordre d'apparition des combinaisons possibles d'un ensemble donné, lorsque celles-ci sont triées de manière lexicographique (dans l'ordre croissant). Par exemple, si on considère toutes les combinaisons possibles de 5 numéros parmi un ensemble de 10 (1 à 10), chaque combinaison aura un "rang" qui indique sa position dans cet ordre.
1:1 2 3 4 5
2:1 2 3 4 6
3:1 2 3 4 7
.....
252 : 6 7 8 9 10

Le rang lexicographique a plusieurs utilités :

• Stockage compact : Au lieu de stocker chaque combinaison comme un ensemble de numéros, on peut simplement stocker son rang dans une séquence ordonnée. Cela permet de compresser les données et d'économiser de l'espace.
  
• Calcul de performance : Lorsqu'il s'agit de manipuler des ensembles de combinaisons, il est plus facile de travailler avec des indices (rangs) que de parcourir des listes complexes de combinaisons.
  
• Accès rapide : Grâce au rang lexicographique, il est possible de retrouver une combinaison à partir de son rang ou de calculer rapidement le rang d'une combinaison donnée.
  

Pour calculer le rang d'une combinaison, on utilise une formule qui repose sur le principe des combinaisons sans répétition. Voici comment cela fonctionne :

Soit une combinaison donnée de k éléments choisis parmi v  (par exemple, 5 numéros parmi 70).

Le rang est calculé en additionnant le nombre de combinaisons qui précèdent la combinaison donnée. Cela revient à compter toutes les combinaisons possibles qui commencent par un numéro inférieur à celui dans la combinaison donnée.

fonction pour calculer correctement le rang d'une combinaison
Function CalculerRangCorrect(combi() As Integer, v As Integer, k As Integer) As ULongInt
    Dim rg As ULongInt = 0
    For i As Integer = 1 To k
        For j As Integer = combi(i - 1) + 1 To combi(i) - 1
            rg += CLngInt(combine(v - j, k - i))
        Next j
    Next i
    CalculerRangCorrect = rg
End Function

combi() : Représente la combinaison pour laquelle on souhaite calculer le rang.
v   : Représente le nombre total d'éléments dans l'ensemble.
k   : Le nombre d'éléments dans la combinaison.

Le rang est calculé en additionnant le nombre de combinaisons qui précèdent la combinaison donnée dans l'ordre lexicographique.

L'opération inverse consiste à retrouver une combinaison donnée son rang dans la liste triée des combinaisons. Cela se fait en soustrayant, pas à pas, les combinaisons de plus petits éléments qui précèdent la combinaison souhaitée.

' Fonction inverse pour retrouver la combinaison à partir du rang
Sub RetrouverCombinaisonParRang(rg As ULongInt, v As Integer, k As Integer, combi() As Integer)
    Dim r As ULongInt = rg
    Dim j As Integer
    For i As Integer = 1 To k
        j = combi(i - 1) + 1
        While combine(v - j, k - i) <= r
            r -= CLngInt(combine(v - j, k - i))
            j += 1
        Wend
        combi(i) = j
    Next i
End Sub

Cette subroutine prend un rang rg et détermine la combinaison correspondante. Elle soustrait progressivement les combinaisons précédentes pour "éliminer" celles qui viennent avant le rang donné.

Les deux fonctions ci-dessus utilisent une fonction utilitaire pour calculer le nombre de combinaisons possibles de m éléments parmi n . Cette fonction est essentielle pour compter le nombre de combinaisons qui précèdent une combinaison donnée dans l'ordre lexicographique.

' Fonction pour calculer les combinaisons (combinaison de n parmi m)
Function combine(n As Integer, m As Integer) As Double
    Dim ic As Double
    Dim fa As Double
    Dim va As Double   
    fa = 1
    For ic = 1 To m
        fa = fa * ic
    Next ic
    va = 1
    For ic = (n - m + 1) To n
        va = va * ic
    Next ic
    combine = va / fa
End Function

Le calcul du rang lexicographique et l'opération inverse (retrouver la combinaison à partir du rang) sont des outils puissants pour optimiser la gestion des combinaisons dans des contextes comme les jeux de loterie, les statistiques, ou l'optimisation. Ces algorithmes permettent de travailler avec des indices plutôt qu'avec les combinaisons elles-mêmes, offrant ainsi des gains de performance et de mémoire.