Publicité
+ Répondre à la discussion
Page 3 sur 8 PremièrePremière 1234567 ... DernièreDernière
Affichage des résultats 41 à 60 sur 142
  1. #41
    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 263
    Points
    1 263

    Par défaut

    Depuis un mois, il y a un installeur .msi (je suppose qu'on ne peut pas l'utiliser sous Linux). Avant, il y avait un fichier zip avec tout dedans : sources, Makefile, README et même install-mono.sh.

    Je regarde si c'est encore accessible quelque part. Sinon, je l'uploade dans l'après-midi.

  2. #42
    Expert Confirmé Sénior
    Avatar de Jedai
    Homme Profil pro
    Enseignant
    Inscrit en
    avril 2003
    Messages
    6 180
    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 180
    Points : 8 325
    Points
    8 325

    Par défaut

    Citation Envoyé par LLB
    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]]; ...]
    Fait gaffe, dans ta version tu utilises filter() là où j'utilise takeWhile()... Ca ne fait pas la même chose : takeWhile() va s'arrêter dès que la condition n'est plus vraie, filter() va tester tous les éléments de la liste. A l'origine j'utilisais un filter() (ou à peu près) et cette solution était particulièrement lente, même plus lente que la première solution !!
    Par ailleurs, j'ai un petit doute, regarde ce qui se passe pour 4 avec ta fonction.

    --
    Jedaï

  3. #43
    Rédacteur/Modérateur

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

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

    Informations forums :
    Inscription : décembre 2005
    Messages : 10 220
    Points : 17 577
    Points
    17 577

    Par défaut

    reçu, je testerai ce soir... ça complétera les tests


    et pour prolog, personne ne sait comment lancer ce qu'il faut en une ligne de commande avec swi ou gprolog ?
    Evitez les MP pour les questions techniques... il y a des forums
    Contributions sur DVP : Mes Tutos | Mon Blog

  4. #44
    Rédacteur/Modérateur
    Avatar de Trap D
    Inscrit en
    septembre 2003
    Messages
    4 579
    Détails du profil
    Informations forums :
    Inscription : septembre 2003
    Messages : 4 579
    Points : 6 013
    Points
    6 013

    Par défaut

    Citation Envoyé par gorgonite
    reçu, je testerai ce soir... ça complétera les tests


    et pour prolog, personne ne sait comment lancer ce qu'il faut en une ligne de commande avec swi ou gprolog ?
    Salut
    I'm back
    Si c'est pour mon programme naïf en Prolog, tu fais
    time(decomposition(N, L)).
    Je cherche à améliorer la rapidité de mon prog mais de toute façon, la méthode est lente, puisque je pars des listes déjà fabriquées et je dois vérifier avant de mémoriser que la liste n'esite pas déjà.
    Au passage, j'ai corrigé une fuite mémoire
    "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. #45
    Expert Confirmé Sénior
    Avatar de Jedai
    Homme Profil pro
    Enseignant
    Inscrit en
    avril 2003
    Messages
    6 180
    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 180
    Points : 8 325
    Points
    8 325

    Par défaut

    Après petit test de la version F# avec tableau pour mémoization, on utilise 44s pour 70 (avec -O3), contre 5s sur ma machine pour la même version en Haskell.

    --
    Jedaï

  6. #46
    Rédacteur/Modérateur

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

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

    Informations forums :
    Inscription : décembre 2005
    Messages : 10 220
    Points : 17 577
    Points
    17 577

    Par défaut

    Citation Envoyé par Jedai
    Après petit test de la version F# avec tableau pour mémoization, on utilise 44s pour 70 (avec -O3), contre 5s sur ma machine pour la même
    version en Haskell.

    au fait de quelle machine disposes-tu ?

    perso, c'est un portable centrino 1,6Ghz (simple coeur), 2Go Ram sous Linux (le reste n'a pas vraiment d'influence )
    Evitez les MP pour les questions techniques... il y a des forums
    Contributions sur DVP : Mes Tutos | Mon Blog

  7. #47
    Rédacteur/Modérateur

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

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

    Informations forums :
    Inscription : décembre 2005
    Messages : 10 220
    Points : 17 577
    Points
    17 577

    Par défaut

    Citation Envoyé par Trap D
    Si c'est pour mon programme naïf en Prolog, tu fais
    time(decomposition(N, L)).

    ben sur ma machine avec swiprolog, ça donne 140ms pour 15, et stack overflow au-delà...


    Citation Envoyé par Trap D
    Au passage, j'ai corrigé une fuite mémoire
    dans le programme prolog ou c ?
    si c'est le prolog, je veux bien la correction
    Evitez les MP pour les questions techniques... il y a des forums
    Contributions sur DVP : Mes Tutos | Mon Blog

  8. #48
    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 263
    Points
    1 263

    Par défaut

    Citation Envoyé par Jedai
    Fait gaffe, dans ta version tu utilises filter() là où j'utilise takeWhile()...
    Oui, merci !
    Il n'y a pas de takeWhile dans la lib, je l'ai recodée. Et l'erreur, c'était juste dans la comparaison (j'ai pas dû poster la bonne version tout à l'heure).
    Code :
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    let rec takeWhile f = function
      | e::l when f e -> e :: takeWhile f l
      | _ -> []
    let rec sums =
      let get x n =
        if x = n then [[]]
        else Seq.nth (n - x) sums |> Lazy.force |> takeWhile (fun k -> List.hd k <= x)
      let init n = lazy [for x in 1 .. n ->> [for xs in get x n -> x :: xs]]
      Seq.init_infinite init
    
    > Seq.nth 5 sums;;
    val it : int list list
    = [[1; 1; 1; 1; 1]; [2; 1; 1; 1]; [2; 2; 1]; [3; 1; 1]; [3; 2]; [4; 1]; [5]]
    Pour les performances, ça se comprend que Haskell soit meilleur sur l'évaluation paresseuse. T'as testé sous Windows ou Unix ?

    D'après un benchmark, les performances de F# sous Windows sont du même ordre que celles obtenues avec ocamlopt. Je pense donc qu'il est possible d'améliorer le temps (peut-être en utilisant un algo plus "classique", sans le lazy ?)

    Ceux qui ont testé F# ont dû se rendre compte que mon code génère un warning. C'est dû à la récursion dans la définition de la valeur (liste ou tableau), puisque c'est potentiellement risqué (Caml l'interdit). Le warning peut s'enlever avec le flag --no-warn 40.

    EDIT
    J'ai ajouté lazy, c'est un peu mieux. Je viens de me rendre compte qu'il y a un type LazyList dans la lib standard. Je vais tester.

  9. #49
    Expert Confirmé Sénior
    Avatar de Jedai
    Homme Profil pro
    Enseignant
    Inscrit en
    avril 2003
    Messages
    6 180
    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 180
    Points : 8 325
    Points
    8 325

    Par défaut

    Citation Envoyé par LLB
    Pour les performances, ça se comprend que Haskell soit meilleur sur l'évaluation paresseuse. T'as testé sous Windows ou Unix ?
    Sous Windows (XP) avec le dernier F# et .Net2 .

    Je dis tout de suite que OCaml est normalement plus rapide qu'Haskell sur les mêmes algorithmes en général (parce qu'Haskell est paresseux et que ça rajoute un cout réel à toutes les opérations, d'où d'ailleurs l'importance de la qualité du compilateur). Je ne doute pas qu'il soit possible d'écrire un code plus rapide en OCaml ou F# qu'en Haskell, mais nous regardons aussi l'élégance et la facilité de maintenance des programmes (sinon nous pouvons tout de suite jeter l'éponge comme le code de Millie nous l'a montré !). Et j'aime à penser que jusqu'ici, à l'exception peut-être du code "à itérateur" (et encore, comparé au C++ ou au C...), la plupart des programmes fonctionnels restaient élégants et compréhensible, et compact également, ce qui a son importance pour la maintenance.

    --
    Jedaï

  10. #50
    Expert Confirmé Sénior
    Avatar de Jedai
    Homme Profil pro
    Enseignant
    Inscrit en
    avril 2003
    Messages
    6 180
    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 180
    Points : 8 325
    Points
    8 325

    Par défaut

    Citation Envoyé par gorgonite
    au fait de quelle machine disposes-tu ?

    perso, c'est un portable centrino 1,6Ghz (simple coeur), 2Go Ram sous Linux (le reste n'a pas vraiment d'influence )
    Portable avec Pentium M 1.73GHz (simple coeur), 1 GO de Ram sous Windows XP (j'ai tendance à faire tourner beaucoup de programme en parallèle, la RAM est donc bien occupée habituellement, la plupart des tests se sont donc fait avec 450-500 Mo de RAM libre).
    (Il n'est pas vraiment à moi, mais je le squatte régulièrement disons... )

    --
    Jedaï

  11. #51
    Rédacteur/Modérateur

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

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

    Informations forums :
    Inscription : décembre 2005
    Messages : 10 220
    Points : 17 577
    Points
    17 577

    Par défaut

    Citation Envoyé par Jedai
    j'ai tendance à faire tourner beaucoup de programme en parallèle, la RAM est donc bien occupée habituellement, la plupart des tests se sont donc fait avec 450-500 Mo de RAM libre

    perso, sur ma machine aussi... j'ai apache2, mysql, postgresql, nagios, munin, monit, openssh-server, vsftpd, cups ; divers gadgets gnome, des extensions firefox pour "tricher" à des jeux en ligne, etc

    mais il doit bien rester 1Go de dispo
    Evitez les MP pour les questions techniques... il y a des forums
    Contributions sur DVP : Mes Tutos | Mon Blog

  12. #52
    Expert Confirmé Sénior
    Avatar de Jedai
    Homme Profil pro
    Enseignant
    Inscrit en
    avril 2003
    Messages
    6 180
    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 180
    Points : 8 325
    Points
    8 325

    Par défaut

    Citation Envoyé par LLB
    D'après un benchmark, les performances de F# sous Windows sont du même ordre que celles obtenues avec ocamlopt. Je pense donc qu'il est possible d'améliorer le temps (peut-être en utilisant un algo plus "classique", sans le lazy ?)
    Tu devrais peut-être essayer mon algorithme avec itérateur, il n'y a pas vraiment de paresse dedans (sauf le unfoldr, mais le genNext() lui-même est assez strict), et il est plutôt efficace normalement.

    --
    Jedaï

  13. #53
    Expert Confirmé Sénior
    Avatar de Jedai
    Homme Profil pro
    Enseignant
    Inscrit en
    avril 2003
    Messages
    6 180
    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 180
    Points : 8 325
    Points
    8 325

    Par défaut

    Donc pour l'instant, j'ai quelques résultats de bench pour n=64 (ce qui est le maximum que je parviens à atteindre avec le ML de Gorgonite) :
    LLB 1 (F#, algorithme naïf)

    real 1m44s
    ---
    Dividee 1 (algorithme naïf)

    real 0m39.782 s
    ---
    Dividee 3 (générateur)

    real 0m36s
    ---
    LLB 3 (F# avec itérateur)

    real 0m24.212s
    ---
    LLB 2 (F# avec matrice de mémoization paresseuse)

    real 0m14.300s
    ---
    Gorgonite 1 (algorithme de base)

    real 0m11.542s
    ---
    Jedaï 1 (algorithme de base, en Haskell)

    real 0m5.1s
    ---
    Gorgonite 2 (OCaml avec memoization dans une matrice (n+1)x(n+1) )

    real 0m3.7s
    ---
    Dividee 2 (avec memoization)

    real 0m3.12s
    ---
    Jedaï 2 (avec tableau de (0,0) à (n,m)

    real 0m3.09s
    ---
    Jedaï 5 (avec liste infinie)

    real 0m2.1s
    ---
    Jedaï 3 (avec itérateur et unfoldr)

    real 0m1.7s
    ---
    Jedaï 6 (avec itérateur et unfoldr, mais dans le bon sens !)

    real 0m0.62s
    ---
    TrapD 2 (itère, ne mémorise pas)

    real 0m0.486s
    ---
    Millie 2 (itère, ne mémorise pas, mais affiche (redirigé vers >nul bien sûr) -O3, l'algorithme employé a malheureusement été démontré faux depuis ces mesures)

    real 0m0.300s
    J'ai compilé le F# avec -O3, le Haskell avec -O2.
    Je suis en train de corriger les temps pour le F#, dont la première exécution est nettement plus lente que les suivantes. (EDIT : Vous pouvez considérer que c'est fait)

    Pour Jedaï 3 (avec itérateur et unfoldr), j'ai également 14s pour 80, 56s pour 90, contre 0.45s pour 80 et 0.62s pour 90 avec Millie 2 et 5s pour 80 et 19s pour 90 avec TrapD 2. Jedaï 6 améliore un peu les choses avec 4.8s pour 80 et 17.2 s pour 90.

    Pour les version de Dividee, j'ai utilisé Python 2.5.1 et j'ai mesuré séparément chacune des versions de façon à éviter les problèmes d'allocation et de swap. La version 4 de Dividee est par contre impossible à mesurer sur mon ordinateur vu la place qu'elle prend en mémoire.

    --
    Jedaï

  14. #54
    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 263
    Points
    1 263

    Par défaut

    Voilà, je viens de traduire "bêtement" ton itérateur en F#. J'ai même pas essayé de comprendre le fonctionnement, je regarderai ça plus tard.

    En effet, il est plus efficace que les autres que j'ai implémentés.

    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
    #light
    
    let rec sums n =
      let first = List.init n (fun _ -> 1)
      let gen prec =
        match genNext(n, prec) with
         | Some x -> Some (x, x)
         | None -> None
      first :: (Seq.unfold gen first |> Seq.to_list)
    
    and genNext = function
     | _, [] -> None
     | _, [x] -> None
     | n, li -> Some (aux(n, li, n) |> fst)
    
    and aux = function
      | k, [x], _ -> if x = 1 then [], true else [x-1], true
      | k, x::xs, m -> match aux(k-x, xs, x) with
                        | nxs, true -> if x < m
                                       then (x+1) :: List.init (k-x-1) (fun _ -> 1), false
                                       else x::nxs, true
                        | nxs,false -> x::nxs, false
    
    Sys.argv.(1) |> int_of_string |> sums |> List.length |> print_int
    J'avais aussi fait quelques tests sur le principe de la matrice lazy, en utilisant les traits impératifs, mais ça n'apporte quasiment rien.

  15. #55
    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

    J'ai ajouté des optimisations très sympatique qui devraient faire un peu gagner de temps :

    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::cout<<"[";
        for(int i =0; i <list.size()-1; i++)
            std::cout<<list[i]<<", ";
        std::cout<<list[list.size()-1];
     
        std::cout<<"], ";
    }
     
    /*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)
    {
        static std::vector<int> list;
        list.resize(taille);
        for(int i=0; i<taille; i++)
            list[i] = 1;
     
        for(int i=n/taille; i<=n+1-taille; i++)
        {
            int total = 0;
            mettrePremierN(list, i); //somme vaut i>=n+1-taille
                                        //dans la boucle, ça sera au maximum = taille * 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;
    }


    Notamment, la ligne : for(int i=n/taille; i<=n+1-taille; i++)
    qui était avant : for(int i=1; i<=n; i++)

    J'ai également dégagé les allocations dynamiques à chaque boucle avec std::vector.
    Je ne répondrai à aucune question technique en privé

  16. #56
    Rédacteur/Modérateur
    Avatar de Trap D
    Inscrit en
    septembre 2003
    Messages
    4 579
    Détails du profil
    Informations forums :
    Inscription : septembre 2003
    Messages : 4 579
    Points : 6 013
    Points
    6 013

    Par défaut

    J'ai modifié le calcul et sans mémorisation des résultats, voici ce que j'obtiens
    10 : 42 solutions durée 0.000 s
    20 : 627 solutions durée 0.000s
    30 : 5 604 solutions durée 0.000s
    40 : 37 338 solutions durée 0.015 s
    50 : 204 226 solutions durée 0.032 s
    70 : 4 087 968 solutions durée 0.625 s
    80 : 15 796 476 solutions durée 2.610 s
    90 : 56 634 173 solutions durée 9.938 s
    100 : 190 569 292 solutions durée 34.250 s

    Le bon est important entre 90 et 100 je ne sais pas pourquoi.

    [edit] on peut l'expliquer en remarquant que le nombre de décompositions de 100 est 933 fois plus grand que celui de 50, donc la durée est 900 fois plus importante pour 100 que pour 50
    [/edit]

    Le code de la fonction de calcul est très simple, c'est une simple boucle tant que
    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
    void travail(int n)
    {
    	int total = n;
    	int ptcur = n-1;
    	int *tab = malloc(n * sizeof(int));
    	int i;
    	int nb = 0;
    	// initialisation
    	for(i = 0; i < n; i++)
    		tab[i] = 1;
     
    	while (tab[0] != n)
    	{
    		if (total >= n)
    		{
    			if (total == n)
    			{
    				// on a trouve une solution
    				//edit(tab, ptcur);
    				nb++;
    			}
    			// on revient un cran en arrière
    			total -= tab[ptcur];
    			ptcur--;
    			tab[ptcur]++;
    			total ++;
    		}
    		else
    		{
    			ptcur++;
    			tab[ptcur] = tab[ptcur-1];
    			total += tab[ptcur];
    		}
    	}
    	nb++;
    	//edit(tab, 0);
    	printf("Nombre de solutions %d\n", nb);
    	free(tab);
    }
    [edit] correction du nombre de résultats pour 100.
    "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

  17. #57
    Rédacteur/Modérateur
    Avatar de Trap D
    Inscrit en
    septembre 2003
    Messages
    4 579
    Détails du profil
    Informations forums :
    Inscription : septembre 2003
    Messages : 4 579
    Points : 6 013
    Points
    6 013

    Par défaut

    En modifiant légèrement le code et en choisisssant les options de compilation pour optimiser la vitesse, (/O2) j'obtiens
    pour 50 : 0.016 s
    pour 70 : 0.250 s
    pour 80 : 1.016 s
    pour 90 : 3.781 s
    pour 100 : 13.104 s (soit une durée divisée par près de 3).

    le code :
    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
    38
    39
    40
    41
    42
    43
    44
    45
    void travail(int n)
    {
    	int total = n;
    	int ptcur = n-1;
    	int i;
    	int nb = 0;
    	int *tab = malloc(n * sizeof(int));
    	// initialisation
    	for(i = 0; i < n; i++)
    		tab[i] = 1;
    
    	while (tab[0] != n)
    	{
    		if (total > n)
    		{
    			// on revient un cran en arrière
    			total -= tab[ptcur];
    			--ptcur;
    			++tab[ptcur];
    			++total;
    		}
    		else
    		if (total == n)
    		{
    			// on a trouve une solution
    			//edit(tab, ptcur);
    			++nb;
    			// on revient un cran en arrière
    			total -= tab[ptcur];
    			--ptcur;
    			++tab[ptcur];
    			++total;
    		}
    		else
    		{
    			++ptcur;
    			tab[ptcur] = tab[ptcur-1];
    			total += tab[ptcur];
    		}
    	}
    	nb++;
    	//edit(tab, 0);
    	printf("Nombre de solutions %d\n", nb);
    	free(tab);
    }
    "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

  18. #58
    Membre Expert
    Homme Profil pro
    Inscrit en
    mars 2007
    Messages
    895
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : Belgique

    Informations forums :
    Inscription : mars 2007
    Messages : 895
    Points : 1 300
    Points
    1 300

    Par défaut

    Personne n'a encore posté de version Python alors voilà:

    sums1 = algorithme de base (celui de LLB)
    sums2 = version avec mémoization
    sums3 = un générateur (un peu comme une version lazy)
    sums4 = version non récursive; programmation dynamique

    Les temps que j'obtiens sur mon T2400 @ 1.83 Ghz:
    sums1(64): 36 s
    sums2(64): 2.5 s
    sums3(64): 34 s
    sums4(64): 8.7 s

    Au niveau de l'utilisation mémoire, je n'ai pas fait de mesure précise, mais en gros sums4 demande plus de 1,2 GB de mémoire (!); sums2 environ 600 MB, sums1 200 MB, et sums3 est bien sur la plus économique, son utilisation mémoire ne dépendant que de la profondeur de la pile d'appels (tant qu'on n'a pas besoin de toutes les combinaisons en même temps).

    Je suis étonné que la version 4 (prog.dyn.) utilise deux fois plus de mémoire et est plus lent que la mémoization; j'ai pourtant essayé de ne générer que les combinaisons qui seront utilisées. Il y a certainement moyen de faire mieux.

    Code python :
    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
     
    # version de base
    def sums1(n):
      def sumrec(n,m):
        if n == 0: return [()]
        else:
          return [(i,)+j for i in xrange(1,min(m,n)+1) for j in sumrec(n-i,i)]
      return sumrec(n,n)
     
    # avec mémoization
    def memoize(f):
      mem={}
      def memo(*args):
        if args not in mem:
          mem[args] = f(*args)
        return mem[args]
      return memo
     
    def sums2(n):
      @memoize
      def sumrec(n,m):
        if n == 0: return [()]
        else:
          return [(i,)+j for i in xrange(1,m+1) for j in sumrec(n-i,min(i,n-i))]
      return sumrec(n,n)
     
    # avec un générateur
    def sums3(n):
      def sumrec(n,m):
        if n == 0: yield ()
        else:
          for i in xrange(1,min(m,n)+1):
            for j in sumrec(n-i,i): yield (i,)+j
      return sumrec(n,n)
     
    # version plus impérative (?)
    def sums4(nn):
      mem = {(0,0): [()]}
      for n in xrange(1,nn):
        for m in xrange(1,min(n,nn-n)+1):
          mem[(n,m)] = [(i,)+j for i in xrange(1,m+1) for j in mem[(n-i,min(i,n-i))]]
      return [(i,)+j for i in xrange(1,nn+1) for j in mem[(nn-i,min(i,nn-i))]]
     
    import timeit
    print "sums1",
    print timeit.Timer("sums1(64)","from __main__ import sums1").timeit(1)
    print "sums2",
    print timeit.Timer("sums2(64)","from __main__ import sums2").timeit(1)
    print "sums3",
    print timeit.Timer("for x in sums3(64): pass","from __main__ import sums3").timeit(1)
    print "sums4",
    print timeit.Timer("sums4(64)","from __main__ import sums4").timeit(1)

  19. #59
    Expert Confirmé Sénior
    Avatar de Jedai
    Homme Profil pro
    Enseignant
    Inscrit en
    avril 2003
    Messages
    6 180
    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 180
    Points : 8 325
    Points
    8 325

    Par défaut

    Bon, je pense qu'on peut encore améliorer la mémoization avec liste infinie, mais en attendant voici le programme le plus rapide que j'ai créé pour l'instant, sur le principe de l'itérateur, mais meilleur que le précédent en cela qu'on n'a pas besoin de lire toute la liste à tous les coups car je donne les possibilités sous forme de n-uplet ascendant ce coup-ci :
    Code :
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    module Main where
    import System
    import Data.List
    
    -- fonction générant la liste complète des possibilités
    sums n = first : unfoldr (maybe Nothing (\x -> Just (x,x)) . genNext) first
        where first = replicate n 1
    
    -- fonction pour passer d'une possibilité à la suivante
    genNext [] = Nothing
    genNext (x:[]) = Nothing
    genNext li = Just $ aux 0 li
        where
          aux 0 (x:xs) = aux x xs
          aux n li@(x:y:xs) = if y > x
                              then replicate (n-1) 1 ++ (x+1 : tail li)
                              else aux (n+x) $ tail li
          aux n li@(x:[]) = replicate (n-1) 1 ++ [x+1]
    
    main = getArgs >>= print . length . sums . read . (!!0)
    Vous pouvez vous référer à mon post de bench pour constater que cette version est vraiment rapide...

    --
    Jedaï

  20. #60
    Expert Confirmé Sénior
    Avatar de Jedai
    Homme Profil pro
    Enseignant
    Inscrit en
    avril 2003
    Messages
    6 180
    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 180
    Points : 8 325
    Points
    8 325

    Par défaut

    Citation Envoyé par LLB
    Voilà, je viens de traduire "bêtement" ton itérateur en F#. J'ai même pas essayé de comprendre le fonctionnement, je regarderai ça plus tard.

    En effet, il est plus efficace que les autres que j'ai implémentés.
    Pas selon mes tests... D'un autre côté mes tests ont révélé que le compilateur F# n'effectuait pas proprement la fusion du length et du unfold, ce qui signifie que tu perds l'avantage en place mémoire que te conférait l'itérateur. Essaie de compter les possibilités "à la main" plutôt qu'avec length . unfold.

    --
    Jedaï

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
  •