Bonjour
J'ai analysé tout cela sur mon temps libre et c'est assez complexe de
comprendre comment le code récursif présenté fourni le résultat de la
formule mathématique.
Je suis convaincu que l'on peut économiser énormément de
multiplications à condition de créer une table de travail T de double
de longueur C(n,n-2)
Pour préparer cette table, le calcul des C(n,i) pour i=0 à n-2 doit
être réalisé initialement dans un table d'entiers de taille n, ce qui à
priori économise des additions par rapport au calcul récursif.
Ensuite, il s'agit de calculer le résultat R par la boucle suivante
d'indice i de 1 à n-1,
R=0
facteur=(1-beta)
pour chaque i
- boucle de k=0 à C(n,n-2)
si i=1,
si k=u, initialiser T[k]=1 sinon T[k] = s(k)
sinon
si k<>u T[k] = T[k] * s(k+i-1)
- Ri=0
- boucle de k=0 à C(n,i-1) : Ri = Ri + T[k]
- R = R + facteur * Ri
- facteur = facteur * (1-beta)
fin de boucle i
Si j'ai vu juste, ce code purement impératif réalise exactement le
nombre de multiplications requises à l'exception de quelques exclusions
de s(u) remplacées par un produit par 1.
Je participe volontiers à l'élaboration du code lui-même et à sa
comparaison en terme de performance mais il me faudrait le source
complet d'origine avec un jeu de données pour valider.
Évidemment c'est mono-thread. Avec des valeurs élevées de n, on peut
envisager un code parallèle qui malheureusement devra réaliser des
multiplications redondantes et gérer un rendez-vous - à voir si la
complexité en vaut la chandelle.
Cordialement
--
Yves Martin
On Tue, 2020-03-17 at 15:25 +0100, Patrick Dupre wrote:
> Je mets la formule en pdf
> J'espere que c'est clair.
>
> =====================================================================
> ======
> Patrick DUPRÉ | | email:
> pdupre@???
> Laboratoire interdisciplinaire Carnot de Bourgogne
> 9 Avenue Alain Savary, BP 47870, 21078 DIJON Cedex FRANCE
> Tel: +33 (0)380395988
> =====================================================================
> ======
>
>
> > Sent: Tuesday, March 17, 2020 at 1:47 PM
> > From: "Yves Martin" <ymartin59@???>
> > To: "Patrick Dupre" <pdupre@???>, guilde <guilde@???
> > >
> > Subject: Re: Optimization de code c
> >
> > On Tue, 2020-03-17 at 10:42 +0100, Patrick Dupre wrote:
> > > En cette periode de teletravail, j'aimerai optimizer cette
> > > routine
> > > (en temps CPU)
> > >
> > > void nume_pop_absor_satur (const double* S, const unsigned short
> > > int
> > > e, const unsigned short int n, const unsigned short int i, const
> > > unsigned short int k, const short int kk, double *sum, double
> > > prod) {
> > > unsigned short int j ;
> > > if (kk >= 0) {
> > > for (j = i ; j < n - kk ; j++) {
> > > if (j == e) continue ;
> > > if (k == 0) {
> > > *sum += S [j] ;
> > > }
> > > else nume_pop_absor_satur (S, e, n, j + 1, k, kk - 1, sum,
> > > prod
> > > * S [j]) ;
> > > }
> > > }
> > > else {
> > > *sum += prod ;
> > > }
> > > }
> > >
> > > Est-ce que vous auriez des idees ?
> >
> > Bonjour
> >
> > Joli défi. Je pense que le plus grand facteur de gain sera de
> > supprimer
> > l'appel récursif ("dé-récursiver") pour éviter la mise en pile des
> > paramètres - à moins que le compilo ait été suffisamment futé pour
> > passer tous les paramètres en registres et identifier les variables
> > qui
> > ne changent pas - et donc inutiles d'empiler.
> >
> > Par contre, le reverse-engineering va me donner la migraine.
> >
> > Aurais-tu s'il te plaît le modèle mathématique de ce calcul (je
> > vois
> > bien une définition de suite arriver...)
> >
> > --
> > Yves Martin
> >
> >
