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

C++ Discussion :

Transcription algorithme récursif Matlab/C++


Sujet :

C++

  1. #1
    Membre habitué
    Profil pro
    Inscrit en
    Novembre 2009
    Messages
    134
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Novembre 2009
    Messages : 134
    Points : 129
    Points
    129
    Par défaut Transcription algorithme récursif Matlab/C++
    Bonsoir,

    Après avoir écrit une fonction sous Matlab me permettant de calculer l'ensemble des combinaisons possibles d'allocations de portefeuilles comme ci-dessous :

    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    t{1} = 0:0.1:1;
    t{2} = 0:0.2:1;
    t{3} = 0:0.5:1;
    resultattemporaire = [];
    resultat = [];
    resultat = allocation(t,resultattemporaire,resultat);
    Avec la fonction récursive allocation :

    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    function resultat = allocation(t,resultattemporaire,resultat)
     
    indice = length(resultattemporaire)+1;
    for k=1:length(t{indice})
        if sum(resultattemporaire)+t{indice}(k)<=1 && indice<numel(t)
            resultattemporaire2 = [resultattemporaire t{indice}(k)];
            resultat = allocation(t,resultattemporaire2,resultat);
        elseif sum(resultattemporaire)+t{indice}(k)==1 && indice==numel(t)
            resultat = [resultat;[resultattemporaire t{indice}(k)]];
        end
    end
    Me donne toutes les combinaisons < 1 de t{1} à t{3} suivant les pas d'incrémentations t{2}

    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    >> resultat
     
    resultat =
     
             0         0    1.0000
             0    1.0000         0
        0.1000    0.4000    0.5000
        0.2000    0.8000         0
        0.3000    0.2000    0.5000
        0.4000    0.6000         0
        0.5000         0    0.5000
        0.6000    0.4000         0
        0.8000    0.2000         0
        1.0000         0         0
    Le soucis est que pour des vecteurs de 50 lignes par exemple, le temps d'execution de cette fonction est extrêment long
    Je souhaite donc re-écrire la fonction allocation.m en C++ puis la convertire en format MEX en espérant réduire le temps de calcul sous Matlab.

    Le fait est que j'ai beaucoup de mal à écrire cette fonction récursive en C++ En fait j'ai du mal avec toutes les fonctions récursives .

    Une aide serait la bienvenue

    Merci !
    Au taf : Quad Core/8Go de RAM sous Win Seven 64 - Matlab 2009b 64bit.
    Perso : Core 2 Duo/8Go de RAM Mac OS X 10.6 - Matlab 2009b 64bit

  2. #2
    Membre chevronné
    Avatar de Goten
    Profil pro
    Inscrit en
    Juillet 2008
    Messages
    1 580
    Détails du profil
    Informations personnelles :
    Âge : 33
    Localisation : France

    Informations forums :
    Inscription : Juillet 2008
    Messages : 1 580
    Points : 2 205
    Points
    2 205
    Par défaut
    Le C++ est pas ce qu'il y'a de plus adaptée pour faire des fonctions récursives.. J'ai peur qu'avec des grosses récursions tu fasses péter la pile. Une bonne idée serait de transformer ton algorithme récursif en itératif...
    "Hardcoded types are to generic code what magic constants are to regular code." --A. Alexandrescu

  3. #3
    Membre expert
    Profil pro
    Inscrit en
    Mars 2007
    Messages
    1 415
    Détails du profil
    Informations personnelles :
    Localisation : France, Paris (Île de France)

    Informations forums :
    Inscription : Mars 2007
    Messages : 1 415
    Points : 3 156
    Points
    3 156
    Par défaut
    Salut !

    à plus forte raison que générer des combinaisons de portefeuille avec un pas est quand même pas quelque chose de très lourd en calcul !

    Deux boucles, et sans récursion, font l'affaire :

    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
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
     
    #include <cstdlib>
    #include <vector>
    #include <iostream>
     
    struct portefeuille {
    	float actions;
    	float hedge;
    	float obligs;
    };
     
    typedef struct portefeuille Portefeuille;
     
    int main(int argc, char* argv[])
    {
    	std::vector<Portefeuille> possibilites;
     
    	const float pas = 0.1f;
    	float partAction = 0.f;
    	float partHedge = 0.f;
    	float partOblig = 0.f;
    	float restant;
     
    	while(partAction <= 1.f){
    		restant = 1.f - partAction;
    		partHedge = 0.f;
     
    		while(partHedge <= restant){
    			partOblig = restant - partHedge;;
     
    			Portefeuille courant = {partAction,partHedge,partOblig};
    			possibilites.push_back(courant);
     
    			partHedge += pas;
    		}
     
    		partAction += pas;
    	}
     
    	// Affichage
    	for(std::vector<Portefeuille>::iterator it = possibilites.begin(); it != possibilites.end(); it ++){
    		std::cout << it->actions << "," << it->hedge << "," << it->obligs << std::endl;
    	}
     
    	return 0;
    }
    J'ai pas fait de matlab depuis longtemps alors je te l'ai fait en C++ mais ça s'adapte easy.

    Edit : je viens de percuter qu'en fait, ton nombre d'actifs est variable donc ma solution ne sert à rien . Anyway, je suis sûr qu'on doit pouvoir trouver une solution simple qui calculer assez vite.
    Find me on github

  4. #4
    Membre chevronné
    Avatar de Joel F
    Homme Profil pro
    Chercheur en informatique
    Inscrit en
    Septembre 2002
    Messages
    918
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 43
    Localisation : France, Essonne (Île de France)

    Informations professionnelles :
    Activité : Chercheur en informatique
    Secteur : Service public

    Informations forums :
    Inscription : Septembre 2002
    Messages : 918
    Points : 1 921
    Points
    1 921
    Par défaut
    Citation Envoyé par Goten Voir le message
    Le C++ est pas ce qu'il y'a de plus adaptée pour faire des fonctions récursives.. J'ai peur qu'avec des grosses récursions tu fasses péter la pile. Une bonne idée serait de transformer ton algorithme récursif en itératif...
    Si la fonction est tail-recursive, la plupart des compilateurs sérieux le font tout seul.

    Tail-recursive: http://fr.wikipedia.org/wiki/R%C3%A9cursion_terminale

  5. #5
    Membre habitué
    Profil pro
    Inscrit en
    Novembre 2009
    Messages
    134
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Novembre 2009
    Messages : 134
    Points : 129
    Points
    129
    Par défaut
    @ jblecanard

    Oui, je calcul des allocations sur des portefeuilles allant de 1 à 40 titres maximum, avec des incréments souvents différents sur chaque titre ;

    @ Joel F et Goten

    Au final j'ai écrit en C++ hybride .mex une fonction itérative :

    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
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    73
    74
    75
    76
    77
    78
    79
    80
    81
    82
    83
    84
    85
    86
    87
    88
    89
    90
    91
    92
    93
    94
    95
    96
    97
    98
    99
    100
    101
    102
    103
    104
    105
    106
    107
    108
    # include "mex.h"
     
     
    // CALCUL DES ALLOCATIONS INITIALES DE PORTEFEUILLES.
    void mexFunction(int nlhs, mxArray *plhs[], int nrhs, const mxArray *prhs[])
    {
    	 double *PoidsDepart, *Pas, *PoidsFin, Allocations[40][500], *AllocationsFinales;
    	 double Compteur;
    	 int j, k, Numero;
    	 double i[40];
     
    	 mxArray *ValeursDepart;
    	 mxArray *ValeursPas;
    	 mxArray *ValeursFin;
     
             if (nrhs!=3)
    	 {	
    		mexErrMsgTxt ("Nombre d'arguments incorrect !");
    	 }	
    	 if (nlhs>1)
    	 {	
    		mexErrMsgTxt ("Une seule variable est calculée !");
    	 }
     
    	 ValeursDepart = prhs[0];
    	 ValeursPas = prhs[1];
    	 ValeursFin = prhs[2];
     
    	 PoidsDepart = mxGetPr(ValeursDepart);
    	 Pas = mxGetPr(ValeursPas);
    	 PoidsFin = mxGetPr(ValeursFin);
     
    	 Numero = 0;
     
    	 for (i[0]=PoidsDepart[0]; i[0]<=(PoidsFin[0]+0.000001); i[0]=i[0]+Pas[0]) 
    	 {for (i[1]=PoidsDepart[1]; i[1]<=(PoidsFin[1]+0.000001); i[1]=i[1]+Pas[1]) 
    	 {for (i[2]=PoidsDepart[2]; i[2]<=(PoidsFin[2]+0.000001); i[2]=i[2]+Pas[2]) 
    	 {for (i[3]=PoidsDepart[3]; i[3]<=(PoidsFin[3]+0.000001); i[3]=i[3]+Pas[3])
             {for (i[4]=PoidsDepart[4]; i[4]<=(PoidsFin[4]+0.000001); i[4]=i[4]+Pas[4]) 
    	 {for (i[5]=PoidsDepart[5]; i[5]<=(PoidsFin[5]+0.000001); i[5]=i[5]+Pas[5]) 
    	 {for (i[6]=PoidsDepart[6]; i[6]<=(PoidsFin[6]+0.000001); i[6]=i[6]+Pas[6]) 
    	 {for (i[7]=PoidsDepart[7]; i[7]<=(PoidsFin[7]+0.000001); i[7]=i[7]+Pas[7]) 
    	 {for (i[8]=PoidsDepart[8]; i[8]<=(PoidsFin[8]+0.000001); i[8]=i[8]+Pas[8])
    	 {for (i[9]=PoidsDepart[9]; i[9]<=(PoidsFin[9]+0.000001); i[9]=i[9]+Pas[9])	
    	 {for (i[10]=PoidsDepart[10]; i[10]<=(PoidsFin[10]+0.000001); i[10]=i[10]+Pas[10]) 
    	 {for (i[11]=PoidsDepart[11]; i[11]<=(PoidsFin[11]+0.000001); i[11]=i[11]+Pas[11]) 
    	 {for (i[12]=PoidsDepart[12]; i[12]<=(PoidsFin[12]+0.000001); i[12]=i[12]+Pas[12]) 
    	 {for (i[13]=PoidsDepart[13]; i[13]<=(PoidsFin[13]+0.000001); i[13]=i[13]+Pas[13])
             {for (i[14]=PoidsDepart[14]; i[14]<=(PoidsFin[14]+0.000001); i[14]=i[14]+Pas[14]) 
    	 {for (i[15]=PoidsDepart[15]; i[15]<=(PoidsFin[15]+0.000001); i[15]=i[15]+Pas[15]) 
    	 {for (i[16]=PoidsDepart[16]; i[16]<=(PoidsFin[16]+0.000001); i[16]=i[16]+Pas[16]) 
    	 {for (i[17]=PoidsDepart[17]; i[17]<=(PoidsFin[17]+0.000001); i[17]=i[17]+Pas[17]) 
    	 {for (i[18]=PoidsDepart[18]; i[18]<=(PoidsFin[18]+0.000001); i[18]=i[18]+Pas[18])
    	 {for (i[19]=PoidsDepart[19]; i[19]<=(PoidsFin[19]+0.000001); i[19]=i[19]+Pas[19])	 
    	 {for (i[20]=PoidsDepart[20]; i[20]<=(PoidsFin[20]+0.000001); i[20]=i[20]+Pas[20]) 
    	 {for (i[21]=PoidsDepart[21]; i[21]<=(PoidsFin[21]+0.000001); i[21]=i[21]+Pas[21]) 
    	 {for (i[22]=PoidsDepart[22]; i[22]<=(PoidsFin[22]+0.000001); i[22]=i[22]+Pas[22]) 
    	 {for (i[23]=PoidsDepart[23]; i[23]<=(PoidsFin[23]+0.000001); i[23]=i[23]+Pas[23])
             {for (i[24]=PoidsDepart[24]; i[24]<=(PoidsFin[24]+0.000001); i[24]=i[24]+Pas[24]) 
    	 {for (i[25]=PoidsDepart[25]; i[25]<=(PoidsFin[25]+0.000001); i[25]=i[25]+Pas[25]) 
    	 {for (i[26]=PoidsDepart[26]; i[26]<=(PoidsFin[26]+0.000001); i[26]=i[26]+Pas[26]) 
    	 {for (i[27]=PoidsDepart[27]; i[27]<=(PoidsFin[27]+0.000001); i[27]=i[27]+Pas[27]) 
    	 {for (i[28]=PoidsDepart[28]; i[28]<=(PoidsFin[28]+0.000001); i[28]=i[28]+Pas[28])
    	 {for (i[29]=PoidsDepart[29]; i[29]<=(PoidsFin[29]+0.000001); i[29]=i[29]+Pas[29])	  
    	 {for (i[30]=PoidsDepart[30]; i[30]<=(PoidsFin[30]+0.000001); i[30]=i[30]+Pas[30]) 
    	 {for (i[31]=PoidsDepart[31]; i[31]<=(PoidsFin[31]+0.000001); i[31]=i[31]+Pas[31]) 
    	 {for (i[32]=PoidsDepart[32]; i[32]<=(PoidsFin[32]+0.000001); i[32]=i[32]+Pas[32]) 
    	 {for (i[33]=PoidsDepart[33]; i[33]<=(PoidsFin[33]+0.000001); i[33]=i[33]+Pas[33])
    	 {for (i[34]=PoidsDepart[34]; i[34]<=(PoidsFin[34]+0.000001); i[34]=i[34]+Pas[34]) 
    	 {for (i[35]=PoidsDepart[35]; i[35]<=(PoidsFin[35]+0.000001); i[35]=i[35]+Pas[35]) 
    	 {for (i[36]=PoidsDepart[36]; i[36]<=(PoidsFin[36]+0.000001); i[36]=i[36]+Pas[36]) 
    	 {for (i[37]=PoidsDepart[37]; i[37]<=(PoidsFin[37]+0.000001); i[37]=i[37]+Pas[37]) 
    	 {for (i[38]=PoidsDepart[38]; i[38]<=(PoidsFin[38]+0.000001); i[38]=i[38]+Pas[38])
    	 {for (i[39]=PoidsDepart[39]; i[39]<=(PoidsFin[39]+0.000001); i[39]=i[39]+Pas[39]) 
    	 {
    		 Compteur = 0; 
     
    		 for (k=0; k<40; k++)
    		 {
    			 Compteur = Compteur + i[k];
    		 }
    	         if (Compteur<(1+0.000001) && Compteur>(1-0.000001))
    	        {
    		    Numero = Numero+1;      
     
    		    if (Numero > 500)
    		    {  
    			   mexErrMsgTxt ("Nombre maximal de portefeuilles atteint !");
    		    }
    		    for (j=0; j<40; j++)
    		    {	   
    				Allocations[j][Numero-1] = i[j];
    	        }
    	     }
    	  }
    	 }}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}
     
    	 plhs[0] = mxCreateDoubleMatrix(Numero, 40, mxREAL);
    	 AllocationsFinales = mxGetData(plhs[0]); 
     
    	 for (k=0; k<Numero; k++)
    	 {
    		 for (j=0; j<40; j++)
    		 {
    			 AllocationsFinales[k+(j*Numero)] = Allocations[j][k];
    		 }
    	 }	
    }
    Les temps d'executions sont très courts (la limite de 500 portefeuilles y est pour beaucoup faut dire ).

    En tout cas merci pour vos réponses
    Au taf : Quad Core/8Go de RAM sous Win Seven 64 - Matlab 2009b 64bit.
    Perso : Core 2 Duo/8Go de RAM Mac OS X 10.6 - Matlab 2009b 64bit

Discussions similaires

  1. Algorithme récursif (Poker)
    Par MagicTux dans le forum Débuter
    Réponses: 5
    Dernier message: 31/01/2009, 15h12
  2. comment ecrire les algorithme en MATLAB?
    Par waliddz dans le forum MATLAB
    Réponses: 1
    Dernier message: 27/10/2008, 11h52
  3. Algorithme récursif de calcul de moyenne
    Par kromartien dans le forum Mathématiques
    Réponses: 25
    Dernier message: 23/10/2007, 12h05
  4. [SQL] Tree : algorithme récursif
    Par Fabouney dans le forum PHP & Base de données
    Réponses: 4
    Dernier message: 03/08/2007, 16h39
  5. problème algorithme récursif
    Par seb888 dans le forum Général Java
    Réponses: 11
    Dernier message: 04/06/2005, 22h35

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