Discussion :

[hazem2410]

Bonjour,

J'ai un algorithme de calcule basé sur une fonction de combinaison probabiliste. J'ai effectué un line by line profiling et je sais désormais, d'où vient la lenteur. Ma première fonction est nCr, qui prend deux entiers n et r pour renvoyer la combinaison (nombre entier).

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
 
from itertools import izip
    def nCr(self,n,r):
 
        if n > r:
            return reduce(lambda x, y: x * y[0] / y[1], izip(xrange(n - r + 1, n+1), xrange(1, r+1)), 1)
        elif n == r:
            return 1
        else: 
            return 0

La deuxième fonction se base sur des combinaisons en vecteur. En effet, le code d'origine est en loop for, ça donne ceci:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
 
        z_triangle = 3*x1*np.array( [ nCr(L1,1) , nCr(L2, 1) ] )                
        for k in range(1,triangle_number_max):
            z_triangle += x1*np.array( [ nCr(L1, k+1), nCr(L2, k+1) ] )/2**k

Pour améliorer ceci, je définis un numpy array qui a le range de k, j'applique la fonction nCr en vecteur, qui j'applique la somme par einsum. Ainsi le code devient ainsi:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
 
        z_triangle = 3*x1*np.array([self.nCr(L1, 1), self.nCr(L2, 1)])        
        l = np.arange(1,triangle_number_max)
        z_triangle = z_triangle+ x1*np.einsum( 'ij->i',np.array( [ np.vectorize(nCr) (L1,l+1) , np.vectorize(nCr) (L2,l+1) ] ) / 2**l )

Toutefois, ce dernier code prend beaucoup de temps aussi (un tout petit peu moins que le précédent). J'ai d'énormes simulations, et diviser le temps de cette opération par deux ou trois m'aiderai énormément.

Merci d'avance.

[fred1599]

Bonjour,

Il faudrait préciser un peu plus en détails ce que font chaque fonctions à optimiser...

Après je vois par exemple que

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
from itertools import izip
    def nCr(self,n,r):
 
        if n > r:
            return reduce(lambda x, y: x * y[0] / y[1], izip(xrange(n - r + 1, n+1), xrange(1, r+1)), 1)
        elif n == r:
            return 1
        else: 
            return 0

peut être optimisé en mettant les conditions n==r et n<r comme condition à contrôler en premier avant de faire le calcul de reduce. C'est pas grand chose, mais c'est déjà ça.

Pour le reste si tu ne développes pas ce que tu fais en mathématiques (ainsi que leurs algorithmes respectifs), je pourrais guère t'aider, mes maths étant bien rouillé.

EDIT: Je soupçonne que tu cherches à déterminer le nombre de combinaisons par les coefficients binomiaux... alors je me demande pourquoi ne pas simplement faire...

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
from math import factorial as fact
def nCr(self, n, r):
    return int(fact(n)/(fact(r)*fact(n-r)))

[Alexis.M]

Il existe déja une fonctione combinaison, qui en plus gère très bien le "broadcasting"

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
from scipy.misc import comb
 
Ns = [5, 6]
ks = np.arange(7).reshape(-1, 1)  # Pour avoir un tableau shape = (6, 1)
comb(Ns, ks)

array([[  1.,   1.],
       [  5.,   6.],
       [ 10.,  15.],
       [ 10.,  20.],
       [  5.,  15.],
       [  1.,   6.],
       [  0.,   1.]])

Et pour le reste:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
 
Ls = [L1, L2]
ks = np.arange(num_max).reshape(-1, 1) # num_max + 1 ?
combs = comb(Ls, ks + 1) / (2 ** ks)
z_triange = x1 * (
     np.sum(combs, axis=1) + 
     2 * combs[0] # +2 car on a déjà compté une fois
)