IdentifiantMot de passe
Loading...
Mot de passe oublié ?Je m'inscris ! (gratuit)
Navigation

Inscrivez-vous gratuitement
pour pouvoir participer, suivre les réponses en temps réel, voter pour les messages, poser vos propres questions et recevoir la newsletter

MATLAB Discussion :

fonction récursive : comment améliorer le temps de calcul?


Sujet :

MATLAB

  1. #1
    Membre du Club
    Homme Profil pro
    Développeur informatique
    Inscrit en
    Décembre 2010
    Messages
    81
    Détails du profil
    Informations personnelles :
    Sexe : Homme

    Informations professionnelles :
    Activité : Développeur informatique
    Secteur : High Tech - Éditeur de logiciels

    Informations forums :
    Inscription : Décembre 2010
    Messages : 81
    Points : 50
    Points
    50
    Par défaut fonction récursive : comment améliorer le temps de calcul?
    bonsoir !!
    voila j'ai écris un fonction avec matlab mais le temps de calcul est trés grand
    commet je peut améliorer cette fonction pour y remédier ??
    merci d'avance
    voici le code :
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    function [tn] = cheby(n,x,N)
     
    a=-(n*(n+1)-(2*x-1)*(x-N-1)-x)/(x*(N-x));
    b=((x-1)*(x-N-1))/(x*(N-x));
    if (n==0 && x==0)
        tn=sqrt(1/N);
    elseif (x==1 && n>=1)
        tn=(1+(n*(n+1))/(1-N))*cheby(n-1,0,N);
    elseif (x==0 && n>=1)
        tn=(-sqrt(((N-n)*(2*n+1))/((N+n)*(2*n-1))))*cheby(n-1,0,N);
    else
            if (x>=2 && x<=(N/2))
     
             tn=a*cheby(n,x-1,N)+b*cheby(n,x-2,N);
     
            else 
                tn=cheby(n,(N-1-x),N)/(-1.^n);
            end
    end

  2. #2
    Membre habitué
    Homme Profil pro
    Ingénieur opto-électronique
    Inscrit en
    Avril 2010
    Messages
    129
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France

    Informations professionnelles :
    Activité : Ingénieur opto-électronique
    Secteur : Aéronautique - Marine - Espace - Armement

    Informations forums :
    Inscription : Avril 2010
    Messages : 129
    Points : 157
    Points
    157
    Par défaut
    Bonjour,

    Déjà tu peux décaler ton calcul de a et b pour le mettre dans la boucle conditionnelle où il sert. Ça ne sert à rien de le calculer si tu ne vas pas l'utiliser. Ensuite, tout dépend du but de ce que tu entreprends :

    Si ton but est simplement de connaitre les X premiers termes de ta suite t(n,x,N), alors le mieux est probablement de stocker les résultats dans une matrice en 3 dimensions, de lancer une boucle de manière à que ce chaque terme que tu calcules n'ait besoin que des termes précédemment calculés, et comme ça tu n'as pas besoin d'une fonction récursive, tu fais simplement appel aux résultats précédents.

    Si tu as besoin ponctuellement de t(x,y,z) et que tu te fous des résultats intermédiaires, ta méthode est probablement la plus rapide. Si toutefois au long de ton programme tu as besoin des termes dans l'entourage de (x,y,z), il peut être intéressant de stocker ces valeurs intermédiaires afin de les avoir disponibles lors du calcul suivant, et donc d'accélérer grandement le calcul suivant.


    Autre chose, je n'ai pas reconnu cette suite que tu veux calculer, mais si c'est un problème courant, tu peux éventuellement chercher sur google s'il n'y aurait pas des simplifications à faire, voire même si elle ne pourrait pas être exprimée sans récurrence.

  3. #3
    Membre du Club
    Homme Profil pro
    Développeur informatique
    Inscrit en
    Décembre 2010
    Messages
    81
    Détails du profil
    Informations personnelles :
    Sexe : Homme

    Informations professionnelles :
    Activité : Développeur informatique
    Secteur : High Tech - Éditeur de logiciels

    Informations forums :
    Inscription : Décembre 2010
    Messages : 81
    Points : 50
    Points
    50
    Par défaut
    merci pour votre réponse !!
    pour a et b le temps est légèrement amélioré
    mais quand x>=30 le calcule devient super lent
    la fonction permet de calculer les valeur du polynôme de Chebyshev
    elle est obligatoirement récursive .
    est ce que la décomposition de cette fonction en plusieurs fonction est meilleur??

  4. #4
    Expert éminent sénior
    Avatar de Caro-Line
    Profil pro
    Inscrit en
    Mars 2007
    Messages
    9 458
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Mars 2007
    Messages : 9 458
    Points : 14 830
    Points
    14 830
    Par défaut
    Juste un conseil qui ne changera rien au résultat : tu devrais donner un nom plus long à ta fonction car là on a du mal à voir où elle est appelée dans le code (elle se confond avec les variables).

    C'est d'ailleurs une habitude à prendre que de donner des noms "parlant" à tes fonctions.
    Règles du Forum

    Adepte de la maïeutique

  5. #5
    Membre du Club
    Homme Profil pro
    Développeur informatique
    Inscrit en
    Décembre 2010
    Messages
    81
    Détails du profil
    Informations personnelles :
    Sexe : Homme

    Informations professionnelles :
    Activité : Développeur informatique
    Secteur : High Tech - Éditeur de logiciels

    Informations forums :
    Inscription : Décembre 2010
    Messages : 81
    Points : 50
    Points
    50
    Par défaut
    mercii c'est fait !!
    et pour mon problème

  6. #6
    Membre habitué
    Homme Profil pro
    Ingénieur opto-électronique
    Inscrit en
    Avril 2010
    Messages
    129
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France

    Informations professionnelles :
    Activité : Ingénieur opto-électronique
    Secteur : Aéronautique - Marine - Espace - Armement

    Informations forums :
    Inscription : Avril 2010
    Messages : 129
    Points : 157
    Points
    157
    Par défaut
    J'ai du mal à voir le rapport avec les polynômes de Chebyshev. Pourquoi y a-t-il trois variables, à quoi correspondent-elles ?

    Toujours est-il qu'apparemment, tu veux calculer tous les termes. Sauvegardes tes résultats dans une matrice T[n,x,N] (remplie de zéros ou NaN au préalable).
    Quand tu veux calculer T[X,Y,Z], fais appel à ta fonction cheby, et ne l'appelle de façon récursive que si les termes précédents dont tu as besoin n'ont pas déjà été calculés dans ta matrice T.

    Ta fonctions serait alors

    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    function T=cheby(n,x,N,T)
     
     
    if (n==0 && x==0)
        T(n,x,N)=sqrt(1/N);
    elseif (x==1 && n>=1)
        if ~isnan(T(n-1,0,N))
             T(n-1,0,N)=(1+(n*(n+1))/(1-N))*T(n-1,0,N);
        else
             T=cheby(n-1,0,N,T);
             T(n-1,0,N)=(1+(n*(n+1))/(1-N))*T(n-1,0,N);
     
    %and so on...
    EDIT: j'ai supposé que n,x et N étaient entiers.

  7. #7
    Membre habitué
    Homme Profil pro
    Ingénieur opto-électronique
    Inscrit en
    Avril 2010
    Messages
    129
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France

    Informations professionnelles :
    Activité : Ingénieur opto-électronique
    Secteur : Aéronautique - Marine - Espace - Armement

    Informations forums :
    Inscription : Avril 2010
    Messages : 129
    Points : 157
    Points
    157
    Par défaut
    Par ailleurs, ta définition de t(n,x,N) est la suivante:

    t(0,0,N) = f1(N)

    t(n>=1,0,N) = f2(n,x,N).t(n-1,0,N)

    t(n>=1,1,N) = f3(n,x,N).t(n-1,0,N)

    t(n,2<=x<=N/2,N) = f4(n,x,N).t(n,x-1,N) + f5(n,x,N).t(n,x-2,N)

    t(n,N-1>=x>N/2,N) = f6(n,x,N)*t(n,N-1-x,N)


    Au vu de cet ensemble, si tu parcours les variables dans l'ordre suivant, tu ne devrais jamais avoir de récursivité:

    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
     
    T=NaN(nn,xx);
    for x=0:xx
        for n=0:nn
            T=cheby(n,x,N,T);
        end
    end

  8. #8
    Membre du Club
    Homme Profil pro
    Développeur informatique
    Inscrit en
    Décembre 2010
    Messages
    81
    Détails du profil
    Informations personnelles :
    Sexe : Homme

    Informations professionnelles :
    Activité : Développeur informatique
    Secteur : High Tech - Éditeur de logiciels

    Informations forums :
    Inscription : Décembre 2010
    Messages : 81
    Points : 50
    Points
    50
    Par défaut
    merci
    je vais essayé cette méthode et je vous tiens au courant

  9. #9
    Membre habitué
    Homme Profil pro
    Ingénieur opto-électronique
    Inscrit en
    Avril 2010
    Messages
    129
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France

    Informations professionnelles :
    Activité : Ingénieur opto-électronique
    Secteur : Aéronautique - Marine - Espace - Armement

    Informations forums :
    Inscription : Avril 2010
    Messages : 129
    Points : 157
    Points
    157
    Par défaut
    Chef, j'm'a trompé dans les indices de T, mais tu devrais pouvoir corriger ça :p

Discussions similaires

  1. [MEX] Comment diminuer le temps de calcul
    Par paS_Tek dans le forum MATLAB
    Réponses: 2
    Dernier message: 11/05/2015, 17h15
  2. Comment améliorer le temps de compilation pour C/C++ ?
    Par Hinault Romaric dans le forum C
    Réponses: 18
    Dernier message: 11/01/2013, 22h02
  3. Amélioration du temps de calcul pour creer des figures
    Par comoliv02 dans le forum MATLAB
    Réponses: 2
    Dernier message: 17/10/2007, 12h23
  4. Réponses: 2
    Dernier message: 27/12/2006, 14h31
  5. Comment mesurer le temps d'une fonction ?
    Par Battosaiii dans le forum Général JavaScript
    Réponses: 3
    Dernier message: 05/10/2006, 17h37

Partager

Partager
  • Envoyer la discussion sur Viadeo
  • Envoyer la discussion sur Twitter
  • Envoyer la discussion sur Google
  • Envoyer la discussion sur Facebook
  • Envoyer la discussion sur Digg
  • Envoyer la discussion sur Delicious
  • Envoyer la discussion sur MySpace
  • Envoyer la discussion sur Yahoo