+ Répondre à la discussion
Page 2 sur 8 PremièrePremière 123456 ... DernièreDernière
Affichage des résultats 21 à 40 sur 142
  1. #21
    Rédacteur/Modérateur

    Avatar de millie
    Profil pro
    Inscrit en
    juin 2006
    Messages
    6 944
    Détails du profil
    Informations personnelles :
    Localisation : Luxembourg

    Informations forums :
    Inscription : juin 2006
    Messages : 6 944
    Points : 9 773
    Points
    9 773

    Par défaut

    Une solution en C++, dont je suis pas très fier du code (d'ailleurs, si quelqu'un pondait ça dans un de mes projets, je le dégage sec

    J'y ajouterai quelques explications et j'essayerai de rendre le code plus potable.

    Fonctionne parfaitement avec de grande valeur :

    Il y a des optimisations très bourrine sur la génération des combinaisons.

    Dernière version ici : http://www.developpez.net/forums/sho...0&postcount=55

    Code C++ :
    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
    #include <iostream>
    #include <vector>
     
    /*affiche un vecteur*/
    void afficher(std::vector<int> & list)
    {
        std::cerr<<"[";
        for(int i =0; i <list.size()-1; i++)
            std::cerr<<list[i]<<", ";
        std::cerr<<list[list.size()-1];
     
        std::cerr<<"], "<<std::endl;
    }
     
    /*calcul la somme d'un vecteur*/
    int somme(std::vector<int> & list)
    {
        int total = 0;
        for(int i=0; i<list.size(); i++)
            total += list[i];
        return total;
    }
     
    /*met tout le vecteur à 1 sauf le premier élément à n*/
    void mettrePremierN(std::vector<int> & list, int n)
    {
        list[0] = n;
        for(int i = 1; i<list.size(); i++)
            list[i] = 1;
    }
     
    /*genère la combinaison suivante suivant un critère très particulier*/
    void genererSuivant(std::vector<int> & list)
    {
        int currentMax = 0;
        int pos = 0;
     
        for(pos=0; pos<list.size()-1; pos++)
            if(list[pos+1]< list[pos])
                currentMax = pos+1;
     
        if(pos == list.size()-1)
            list[currentMax]++;
    }
     
    /*génère l'ensemble des solutions dont la taille du vecteur vaut taille*/
    void generationSolution(int n, int taille)
    {
        std::vector<int> list;
        for(int i=0; i<taille; i++)
            list.push_back(1);
     
        for(int i=1; i<=n; i++)
        {
            int total = 0;
            mettrePremierN(list, i);
            while(total<=n && list[0]==i)
            {
                total = somme(list);
                if(total == n)
                    afficher(list);
                if(total >=n)
                    break;
                genererSuivant(list);
            }
        }
     
    }
     
    /*génère l'ensemble des solutions*/
    void generationSomme(int n)
    {
        for(int taille = n; taille>0; taille--)
            generationSolution(n, taille);
    }
     
     
     
    int main()
    {
        generationSomme(5);
        return 0;
    }

    A partir, par exemple du vecteur : 4 1 1 1
    genererSuivant génère successivement les combinaisons suivantes :
    4 1 1 1
    4 2 1 1
    4 2 2 1
    4 2 2 2
    4 3 2 2
    4 3 3 2
    4 3 3 3
    4 4 3 3
    4 4 4 3
    4 4 4 4


    Code :
    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
    //Générer 10 :
    
    [1, 1, 1, 1, 1, 1, 1, 1, 1, 1],
    [2, 1, 1, 1, 1, 1, 1, 1, 1],
    [2, 2, 1, 1, 1, 1, 1, 1],
    [3, 1, 1, 1, 1, 1, 1, 1],
    [2, 2, 2, 1, 1, 1, 1],
    [3, 2, 1, 1, 1, 1, 1],
    [4, 1, 1, 1, 1, 1, 1],
    [2, 2, 2, 2, 1, 1],
    [3, 2, 2, 1, 1, 1],
    [4, 2, 1, 1, 1, 1],
    [5, 1, 1, 1, 1, 1],
    [2, 2, 2, 2, 2],
    [3, 2, 2, 2, 1],
    [4, 2, 2, 1, 1],
    [5, 2, 1, 1, 1],
    [6, 1, 1, 1, 1],
    [3, 3, 2, 2],
    [4, 2, 2, 2],
    [5, 2, 2, 1],
    [6, 2, 1, 1],
    [7, 1, 1, 1],
    [4, 3, 3],
    [5, 3, 2],
    [6, 2, 2],
    [7, 2, 1],
    [8, 1, 1],
    [5, 5],
    [6, 4],
    [7, 3],
    [8, 2],
    [9, 1],
    [10],
    
    Press ENTER to continue.

    Je pense que niveau rapidité et utilisation mémoire, je bats tout le monde pour l'instant. Par contre, niveau longueur de code, c'est pas ça
    Je ne répondrai à aucune question technique en privé

  2. #22
    Rédacteur/Modérateur

    Avatar de gorgonite
    Homme Profil pro
    Ingénieur d'études
    Inscrit en
    décembre 2005
    Messages
    10 223
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 30
    Localisation : France

    Informations professionnelles :
    Activité : Ingénieur d'études
    Secteur : Transports

    Informations forums :
    Inscription : décembre 2005
    Messages : 10 223
    Points : 17 607
    Points
    17 607

    Par défaut

    Citation Envoyé par LLB
    Non, décidément, je n'arrive pas à convenir ma fonction en Caml. Le problème vient de la récursion mutuelle entre le tableau et son initialisation. Même un code aussi simpliste que :
    Code :
    1
    2
    3
    let rec a = Array.init 10 foo
    and foo x = 0;;
    This kind of expression is not allowed as right-hand side of `let rec'
    est refusé. Quelqu'un a une solution (paresseuse et sans faire d'effet de bord) ?
    pourquoi pas cela ?

    Code :
    1
    2
    let foo x = 0;; 
    let a = Array.init 10 foo;;
    Evitez les MP pour les questions techniques... il y a des forums
    Contributions sur DVP : Mes Tutos | Mon Blog

  3. #23
    LLB
    LLB est déconnecté
    Membre Expert
    Inscrit en
    mars 2002
    Messages
    962
    Détails du profil
    Informations forums :
    Inscription : mars 2002
    Messages : 962
    Points : 1 308
    Points
    1 308

    Par défaut

    Oui, mais regarde mon code plus haut. Il faut que a et foo soient mutuellement récursifs : a a besoin de foo pour l'init, et les valeurs stockées dans foo dépendent de a. Apparemment, on ne peut pas s'en sortir sans faire d'effet de bord (on initialise tout le tableau à [[]] et on le met à jour à chaque calcul).


    Citation Envoyé par millie
    Je pense que niveau rapidité et utilisation mémoire, je bats tout le monde pour l'instant. Par contre, niveau longueur de code, c'est pas ça
    Ce serait amusant de comparer pour voir s'il y a une grande différence.

  4. #24
    Rédacteur/Modérateur
    Avatar de Trap D
    Inscrit en
    septembre 2003
    Messages
    4 608
    Détails du profil
    Informations forums :
    Inscription : septembre 2003
    Messages : 4 608
    Points : 5 858
    Points
    5 858

    Par défaut

    Une solution en C itérative :
    Elle est basée sur la décompisition du nombre n en une liste de n 1, et ensuite à partir de cette liste, et des listes obtenues suivantes, on fabrique de nouvelles listes en remplaçant à chaque fois deux nombres de valeurs différentes par leur somme.

    exemple pour 5
    liste intiale [1 1 1 1 1]
    à partir de [1 1 1 1 1 1]
    [2 1 1 1]
    à partir de[2 1 1 1]
    [3 1 1]
    [2 2 1]
    à partir de [3 1 1]
    [4 1]
    [3 2]
    à partir de [2 2 1]
    [4 1] non insérée puisqu'existant déjà
    [3 2] non insérée puisqu'existant déjà
    a partir de [4 1]
    [5]
    à partir de [3 2]
    [5] non inséré puisqu'existant déjà
    à partir de [5]
    Arrêt puisque la longueur est 1

    Code c :
    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
    109
    110
    111
    112
    113
    114
    115
    116
    117
    118
    119
    120
    121
    122
    123
    124
    125
    126
    127
    128
    129
    130
    131
    132
    133
    134
    135
    136
    137
    138
    139
    140
    141
    142
    143
    144
    145
    146
    147
    148
    149
    150
    151
    152
    153
    154
    155
    156
    157
    158
    159
    160
    161
    162
    163
    164
    165
    166
    167
    168
    169
    170
    171
    172
    173
    174
    175
    176
    177
    178
    179
    180
    181
    182
    183
    184
    185
    186
    187
    188
    189
    190
    191
    192
    193
    194
    195
    196
    197
    198
    199
    200
    201
    202
    203
    204
    205
    206
    207
    208
    209
    210
    211
    212
    213
    214
    215
    216
    217
    218
    219
    220
    221
    222
    #include <windows.h>
    #include <stdio.h>
    #include <stdlib.h>
     
    typedef struct une_solution
    {
      int len;
      int *tab;
      struct une_solution *prev;
      struct une_solution *next;
    } une_solution;
     
    typedef struct
    {
       une_solution *tete;
       une_solution *queue;
       une_solution *next;
       int len;
    } les_solutions;
     
    les_solutions tete = {NULL, NULL, NULL, 0};
     
    void nettoie(void)
    {
    	une_solution *ptr = tete.tete;
    	une_solution *tmp;
    	while (ptr != NULL)
    	{
    		tmp = ptr->next;
    		free(ptr->tab);
    		free(ptr);
    		ptr = tmp;
    	}
    	tete.tete = NULL;
    	tete.queue = NULL;
    	tete.next = NULL;
    	tete.len = 0;
    }
     
    void sortie(void)
    {
    	nettoie();
    	exit(EXIT_FAILURE);
    }
     
    une_solution *get_next_solution(void)
    {
    	if (tete.next == NULL)
    		tete.next = tete.tete;
    	else
    		tete.next = tete.next->next;
     
    	return tete.next;
    }
     
    une_solution *cree(int len)
    {
    	une_solution *tmp = malloc(sizeof *tmp);
     
    	if (tmp == NULL)
    	{
    		sortie();
    	}
    	tmp->len = len;
    	tmp->tab = malloc(len * sizeof(int));
    	if (tmp->tab == NULL)
    	{
    		free(tmp);
    		sortie();
    	}
    	tmp->prev = NULL;
    	tmp->next = NULL;
    	return tmp;
    }
     
    int solutions_differentes(une_solution *tmp, une_solution *ptr)
    {
    	int i;
    	for(i = 0; i < ptr->len; i++)
    		if (tmp->tab[i] != ptr->tab[i])
    			return 1;
     
    	return 0;
    }
    void insert_solution(une_solution *ptr)
    {
    	une_solution *tmp;
    	if (tete.tete == NULL)
    	{
    		tete.tete = ptr;
    		tete.queue = ptr;
    		tete.len++;
    	}
    	else
    	{
    		// on insere que si la liste n'existe pas dejà
    		tmp = tete.queue;
    		while (tmp->len == ptr->len && solutions_differentes(tmp, ptr) == 1)
    			tmp = tmp->prev;
     
    		if (tmp->len != ptr->len)
    		{
    			ptr->prev = tete.queue;
    			tete.queue->next = ptr;
    			tete.queue = ptr;
    			tete.len++;
    		}
    	}
    }
     
    une_solution *init(int n)
    {
    	une_solution *ptr = cree(n);
    	int i;
    	for(i = 0; i < n; i++)
    		ptr->tab[i] = 1;
     
    	return ptr;
    }
     
     
    void travail(int n)
    {
    	une_solution *ptr = init(n);
    	une_solution *tmp;
    	int deb ;
    	int next;
    	int old_value;
    	int i,j;
    	int insere;
     
    	insert_solution(ptr);
    	ptr = get_next_solution();
     
    	while (ptr->len > 1)
    	{
    		deb = 0;
    		next = 1;
    		do
    		{
    			tmp = init(ptr->len - 1);
    			// on recopie
    			i = 0; j = 0; insere = 0;
    			while (i < ptr->len)
    			{
    				if (i != deb && i != next)
    				{
    					if (insere == 0 && ptr->tab[i] < ptr->tab[deb] + ptr->tab[next])
    					{
    						insere = 1;
    						tmp->tab[j++] = ptr->tab[deb] + ptr->tab[next];
    					}
     
    					tmp->tab[j++] = ptr->tab[i];
    				}
    				i++;
    			}
    			if (insere == 0)
    				tmp->tab[j++] = ptr->tab[deb] + ptr->tab[next];
     
    			insert_solution(tmp);
     
    			old_value = ptr->tab[next++];
    			while (next < ptr->len && ptr->tab[next] == old_value)
    				next++;
     
    			if (next == ptr->len)
    			{
    				old_value = ptr->tab[deb++];
    				while (deb < ptr->len && ptr->tab[deb] == old_value)
    					deb++;
    				if (deb < ptr->len -1)
    					next = deb + 1;
    			}
    		} while (deb < ptr->len - 1);
    		ptr = get_next_solution();
    	}
    }
     
    void edite_solutions(void)
    {
    	une_solution *ptr = tete.tete;
    	//int i;
     
    	printf("Nombre de solutions %d\n", tete.len);
    /*
    	while(ptr != NULL)
    	{
    		for(i = 0; i < ptr->len; i++)
    			printf("%4d", ptr->tab[i]);
    		puts("");
    		ptr = ptr->next;
    	}
    */
    }
     
     
    int get_nombre(void)
    {
    	int nb;
    	char buf[256];
    	printf("Nombre ");
    	fgets(buf, sizeof buf, stdin);
    	nb = strtol(buf, NULL, 10);
    	return nb;
    }
    int main(int argc, char **argv)
    {
    	int nb;
    	DWORD t1, t2;
     
    	while ((nb = get_nombre()) > 1)
    	{
    		t1 = GetTickCount();
    		travail(nb);
    		edite_solutions();
    		t2 = GetTickCount();
    		printf("Duree %f\n", ((float) (t2 - t1)) / 1000);
    		nettoie();
    	}
    	return 0;
    }
    Les temps de calculs à titre indicatif
    décomposition de 10 : 42 solutions 0,000s
    décomposition de 20 : 627 solutions 0,000s
    décomposition de 30 : 5604 solutions 0,281s
    décomposition de 40 : 37 338 solutions 10,578s
    décomposition de 50 : 204 226 solutions 520,281s
    "La haine seule fait des choix" - Koan Zen
    "Il ne faut pas être meilleur que les autres, il faut être meilleur que soi." Albert Jacquard
    "Ceux qui savent où ils ont posé leur parapluie ne sont pas alcooliques." - pgibonne.
    Faites du Prolog, ça vous changera les idées !
    Ma page Prolog
    Mes codes sources commentés

    Mon avatar : Intérieur avec jeune femme de Vilhelm Hammershoi

  5. #25
    Expert Confirmé Sénior
    Avatar de Jedai
    Homme Profil pro
    Enseignant
    Inscrit en
    avril 2003
    Messages
    6 183
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Côte d'Or (Bourgogne)

    Informations professionnelles :
    Activité : Enseignant

    Informations forums :
    Inscription : avril 2003
    Messages : 6 183
    Points : 8 332
    Points
    8 332

    Par défaut

    Citation Envoyé par LLB
    Ce serait amusant de comparer pour voir s'il y a une grande différence.
    Enorme je pense, en particulier la consommation mémoire est infime dans sa solution puisqu'elle ne conserve qu'une seule liste à la fois en mémoire plutôt que l'ensemble des listes possibles...
    En bref il s'agit d'un algorithme différent des nôtres... Moins lisible et moins naturel bien sûr.
    --
    Jedaï

  6. #26
    Expert Confirmé Sénior
    Avatar de Jedai
    Homme Profil pro
    Enseignant
    Inscrit en
    avril 2003
    Messages
    6 183
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Côte d'Or (Bourgogne)

    Informations professionnelles :
    Activité : Enseignant

    Informations forums :
    Inscription : avril 2003
    Messages : 6 183
    Points : 8 332
    Points
    8 332

    Par défaut

    De même, voici ma solution type "itérateur", avec un unfoldr pour le transformer en liste ! Ce script a une consommation mémoire extrèmement faible évidemment (2 Mo à peu près) :
    Code Haskell :
    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
    module Main where
    import System
    import Data.List
    
    -- fonction générant la liste complète des possibilités
    sums n = first : unfoldr gen first
            where
              first = replicate n 1
              gen prec = do
                x <- genNext n prec
                return (x,x)
    
    -- fonction pour passer d'une possibilité à la suivante
    genNext _ [] = Nothing
    genNext _ (x:[]) = Nothing
    genNext n li = Just $ fst $ aux n li n
        where
          aux k (x:[]) _ = if x == 1 then ([],True) else ([x-1],True)
          aux k (x:xs) m = case aux (k-x) xs x of
                           (nxs,True) -> if x < m 
                                         then ( (x+1):replicate (k-x-1) 1, False )
                                         else ( x:nxs, True )
                           (nxs,False) -> (x:nxs, False)
    
    main = getArgs >>= print . length . sums . read . (!!0)

    --
    Jedaï

  7. #27
    Rédacteur/Modérateur

    Avatar de millie
    Profil pro
    Inscrit en
    juin 2006
    Messages
    6 944
    Détails du profil
    Informations personnelles :
    Localisation : Luxembourg

    Informations forums :
    Inscription : juin 2006
    Messages : 6 944
    Points : 9 773
    Points
    9 773

    Par défaut

    @trap D : Ta solution est super longue. La mienne te bat niveau temps je pense (enfin, faudrait tester sur le même ordinateur et faut que j change les std::cerr en std::cout et que je retire les retours à la ligne (les appels systèmes bouffant énormement de temps) Enfin, ta résolution est particulière

    J'ai quelques optimisations intéressante à ajouter.
    Je ne répondrai à aucune question technique en privé

  8. #28
    Expert Confirmé Sénior
    Avatar de Jedai
    Homme Profil pro
    Enseignant
    Inscrit en
    avril 2003
    Messages
    6 183
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Côte d'Or (Bourgogne)

    Informations professionnelles :
    Activité : Enseignant

    Informations forums :
    Inscription : avril 2003
    Messages : 6 183
    Points : 8 332
    Points
    8 332

    Par défaut

    Citation Envoyé par Trap D
    Les temps de calculs à titre indicatif
    décomposition de 10 : 42 solutions 0,000s
    décomposition de 20 : 627 solutions 0,000s
    décomposition de 30 : 5604 solutions 0,281s
    décomposition de 40 : 37 338 solutions 10,578s (4,42s chez moi)
    décomposition de 50 : 204 226 solutions 520,281s
    Très mauvais semble-t-il... La solution de Millie te bat à plate couture, et même les solutions fonctionnelle font mieux (en tout cas les miennes et celle de Gorgonite). Tu as un problème quelque part, même s'il va falloir que je regarde de plus près ta solution pour le trouver.

    --
    Jedaï

  9. #29
    Rédacteur/Modérateur

    Avatar de gorgonite
    Homme Profil pro
    Ingénieur d'études
    Inscrit en
    décembre 2005
    Messages
    10 223
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 30
    Localisation : France

    Informations professionnelles :
    Activité : Ingénieur d'études
    Secteur : Transports

    Informations forums :
    Inscription : décembre 2005
    Messages : 10 223
    Points : 17 607
    Points
    17 607

    Par défaut

    Citation Envoyé par gorgonite
    pour infos, cela met
    + 19ms pour calculer le résultat pour 21
    + 10s pour 54
    + stack overflow pour 55

    pour infos, ces résultats viennent d'une compilation en bytecode (ocamlc), et non en format natif (ocamlopt)

    pour les résultats en natif (puisque les langages impératifs sont arrivés...)
    + 5ms pour 21
    + 4s pour 54
    + 1min 12s pour 70 (y a plus de stack overflow )

    une version avec mémorisation des listes déjà calculés :
    + n=21 => 2ms
    + n=54 => 657s
    + n=70 => 9s

    en comparaison
    le code c++ de millie donne ceci
    + 9ms pour 21
    + 214ms pour 54
    + 536ms pour 70

    le code c++ de jean-marc bourguet (compilé avec g++ -O2)
    + n=21 => 4 ms
    + n=54 => 92 ms
    + n=70 => 1 s
    + n=100 => 48s

    algo naif en scheme par garulfo (compilé avec bigloo) :
    + 21 => 6ms
    + 54 => 3s
    + 70 => 51s

    le code haskell avec iterateur de jedai (compilé avec ghc)
    + 6ms pour 21
    + 1,6s pour 54
    + 13,8s pour 70

    pour le code haskell de jedai "sans iterateur" (compilé avec ghc)
    + 3ms pour 21
    + 450ms pour 54
    + 5,6s pour 70

    une version faite par alex_pi en ocaml (compilé avec ocamlopt) (solution contestée, ne fait pas la même chose que les autres)
    + n=21 => 3 ms
    + n=54 => 4 ms
    + n=70 => 4 ms
    + n=100 => 6 ms

    pour le code F#, si quelqu'un me trouve un compilateur pour Linux
    pour le code prolog, si quelqu'un sait "lancer" le programme de façon à ce qu'il calcule le nombre de solutions pour N passé en arguments (via la méthode que vous souhaitez), je suis preneur
    pour le code c, étant donné les résultats annoncés, je n'ai pas essayé de les confirmer
    Evitez les MP pour les questions techniques... il y a des forums
    Contributions sur DVP : Mes Tutos | Mon Blog

  10. #30
    Expert Confirmé Sénior
    Avatar de Jedai
    Homme Profil pro
    Enseignant
    Inscrit en
    avril 2003
    Messages
    6 183
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Côte d'Or (Bourgogne)

    Informations professionnelles :
    Activité : Enseignant

    Informations forums :
    Inscription : avril 2003
    Messages : 6 183
    Points : 8 332
    Points
    8 332

    Par défaut

    Citation Envoyé par gorgonite
    pour le code haskell de jedai "sans iterateur", je n'arrive pas à compiler
    Oups, désolé j'avais oublié d'importer les tableaux (Data.Array), c'est corrigé.

    D'ailleurs, dans la droite lignée de la liste infinie pour l'ensemble des n-uplets, voici une liste infinie pour l'ensemble des ensembles :
    Code :
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    module Main where
    import System
    
    main = getArgs >>= print . length . (sums!!) . read . (!!0)
    
    sums = 
        [[]]:
        [[x:xs | 
          x <- [1..n]
         , xs <- if x == n 
                 then [[]]
                 else takeWhile ((<= x) . head) $ sums !! (n - x) ] 
             | n <- [1..]]
    Elle s'avère plus rapide que ma seconde solution, ce qui est sans doute logique puisque cette seconde solution calculait encore certaines listes plusieurs fois (puisque En,m fait partie de En,m+1). On peut encore améliorer la solution, j'y reviendrai.

    --
    Jedaï

  11. #31
    Expert Confirmé Sénior
    Avatar de Jedai
    Homme Profil pro
    Enseignant
    Inscrit en
    avril 2003
    Messages
    6 183
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Côte d'Or (Bourgogne)

    Informations professionnelles :
    Activité : Enseignant

    Informations forums :
    Inscription : avril 2003
    Messages : 6 183
    Points : 8 332
    Points
    8 332

    Par défaut

    Citation Envoyé par gorgonite
    le code haskell avec iterateur de jedai (compilé avec ghc)
    + 6ms pour 21
    + 1,6s pour 54
    + 13,8s pour 70

    pour le code haskell de jedai "sans iterateur" (compilé avec ghc)
    + 3ms pour 21
    + 450ms pour 54
    + 5,6s pour 70
    Je suis un peu surpris par l'ordre des résultat... Comment as-tu compilé, de mon côté avec "ghc -O2 -fglasgow-exts --make le_prog.hs", l'ordre est inversé par rapport à toi.

    --
    Jedaï

  12. #32
    Rédacteur/Modérateur

    Avatar de gorgonite
    Homme Profil pro
    Ingénieur d'études
    Inscrit en
    décembre 2005
    Messages
    10 223
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 30
    Localisation : France

    Informations professionnelles :
    Activité : Ingénieur d'études
    Secteur : Transports

    Informations forums :
    Inscription : décembre 2005
    Messages : 10 223
    Points : 17 607
    Points
    17 607

    Par défaut

    Citation Envoyé par Jedai
    Je suis un peu surpris par l'ordre des résultat... Comment as-tu compilé, de mon côté avec "ghc -O2 -fglasgow-exts --make le_prog.hs", l'ordre est inversé par rapport à toi.

    aucune optimisation... donc en fait, celle par défaut

    avec ton optimisation...

    haskell sans itérateur
    21 0m0.002s
    54 0m0.260s
    70 0m3.108s

    haskell avec iterateur
    21 0m0.002s
    54 0m0.252s
    70 0m3.115s
    Evitez les MP pour les questions techniques... il y a des forums
    Contributions sur DVP : Mes Tutos | Mon Blog

  13. #33
    Rédacteur/Modérateur

    Avatar de millie
    Profil pro
    Inscrit en
    juin 2006
    Messages
    6 944
    Détails du profil
    Informations personnelles :
    Localisation : Luxembourg

    Informations forums :
    Inscription : juin 2006
    Messages : 6 944
    Points : 9 773
    Points
    9 773

    Par défaut

    Ah oui, tu as essayé avec -O3 avec ma version ?

    Il y a des optimisations que je peux ajouter, j'essayerais de les mettre demain soir (ou ce soir si j'ai le temps).
    Je ne répondrai à aucune question technique en privé

  14. #34
    Rédacteur/Modérateur

    Avatar de gorgonite
    Homme Profil pro
    Ingénieur d'études
    Inscrit en
    décembre 2005
    Messages
    10 223
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 30
    Localisation : France

    Informations professionnelles :
    Activité : Ingénieur d'études
    Secteur : Transports

    Informations forums :
    Inscription : décembre 2005
    Messages : 10 223
    Points : 17 607
    Points
    17 607

    Par défaut

    Citation Envoyé par millie
    Ah oui, tu as essayé avec -O3 avec ma version ?

    Il y a des optimisations que je peux ajouter, j'essayerais de les mettre demain soir (ou ce soir si j'ai le temps).

    forcemment, mais dans ce cas, chacun doit refléchir aux options les plus appropriées pour son programme...
    en n'activant aucune optimisation, ça restait "équitable" au sens, que seuls les choix par défaut de chaque compilateur étaient pris en compte

    code c++ millie avec -O3
    21 0m0.002s
    54 0m0.004s
    70 0m0.008s
    Evitez les MP pour les questions techniques... il y a des forums
    Contributions sur DVP : Mes Tutos | Mon Blog

  15. #35
    Expert Confirmé Sénior
    Avatar de Jedai
    Homme Profil pro
    Enseignant
    Inscrit en
    avril 2003
    Messages
    6 183
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Côte d'Or (Bourgogne)

    Informations professionnelles :
    Activité : Enseignant

    Informations forums :
    Inscription : avril 2003
    Messages : 6 183
    Points : 8 332
    Points
    8 332

    Par défaut

    Citation Envoyé par gorgonite
    aucune optimisation... donc en fait, celle par défaut

    avec ton optimisation...

    haskell sans itérateur
    21 0m0.002s
    54 0m0.260s
    70 0m3.108s

    haskell avec iterateur
    21 0m0.002s
    54 0m0.252s
    70 0m3.115s
    Hmmm... Bizarre autant qu'étrange ! Cela dépendrait-il de l'OS ? Sur mon ordinateur la version avec itérateur est presque 2 fois plus rapide à 70. Peut-être aussi une question de version du compilateur ? Quelle version utilises-tu ? De mon côté j'ai la 6.6.1.

    Evidemment le gros avantage de la version avec itérateur c'est l'occupation mémoire : 2 Mo pour 70 (en fait ça ne varie pas vraiment avec n) et 500 Mo dans la version sans itérateur !

    Par ailleurs tu sembles avoir plus de RAM libre que moi, parce que je n'arrive pas à dépasser 64 avec ta version OCaml.



    Citation Envoyé par gorgonite
    en n'activant aucune optimisation, ça restait "équitable" au sens, que seuls les choix par défaut de chaque compilateur étaient pris en compte
    Pas vraiment équitable vu que ocamlopt optimise vraiment son résultat par rapport à un ghc de base. Ce qui m'impressionne toujours avec ocamlopt c'est la vitesse de compilation : c'est instantané sur les petits projets !

    --
    Jedaï

  16. #36
    Rédacteur/Modérateur

    Avatar de gorgonite
    Homme Profil pro
    Ingénieur d'études
    Inscrit en
    décembre 2005
    Messages
    10 223
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 30
    Localisation : France

    Informations professionnelles :
    Activité : Ingénieur d'études
    Secteur : Transports

    Informations forums :
    Inscription : décembre 2005
    Messages : 10 223
    Points : 17 607
    Points
    17 607

    Par défaut

    Citation Envoyé par Jedai
    Peut-être aussi une question de version du compilateur ? Quelle version utilises-tu ? De mon côté j'ai la 6.6.1.

    Code :
    1
    2
    gorgonite@GorgonMobile:~/developpez.com/mes_dev/defis_fonctionnels/01$ ghc --version
    The Glorious Glasgow Haskell Compilation System, version 6.6

    Citation Envoyé par Jedai
    Par ailleurs tu sembles avoir plus de RAM libre que moi, parce que je n'arrive pas à dépasser 64 avec ta version OCaml.
    pas vraiment... juste 2Go

    nb: je n'ai pas fait l'optimisation que tu proposais... j'essaierais mon histoire mutable dès que j'aurais rendu le code plus présentable

    Citation Envoyé par Jedai
    Pas vraiment équitable vu que ocamlopt optimise vraiment son résultat par rapport à un ghc de base. Ce qui m'impressionne toujours avec ocamlopt c'est la vitesse de compilation : c'est instantané sur les petits projets !

    perso, je dirais que c'est le problème de ghc...
    parce qu'il y a aussi pas mal d'optimisations, qui pourrait rendre ocamlopt encore plus agressif
    Evitez les MP pour les questions techniques... il y a des forums
    Contributions sur DVP : Mes Tutos | Mon Blog

  17. #37
    Expert Confirmé Sénior
    Avatar de Jedai
    Homme Profil pro
    Enseignant
    Inscrit en
    avril 2003
    Messages
    6 183
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Côte d'Or (Bourgogne)

    Informations professionnelles :
    Activité : Enseignant

    Informations forums :
    Inscription : avril 2003
    Messages : 6 183
    Points : 8 332
    Points
    8 332

    Par défaut

    Citation Envoyé par gorgonite
    pas vraiment... juste 2Go
    Arf... J'ai 1 Go, dont 600 Mo occupés en permanence par divers autres programmes. Par ailleurs je trouve le comportement des exécutables créés par ocamlopt un peu cavalier : ils plantent tout simplement et sans avertissement s'il n'y a plus de RAM libre ! Au moins Haskell essaie-t-il d'utiliser le disque dur (et rame à mort dans notre cas...).

    Citation Envoyé par gorgonite
    perso, je dirais que c'est le problème de ghc...
    parce qu'il y a aussi pas mal d'optimisations, qui pourrait rendre ocamlopt encore plus agressif
    Oui certes, mais il faut voir que GHC doit gérer tout l'aspect évaluation paresseuse, qu'il est indispensable d'optimiser si on veut avoir des performances un minimum acceptables... Par ailleurs même si ocamlopt est nettement plus rapide, ghc n'est pas particulièrement lent pour ce qu'il fait, on a vu bien pire !

    --
    Jedaï

  18. #38
    Rédacteur/Modérateur

    Avatar de gorgonite
    Homme Profil pro
    Ingénieur d'études
    Inscrit en
    décembre 2005
    Messages
    10 223
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 30
    Localisation : France

    Informations professionnelles :
    Activité : Ingénieur d'études
    Secteur : Transports

    Informations forums :
    Inscription : décembre 2005
    Messages : 10 223
    Points : 17 607
    Points
    17 607

    Par défaut

    Citation Envoyé par Jedai
    ghc n'est pas particulièrement lent pour ce qu'il fait, on a vu bien pire !

    évidemment... si je devais comparer ghc à une machine virtuelle pour un "coreML" basé sur une machine de krivine (déjà fait, donc je peux parler ), il est évident qu'on sent la différence
    Evitez les MP pour les questions techniques... il y a des forums
    Contributions sur DVP : Mes Tutos | Mon Blog

  19. #39
    LLB
    LLB est déconnecté
    Membre Expert
    Inscrit en
    mars 2002
    Messages
    962
    Détails du profil
    Informations forums :
    Inscription : mars 2002
    Messages : 962
    Points : 1 308
    Points
    1 308

    Par défaut

    Citation Envoyé par Jedai
    D'ailleurs, dans la droite lignée de la liste infinie pour l'ensemble des n-uplets, voici une liste infinie pour l'ensemble des ensembles :
    Et la traduction directe en F# :
    Code :
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    let rec sums =
      let get x n =
        if x = n then [[]]
        else List.filter ((>) x << List.head) <| Seq.nth (n - x) sums
      let init n = [for x in 1 .. n ->> [for xs in get x n -> x :: xs]]
      Seq.init_infinite init;;
    
    > sums;;
    val it : seq<int list list>
    = seq [[]; [[1]]; [[1; 1]; [2]]; [[1; 1; 1]; [1; 2]; [3]]; ...]
    Le module Seq est la version lazy du module List.

    pour le code F#, si quelqu'un me trouve un compilateur pour Linux
    Pour avoir essayé plusieurs fois, il tourne bien sous Mono. Par contre, je n'ai plus d'accès ssh sur la machine où j'avais fait mes tests.

    Je viens d'essayer sur une autre machine (qui a une vieille version Mono, et n'a pas F#), en faisant un scp du binaire généré sous Windows. J'ai comparé ta version Caml compilée avec ocamlopt et celle compilée par f#... ben, ocamlopt va bien plus vite (un facteur 10 sur les petits tests ; j'ai pas pu monter haut, la ram est très limitée ). Ca peut se comprendre, j'ai dû compiler pour .NET 1.1, sans les generics (ce qui ralentit beaucoup).

    J'ai voulu tester ma version avec la matrice lazy, mais le compilateur ne peut compiler ce code que pour .NET >= 2. :/


    Bon, si quelqu'un peut tester avec des outils convenables, ce serait bien. Sinon, je vais tester sous Windows. J'ai juste à installer un compilateur Caml pour comparer.

  20. #40
    Rédacteur/Modérateur

    Avatar de gorgonite
    Homme Profil pro
    Ingénieur d'études
    Inscrit en
    décembre 2005
    Messages
    10 223
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 30
    Localisation : France

    Informations professionnelles :
    Activité : Ingénieur d'études
    Secteur : Transports

    Informations forums :
    Inscription : décembre 2005
    Messages : 10 223
    Points : 17 607
    Points
    17 607

    Par défaut

    Citation Envoyé par LLB
    Pour avoir essayé plusieurs fois, il tourne bien sous Mono. Par contre, je n'ai plus d'accès ssh sur la machine où j'avais fait mes tests.

    Je viens d'essayer sur une autre machine (qui a une vieille version Mono, et n'a pas F#), en faisant un scp du binaire généré sous Windows. J'ai comparé ta version Caml compilée avec ocamlopt et celle compilée par f#... ben, ocamlopt va bien plus vite (un facteur 10 sur les petits tests ; j'ai pas pu monter haut, la ram est très limitée ). Ca peut se comprendre, j'ai dû compiler pour .NET 1.1, sans les generics (ce qui ralentit beaucoup).

    J'ai voulu tester ma version avec la matrice lazy, mais le compilateur ne peut compiler ce code que pour .NET >= 2. :/


    Bon, si quelqu'un peut tester avec des outils convenables, ce serait bien. Sinon, je vais tester sous Windows. J'ai juste à installer un compilateur Caml pour comparer.

    perso, j'ai mono sous linux, donc si tu me files le lien pour un compilateur F# qui tourne sur mono, je prends aussi
    Evitez les MP pour les questions techniques... il y a des forums
    Contributions sur DVP : Mes Tutos | Mon Blog

Liens sociaux

Règles de messages

  • Vous ne pouvez pas créer de nouvelles discussions
  • Vous ne pouvez pas envoyer des réponses
  • Vous ne pouvez pas envoyer des pièces jointes
  • Vous ne pouvez pas modifier vos messages
  •