Bonjour, 

je dipose du code ci-dessous sous Scilab récursif en la variable k de la fonction delta et donc peu efficace. Je ne sais pas comment le transformer en itératif. C'est une façon de penser dont je n'ai pas trop l'habitude. Pouvez-vous m'aider ? Idem pour la fonction alpha.

Merci. Je précise que c'est un repost, n'ayant pas eu de succès en le posant dans d'autres rubriques du forum, ce qui explique que ce n'est pas du C++ bien que ça ne devrait pas poser de problèmes aux intervenants (le problème n'est pas la syntaxe). 

function[res]=delta(y,x,k,p,N,L,pi)
    Eu=E(p,N)
    P=Pa(N)
    if k==1 then
        z=y(1,:)
        res= pi(x+1)*Eu(1+z(1)+z(2)*(N+1),x+1)
    else
    for i=0:N
       u(i+1)=delta(y,i,k-1,p,N,L,pi)*P(i+1,x+1)
            end
      
    w=y(k,:)
    res=max(u)*Eu(1+w(1)+w(2)*(N+1),x+1)
    end
  endfunction
 
function[res]=alpha(y,x,k,p,N,L,pi)
    Eu=E(p,N)
    P=Pa(N)
    res=0
    if k==1 then
        z=y(1,:)
        res=Eu(1+z(1)+z(2)*(N+1),x+1)*pi(x+1)
    else
        w=y(k,:)
        for i=0:N
            res=res+alpha(y,i,k-1,p,N,L,pi)*P(i+1,x+1)*Eu(1+w(1)+w(2)*(N+1),x+1)
        end
    end
  
endfunction

Qu'est-ce qui prouve que ce n'est donc pas efficace ?

Tu compares avec l'efficacité du code qui n'existe pas ?

> Ca ne devrait pas poser de problème aux intervenants

ceux qui n'ont que ça à faire

Faut être sérieux : dérécursiver "bêtement", ce n'est qu'une micro-optimisation. Si on veut un vrai gain, il faut comprendre le problème, ce qui permettra d'améliorer l'algorithme de calcul. Tes trucs, c'est incompréhensible.

-
Edité par michelbillaud 17 octobre 2020 à 17:45:38

Bonjour, 

je ne suis pas étudiant en info déjà je précise vu que votre dernier message n'est pas très sympathique.

Je suis étudiant en proba, et c'est un programme en chaîne de Markov. La fonction delta(k) appelle delta(k-1) donc la pile augmente donc oui ce n'est pas efficace puisque je dois attendre presque 1 minute pour avoir un retour pour des petites valeurs des paramètres d'entrée.

y est une matrice de taille Lx2 d'entiers entre 0 et N, P une matrice carrée de taille N+1, x un entier entre 0 et N, N un entier, L un entier, pi un vecteur de réels de somme 1 de taille N+1, p une proba entre 0 et 1. Pas sûr que ça vous aide...

L'exemple académique courant, c'est l'algorithme de n! que l'on transforme en itératif ou en récursif terminal, n'est-ce pas ? Je voudrais faire la même chose ici. 

Quand je disais "ça ne devrait pas poser de problème", je voulais dire que la syntaxe n'est pas celle de C++, c'est tout. Donc merci de ne pas me faire dire ce que je n'ai pas dit. 

Justement, ce n'est pas un appel terminal.

Donc ça ne se transforme pas directement en boucle, il faut introduire une pile explicite, qui ne fait que simuler ce que fait la pile de la version récursive.  ce qui fait qu'on ne gagne pas grand chose.

Pour y gagner quelque chose, il faut trouver des moyens de court circuiter certains calculs. Par exemple, pour recursiver  fibonacci, ou on s'aperçoit que fib(n-2) intervient dans le calcul de fib(n) et aussi dans fib(n-1) qui y intervient aussi. Mais il faut connaître le probleme qui est dessous.  C'est pas juste un jeu d'ecritures

-
Edité par michelbillaud 17 octobre 2020 à 20:51:19

Entendu, je comprends, il faut une astuce mathématique. Mais là, j'avoue que je ne vois pas... Il s'agit de l'algorithme de Viterbi (slide 24 : http://pascal.rigaud4.free.fr/Polytech/cours/fc/Algo Viterbi.pdf) Je vais sûrement dans une seule et même fonction, calculer une matrice delta, une matrice psi, je les mets en mémoire et je peux ensuite calculer mes argmax...

Un coup de Google "viterbi iterative" montre qu'il y a des articles de recherche sur le sujet, comme quoi ce n'est sans doute pas un problème trivial.

Tu peux déjà sortir les termes constants de tes boucles (dans alpha). z et w, c'est un peu beaucoup la même chose. Il faut simplifier parfois pour voir se dégager les patterns et espérer changer l'architecture d'un code. Maintenant... comme Michel l'a dit, ce n'est pas du récursif terminal, cela ne va pas se changer en itératif efficace par magie.

Sinon, si mes souvenirs sont bons, il y a possibilité de gagner un facteur constant en performances par rapport à scilab en changeant de langage (genre python + numba, ou même (fallait pas venir ici): C++...).

EDIT-PS: il y a des choses qui peuvent être précalculée: genre les (1+w(1)+w(2)*(N+1))[k], pour un k donné, cela ne change pas, et tes fonctions sont appelées N fois pour chaque K. => factoriser et cacher en amont.
Si E est un tableau à 4 dimensions... diantre! Si par contre c'est une fonction, pareil => précalcule E(p,N), il ne change pas une seule fois! Idem pour Pa

-
Edité par lmghs 18 octobre 2020 à 13:21:46

Hello, Je ne suis absolument pas un pro de SciLab, mais il me semblerait assez surprenant qu'il n'y ait pas d'optimisations de faites par le logiciel sur du code fournit ; ce n'est certainement pas un «simple interpréteur». On trouve rapidement des remarques du genre «Not using vectorized operations in Scilab is the main source for suffering from a slow code.» →http://kiwi.emse.fr/SCILAB/sci-bot/c1143.htm

De plus la fonction delta(k) n'appelle pas la fonction delta(k-1), mais au niveau k on fait n appels récursifs à un niveau n-1 … du coup comme ça à vue de nez ça doit donner basiquement une complexité exponentielle. On pourrait peut-être avoir une amélioration des perf avec une approche bottom-top genre programmation dynamique. À creuser …

mais bon, ce ne sont que quelques réflexions en diagonales après 3 minutes de lecture.

Bon, merci pour vos remarques même si beaucoup me dépassent. Je comprends, avec la compréhension que j'ai de mon algorithme de Viterbi, que j'ai tout intérêt à faire une seule fonction. Les fonction delta et psi ne prennent en fait qu'un nombre fini de valeurs donc je peux calculer sans peine la matrice delta (chaque ligne sera un delta(k)), idem pour psi et j'obtiendrai normalement facilement mes y*. Bref, si je fais un effort sur ce que je dois faire mathématiquement, je dois pouvoir me passer d'optimisation "algorithmique" (les paramètres L,N sont petits, si ce n'était pas le cas, je pense qu'il faudrait mener une vraie réflexion plus approfondie).

Et ça va demander pas mal de boulot.

Je ne sais pas s'il y a tant de boulot que ça.

Après un premier nettoyage pour factoriser, on tombe, si je ne m'abuse, sur:

function[res]=alpha_impl(x,k,N,pi, Eu, Eu_idx_1, P)
    eu_cache = Eu(Eu_idx_1(k),x+1) // même valeur qq soit k => factoriser
    if k==1 then
        res=pi(x+1)
    else
        res=0
        for i=0:N
            res=res+alpha_impl(i,k-1,N,pi, Eu, Eu_idx_1, P) * P(i+1,x+1)
        end
    end
    res = res * eu_cache // pas besoin de multiplier à chaque itération
endfunction

function[res]=alpha(y,x,k,p,N,pi) // L ne sert à rien! => KISS
    P=Pa(N)  // ne pas recalculer à chaque fois!
    Eu=E(p,N) // ne pas recalculer à chaque fois!
    for kk = 0:k
        w = y(kk,:)
        // Pas sûr pour la syntaxe pour déclarer un tableau de dimension k
        // Ca sert à cacher tous les premiers index dans les Eu, vu qu'ils sont toujours identique
        Eu_idx_1(kk) = 1+w(1)+w(2)*(N+1)
    end

    res = alpha_impl(x, k, N, pi, Eu, Eu_idx_1, P)
endfunction

Et là... J'ai la furieuse impression que tous les alpha_impl de niveau k vont être calculés à partir de tous les alpha_impl(k-1, X in [0:N]) -- seuls k et x varient lors d'une récursion, tout le reste reste identique. De fait, j'ai comme l'impression que l'on peut procéder à l'envers. On calcule tous (pour tous les X de 0 à N) les alpha au niveau k=0 d'abord, et là on calcule tous les alpha au niveau k=1, et ainsi de suite.

Et si après ça c'est toujours trop lent => langage compilé: Python+numba ou C++.

-
Edité par lmghs 19 octobre 2020 à 23:16:20

Il faut éviter de refaire des calculs qui ont deja ete faits.

Et pour ça, il vaudrait mieux lire les papiers de ceux qui ont déjà fait de la recherche dessus !