Publicité
+ Répondre à la discussion
Page 6 sur 8 PremièrePremière ... 2345678 DernièreDernière
Affichage des résultats 101 à 120 sur 142
  1. #101
    Rédacteur/Modérateur

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

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

    Informations forums :
    Inscription : décembre 2005
    Messages : 10 194
    Points : 16 749
    Points
    16 749

    Par défaut

    tout a l'air de bien fonctionner

    les performances (g++ avec option -O2)
    + n=21 => 4 ms
    + n=54 => 92 ms
    + n=70 => 1 s
    + n=100 => 48s





    pour infos, nous allons faire un récapitulatif avec les codes et les perfs...
    temporairement, ce post de benchmarks peut vous donner une idée...
    Evitez les MP pour les questions techniques... il y a des forums
    Contributions sur DVP : Mes Tutos | Mon Blog

  2. #102
    Rédacteur/Modérateur

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

    Informations forums :
    Inscription : juin 2006
    Messages : 6 939
    Points : 8 757
    Points
    8 757

    Par défaut

    Ok, ma version a en fait toujours été buggué... Mon idée de départ était fausse



    J'ai corrigé, mais les performances tombent un peu... Faut que je parte à la recherche d'une nouvelle idée.


    Snif snif, les langages fonctionnels reprennent la tête


    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
    #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<<"], "<<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]++;
            for(pos=currentMax+1; pos<list.size(); pos++)
                list[pos] = 1;
        }
    }
     
    /*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(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()
    {
    /*    std::vector<int> list;
        list.push_back(4);
        list.push_back(1);
        list.push_back(1);
     
        for(int i=0; i<4; i++) {
         genererSuivant(list);
         afficher(list);
        }*/
     
        generationSomme(100);
     
        return 0;
    }
    Je ne répondrai à aucune question technique en privé

  3. #103
    Invité régulier
    Inscrit en
    juin 2007
    Messages
    6
    Détails du profil
    Informations forums :
    Inscription : juin 2007
    Messages : 6
    Points : 6
    Points
    6

    Par défaut

    Citation Envoyé par alex_pi
    Mais pourquoi personne n'aime mon code :'(
    Parce que tu n'as pas expliqué ce qu'il fait ni comment il marche. Ca pourrait être le code le plus génial du monde, s'il laisse l'impression qu'il ne répond pas à la question et que tu ne fais rien pour nous aider à comprendre, il aura peu de succès... Les perfs annoncées sont brillantes et un peu incroyables, à toi de nous faire passer le message.

    Je ne suis pas juste pénible par plaisir, c'est une question fondamentale quand on développe du code : faire en sorte que ceux qui l'utilisent aient confiance.

  4. #104
    Expert Confirmé Sénior

    Inscrit en
    novembre 2005
    Messages
    5 104
    Détails du profil
    Informations forums :
    Inscription : novembre 2005
    Messages : 5 104
    Points : 5 985
    Points
    5 985

    Par défaut

    Citation Envoyé par strate
    Parce que tu n'as pas expliqué ce qu'il fait ni comment il marche.
    Il construit un DAG dont les chemins de la racine aux feuilles sont les solutions. Les autres propositions generent toutes les solutions (soit en les conservant, soit en ne le faisant pas), ce qui est different.

    Si on ajoute le parcours des chemins, sa solution n'est pas tellement (ou meme pas du tout?) meilleure. En fait on peut meme dire que les autres solutions parcourent aussi le meme DAG sans prendre la peine de le construire.


    Autre proposition en C++ -- qui itere toujours sur toutes les solutions --, en utilisant une representation qui comprime les 1 finaux. On peut pousser cette idee plus loin en utilisant du RLE pour tous les elements ou une representation des comptes (donc avec beaucoup de 0, ca ne va vraissemblablement pas apporter grand chose).

    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
     
    void consume(std::vector<long> const& tab, int trailing1s) {
    #ifdef COUNT_ONLY
      ++solutions;
    #else
      if (!tab.empty()) {
          std::cout << tab[0];
          for (std::vector<long>::size_type i = 1; i < tab.size(); ++i)
          {
              std::cout << ", " << tab[i];
          }  
      } else {
          std::cout << '1';
          --trailing1s;
      }
      while (trailing1s != 0) {
          std::cout << ", 1";
          --trailing1s;
      }
      std::cout << '\n';
    #endif
    }
     
    void generate(long val)
    {
        std::vector<long> result;
        result.reserve(val);
        result.push_back(val);
        long remainder = 0;
        consume(result, remainder);
        while (!result.empty()) {
            long last = result.back();
            result.pop_back();
            remainder += last;
            --last;
            if (last != 1) {
                while (remainder >= last) {
                    result.push_back(last);
                    remainder -= last;
                }
                if (remainder > 1) {
                    result.push_back(remainder);
                    remainder = 0;
                }
            }
            consume(result, remainder);
        }
    }
    Les MP ne sont pas là pour les questions techniques, les forums sont là pour ça.

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

    Par défaut

    Citation Envoyé par gorgonite
    temporairement, ce post peut vous donner une idée... http://www.developpez.net/forums/sho...4&postcount=29
    Tu aurais du corriger pour le code C, après vérification, il me semble qu'il arrive assez bien placé (version 2 avec optimisation de vitesse)
    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
    PS : J'ai ajouté le programme C, c'est du windows à cause de GetTickCount().
    Fichiers attachés Fichiers attachés
    • Type de fichier : c defi.c (1,2 Ko, 5 affichages)
    "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

  6. #106
    Rédacteur/Modérateur
    Avatar de Trap D
    Inscrit en
    septembre 2003
    Messages
    4 559
    Détails du profil
    Informations forums :
    Inscription : septembre 2003
    Messages : 4 559
    Points : 5 478
    Points
    5 478

    Par défaut

    Citation Envoyé par alex_pi
    Et pour n = 100, il retourne 122072 solution alors qu'il y en a 2300165032574323995027.
    Non, pour n = 100, le nombre de décomposition est 190 569 292
    voir ici
    "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

  7. #107
    Expert Confirmé Sénior
    Avatar de Jedai
    Homme Profil pro
    Enseignant
    Inscrit en
    avril 2003
    Messages
    6 164
    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 164
    Points : 7 656
    Points
    7 656

    Par défaut

    Je rajoute une implémentation en Haskell, elle n'est pas destinée à être rapide (ce qu'elle n'est pas vraiment, enfin elle doit être au niveau des codes OCaml de Gorgonite à peu près), mais elle est belle (de mon point de vue ) :
    Code :
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    import System
    
    combinations = foldl (\without p ->
                              let (poor,rich) = splitAt p without
                                  with = poor ++ 
                                         zipWith (++) (map (map (p:)) with)
                                                      rich
                              in with
                         ) ([[]] : repeat [])
    
    main = do
      args <- getArgs
      let n = read $ args !! 0
      print . length $ combinations [1..n] !! n
    Néanmoins elle emploie à plein l'évaluation paresseuse et fait usage d'une valeur récursive et infinie pour faire de la programmation dynamique !

    De plus sa portée est plus générale que la plupart des programmes présents ici car elle permet d'entrer une liste d'entiers utilisables, elle résout de façon très élégante et très efficace le problème du menu (que pouvez vous vous acheter à la carte pour une somme donnée ?) (plus connu sous le nom de knapsack).

    (Malheureusement la solution n'est pas de moi, je reproduis de mémoire une fonction dont j'ai vu la définition sur une mailing-list en réponse à ce webcomic (très fun pour les informaticiens par ailleurs))

    --
    Jedaï

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

    Par défaut

    Je rappelle que ce post fournit une comparaison de la plupart des programmes présentés dans ce sujet.
    Les tests ont été fait sous Windows XP, un pentium M 1.73Mhz, 1Go de RAM (dont 400Mo occupés).

    --
    Jedaï

  9. #109
    Membre chevronné Avatar de HanLee
    Profil pro
    Inscrit en
    mai 2004
    Messages
    738
    Détails du profil
    Informations personnelles :
    Âge : 27
    Localisation : France, Rhône (Rhône Alpes)

    Informations forums :
    Inscription : mai 2004
    Messages : 738
    Points : 770
    Points
    770

    Par défaut

    Citation Envoyé par Jedai Voir le message
    (Malheureusement la solution n'est pas de moi, je reproduis de mémoire une fonction dont j'ai vu la définition sur une mailing-list en réponse à ce webcomic (très fun pour les informaticiens par ailleurs))

    --
    Jedaï
    (je sais, j'ai pas de proposition sous la main... J'vais peut-être en donner plus tard)

  10. #110
    Membre confirmé Avatar de Steki-kun
    Profil pro
    Inscrit en
    janvier 2005
    Messages
    222
    Détails du profil
    Informations personnelles :
    Âge : 31
    Localisation : France, Paris (Île de France)

    Informations forums :
    Inscription : janvier 2005
    Messages : 222
    Points : 255
    Points
    255

    Par défaut

    Coucou tout le monde, je savais pas quoi faire cette apres-midi alors j'ai essayé de faire la mienne. En OCaml (très impur mais mon but n'était pas de le faire pur ) avec tableaux : je fais que parcourir toutes les solutions sans les garder en mémoire. Elles sont calculées dans l'ordre lexicographique inverse selon l'algo donné dans TAOCP.

    Pour l'appeler : ./partP -n 64, ajouter -debug pour voir toutes les solutions et leur nombre, et si vous rediriger vers /dev/null il vous donnera quand même le nombre de solutions sur la sortie err.

    Compilé avec ocamlopt -unsafe (mais le -unsafe m'a quasimment rien fait gagner) :

    Code :
    1
    2
    3
    4
    5
    6
    7
    8
    ...@...:.../Partitions$ time ./partP -n 32
    real	0m0.005s user	0m0.000s sys	0m0.000s
    
    ...@...:.../Partitions$ time ./partP -n 64
    real	0m0.065s user	0m0.056s sys	0m0.004s
    
    ...@...:.../Partitions$ time ./partP -n 100
    real	0m2.610s user	0m2.608s sys	0m0.000s
    Je sais que time c'est pas la panacée pour faire des benchs mais j'en ai fait plusieurs et j'ai pris un "moyen", ça donne une idée.

    Le code OCaml :
    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
    46
    47
    48
    49
    50
    51
    52
    53
    54
    let debug = ref false
    let sol = ref 0
    
    let visit a m = 
      incr sol;
      for i = 1 to m-1 do
        Printf.printf "%d+" a.(i)
      done;
      print_endline (string_of_int a.(m))
    
    let rec copy_loop a n m x =
      if n <= x then n, m
      else 
        (a.(m) <- x;
         copy_loop a (n-x) (m+1) x)
    
    let rec main_loop a n m q =
      if !debug then visit a m;
      if a.(q) = 2 then
        (a.(q) <- 1;
         a.(m+1) <- 1;
         main_loop a n (m+1) (q-1))
      else
        if q = 0 then ()
        else
          begin
    	let x = a.(q) - 1 in 
    	  a.(q) <- x;
    	  let n,m = copy_loop a (m-q+1) (q+1) x in
    	    a.(m) <- n;
    	    main_loop a n m (m - (if n=1 then 1 else 0))
          end
    
          
    let main n =
      if n < 1 then raise (Invalid_argument "n should be positive");
      let a = Array.make (n+1) 0 in
        a.(1) <- n;
        main_loop a n 1 (if n = 1 then 0 else 1)
    
    let usage = 
      Printf.sprintf 
        "%s <n> <t>\n  Generates all partitions of n\n"
        (Sys.argv.(0))
    
    let n = ref 0
    let _ = 
      Arg.parse [("-debug", Arg.Set debug, "prints each partition");
    	     ("-n", Arg.Set_int n, "integer to partition")]
        (fun s -> print_endline usage)
        usage;
      main !n;
      if !debug then 
        Printf.eprintf "Number of solutions visited : %d\n" !sol
    I'm the kind of guy that until it happens, I won't worry about it. - R.H. RoY05, MVP06

  11. #111
    yan
    yan est déconnecté
    Rédacteur
    Avatar de yan
    Homme Profil pro yan verdavaine
    Ingénieur expert
    Inscrit en
    mars 2004
    Messages
    9 961
    Détails du profil
    Informations personnelles :
    Nom : Homme yan verdavaine
    Âge : 32
    Localisation : France, Ille et Vilaine (Bretagne)

    Informations professionnelles :
    Activité : Ingénieur expert
    Secteur : High Tech - Multimédia et Internet

    Informations forums :
    Inscription : mars 2004
    Messages : 9 961
    Points : 12 421
    Points
    12 421

    Par défaut

    Bonjour,
    en regardant le code millie
    http://www.developpez.net/forums/sho...0&postcount=55
    j'ai vue qu'il y avait encore une optimisation a faire. Et pour tester je l'ai refait en utilisant la STL.
    Grosse déception, c'est moins rapide sous GCC même sans rajouter l'optimisation :
    Code :
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    void genererSuivant(std::vector<int> & list)
    {
    //diminue le nombre de test 
      for(pos=list.size()-2;pos>= 0 && list[pos+1]>= list[pos]; pos--);
    
        if(list[pos+1]< list[pos])
            list[pos+1]++;
        else
             list[0]++;
    }


    le voila avec la STL
    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
     
    #include <iostream>
    #include <vector>
    #include <algorithm>
    #include <iterator>
    #include <numeric>
    #include <ctime>
     
     
    /*affiche un vecteur*/
    void afficherMongaulois(const std::vector<int> & list)
    {
        std::cout<<"[";
        std::copy(list.begin(),list.end()-1,std::ostream_iterator<int>(std::cout,", "));
        std::cout<< *list.rbegin()<<"]\n ";
    }
     
    /*calcul la somme d'un vecteur*/
    int sommeMongaulois(const std::vector<int> & list)
    {
        return std::accumulate(list.begin(),list.end(),0);
    }
     
    /*met tout le vecteur à 1 sauf le premier élément à n*/
    void mettrePremierNMongaulois(std::vector<int> & list,const int &n)
    {
        list[0] = n;
        std::fill(list.begin()+1,list.end(),1);
    }
     
    /*genère la combinaison suivante suivant un critère très particulier*/
    void genererSuivantMongaulois(std::vector<int> & list)
        {
         std::vector<int>::reverse_iterator it = std::adjacent_find( list.rbegin(), list.rend(),std::less<int>());
     
        if(list.rend()!=it)
            (*it)++;
        else
            (*list.begin())++;
        }
     
    /*génère l'ensemble des solutions dont la taille du vecteur vaut taille*/
    void generationSolutionMongaulois(int n, int taille)
    {
        static std::vector<int> list;
        list.resize(taille);
        std::fill(list.begin(),list.end(),1);
     
     
        for(int i=n/taille; i<=n+1-taille; i++)
        {
            int total = 0;
            mettrePremierNMongaulois(list, i); //somme vaut i>=n+1-taille
                                        //dans la boucle, ça sera au maximum = taille * i
            while(total<=n && list[0]==i)
            {
                total = sommeMongaulois(list);
                if(total == n)
                    afficherMongaulois(list);
                if(total >=n)
                    break;
                genererSuivantMongaulois(list);
            }
        }
     
    }
     
    /*génère l'ensemble des solutions*/
    void generationSommeMongaulois(int n)
    {
        for(int taille = n; taille>0; taille--)
            generationSolutionMongaulois(n, taille);
    }
     
    int main(int argc,char ** argv)
    {
        int nb = 100;
     
        generationSommeMongaulois(nb);
        return 0;
    }
    Es ce que quelqu'un pourrai tester pour vérifier les résultat?
    merci
    Développeur Windows 8, Windows phone 8 et Nokia Asha, inscrivez vous sur DVLUP

  12. #112
    Rédacteur/Modérateur

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

    Informations forums :
    Inscription : juin 2006
    Messages : 6 939
    Points : 8 757
    Points
    8 757

    Par défaut

    En fait, mon code est faux, il me manque des parties

    En tout cas, ce qui est sûr, c'est que ma solution où j'étais partie sera peut être au final plus rapide, mais j'ai passé un maximum de temps à résoudre le problème en amont alors que les solutions de bases fonctionnels laissent tout le travail au programme.
    Mais il doit y avoir des versions fonctionnels plus réfléchies, faudrait que je relise les quelques pages.
    Je ne répondrai à aucune question technique en privé

  13. #113
    Membre confirmé Avatar de Steki-kun
    Profil pro
    Inscrit en
    janvier 2005
    Messages
    222
    Détails du profil
    Informations personnelles :
    Âge : 31
    Localisation : France, Paris (Île de France)

    Informations forums :
    Inscription : janvier 2005
    Messages : 222
    Points : 255
    Points
    255

    Par défaut

    Euh, la mienne est très réfléchie ! Je peux la réécrire en fonctionnel pur et elle reste tout à fait réfléchie : en remplaçant le tableau de taille constante sur lequel l'algo travaille par une liste de couples (n,k) représentant de manière condensée la partition où k est présent n fois, et en les générant à l'envers pour profiter d'un meilleur sharing (les petits facteurs de la partition changent souvent sans que les gros ne changent). C'est forcément plus lent que l'autre à cause des allocations et des copies en plus, mais ça reste efficace.
    ...:~/.../Partitions$ time ./partPpur -n 32
    user 0m0.000s

    ...:~/.../Partitions$ time ./partPpur -n 64
    user 0m0.108s

    ...:~/.../Partitions$ time ./partPpur -n 100
    user 0m5.236s
    Voilà le code, la boucle principale en gras :

    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
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    open Int64
    
    let debug = ref false
    let sol = ref zero
    
    let rec visit = function
        [] -> assert false
      | [(ck,ak)] -> 
          sol := add !sol one;
          let sk = string_of_int ak in
          let skp = sk^"+" in
    	for i = 1 to (ck-1) do 
    	  print_string skp;
    	done; print_endline sk
      | (ck,ak)::q -> 
          let sk = string_of_int ak in
          let skp = sk^"+" in
    	for i = 1 to ck do 
    	  print_string skp;
    	done; visit q
    
    let rec main_loop n l =
      if !debug then visit (List.rev l);
      match l with
        | [] -> assert false
        | [(_,1)] -> ()
        | (ck,1)::(dk, 2)::q -> 
    	let q' = if dk=1 then q else (dk-1,2)::q in
    	  main_loop n ((ck+2,1)::q')
        | (ck,1)::(dk, ak)::q -> 
    	let x = ak-1 in
    	let q' = if dk=1 then q else (dk-1,ak)::q in
    	let quot = (ck+1)/x in
    	let r = (ck+1)-x*quot in
    	  main_loop n 
    	    (if r = 0 then
    	       (quot+1,x)::q'
    	     else
    	       (1,r)::(quot+1,x)::q')	    
        | (dk,2)::q ->
    	let q' = if dk=1 then q else (dk-1,2)::q in
    	  main_loop n ((2,1)::q')
        | (dk,ak)::q ->
    	let q' = if dk=1 then q else (dk-1,ak)::q in
    	  main_loop n ((1,1)::(1,ak-1)::q')
          
    let main n =
      if n < 1 then raise (Invalid_argument "n should be positive");
      main_loop n [(1,n)]
    
    let usage = 
      Printf.sprintf 
        "%s <n> <t>\n  Generates all partitions of n\n"
        (Sys.argv.(0))
    
    let n = ref 0
    let _ = 
      Arg.parse [("-debug", Arg.Set debug, "prints each partition");
    	     ("-n", Arg.Set_int n, "integer to partition")]
        (fun s -> print_endline usage)
        usage;
      main !n;
      if !debug then Printf.eprintf "Number of solutions visited : %s\n" (to_string !sol)
    Il y a de la duplication dans le matching, c'est pour traiter efficacement le cas simple et très fréquent où la partition est de la forme n = .. + ... + 2 + 1 + 1 + 1 ... + 1.
    I'm the kind of guy that until it happens, I won't worry about it. - R.H. RoY05, MVP06

  14. #114
    yan
    yan est déconnecté
    Rédacteur
    Avatar de yan
    Homme Profil pro yan verdavaine
    Ingénieur expert
    Inscrit en
    mars 2004
    Messages
    9 961
    Détails du profil
    Informations personnelles :
    Nom : Homme yan verdavaine
    Âge : 32
    Localisation : France, Ille et Vilaine (Bretagne)

    Informations professionnelles :
    Activité : Ingénieur expert
    Secteur : High Tech - Multimédia et Internet

    Informations forums :
    Inscription : mars 2004
    Messages : 9 961
    Points : 12 421
    Points
    12 421

    Par défaut

    Citation Envoyé par millie Voir le message
    En fait, mon code est faux, il me manque des parties

    En tout cas, ce qui est sûr, c'est que ma solution où j'étais partie sera peut être au final plus rapide, mais j'ai passé un maximum de temps à résoudre le problème en amont alors que les solutions de bases fonctionnels laissent tout le travail au programme.
    Mais il doit y avoir des versions fonctionnels plus réfléchies, faudrait que je relise les quelques pages.
    ha ok.
    J'ai pas du voir où c'était ecrit...
    Ben tans pis (c'était surtout pour voir comment le réécrire avec la STL et verifier que c'etait plus, ou au moins aussi, rapide... ).
    Il y as juste les versions fonctionnelle qui sont correcte?
    Développeur Windows 8, Windows phone 8 et Nokia Asha, inscrivez vous sur DVLUP

  15. #115
    Rédacteur/Modérateur

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

    Informations forums :
    Inscription : juin 2006
    Messages : 6 939
    Points : 8 757
    Points
    8 757

    Par défaut

    Citation Envoyé par Steki-kun Voir le message
    Euh, la mienne est très réfléchie ! Je peux la réécrire en fonctionnel pur et elle reste tout à fait réfléchie : en remplaçant le tableau de taille constante sur lequel l'algo travaille par une liste de couples (n,k) représentant de manière condensée la partition où k est présent n fois, et en les générant à l'envers pour profiter d'un meilleur sharing (les petits facteurs de la partition changent souvent sans que les gros ne changent). C'est forcément plus lent que l'autre à cause des allocations et des copies en plus, mais ça reste efficace.


    Voilà le code, la boucle principale en gras :

    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
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    open Int64
    
    let debug = ref false
    let sol = ref zero
    
    let rec visit = function
        [] -> assert false
      | [(ck,ak)] -> 
          sol := add !sol one;
          let sk = string_of_int ak in
          let skp = sk^"+" in
    	for i = 1 to (ck-1) do 
    	  print_string skp;
    	done; print_endline sk
      | (ck,ak)::q -> 
          let sk = string_of_int ak in
          let skp = sk^"+" in
    	for i = 1 to ck do 
    	  print_string skp;
    	done; visit q
    
    let rec main_loop n l =
      if !debug then visit (List.rev l);
      match l with
        | [] -> assert false
        | [(_,1)] -> ()
        | (ck,1)::(dk, 2)::q -> 
    	let q' = if dk=1 then q else (dk-1,2)::q in
    	  main_loop n ((ck+2,1)::q')
        | (ck,1)::(dk, ak)::q -> 
    	let x = ak-1 in
    	let q' = if dk=1 then q else (dk-1,ak)::q in
    	let quot = (ck+1)/x in
    	let r = (ck+1)-x*quot in
    	  main_loop n 
    	    (if r = 0 then
    	       (quot+1,x)::q'
    	     else
    	       (1,r)::(quot+1,x)::q')	    
        | (dk,2)::q ->
    	let q' = if dk=1 then q else (dk-1,2)::q in
    	  main_loop n ((2,1)::q')
        | (dk,ak)::q ->
    	let q' = if dk=1 then q else (dk-1,ak)::q in
    	  main_loop n ((1,1)::(1,ak-1)::q')
          
    let main n =
      if n < 1 then raise (Invalid_argument "n should be positive");
      main_loop n [(1,n)]
    
    let usage = 
      Printf.sprintf 
        "%s <n> <t>\n  Generates all partitions of n\n"
        (Sys.argv.(0))
    
    let n = ref 0
    let _ = 
      Arg.parse [("-debug", Arg.Set debug, "prints each partition");
    	     ("-n", Arg.Set_int n, "integer to partition")]
        (fun s -> print_endline usage)
        usage;
      main !n;
      if !debug then Printf.eprintf "Number of solutions visited : %s\n" (to_string !sol)
    Il y a de la duplication dans le matching, c'est pour traiter efficacement le cas simple et très fréquent où la partition est de la forme n = .. + ... + 2 + 1 + 1 + 1 ... + 1.
    Je parlais surtout des premières réponses, mais je n'avais pas tout revu quand j'ai reposté ici, ça fait quelques temps qu'il n'y avait plus de réponse ici
    Je ne répondrai à aucune question technique en privé

  16. #116
    yan
    yan est déconnecté
    Rédacteur
    Avatar de yan
    Homme Profil pro yan verdavaine
    Ingénieur expert
    Inscrit en
    mars 2004
    Messages
    9 961
    Détails du profil
    Informations personnelles :
    Nom : Homme yan verdavaine
    Âge : 32
    Localisation : France, Ille et Vilaine (Bretagne)

    Informations professionnelles :
    Activité : Ingénieur expert
    Secteur : High Tech - Multimédia et Internet

    Informations forums :
    Inscription : mars 2004
    Messages : 9 961
    Points : 12 421
    Points
    12 421

    Par défaut

    Bon ben,
    vu que j'avais recodé un algo faux, j'ai fait ma propre solution en récursive avec C++
    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
    #include <iostream>
    #include <algorithm>
    #include <vector>
    #include <ctime>
    #include <iterator>
     
    //#define AFFICHER
    int nbvalue(0);
     
    inline void afficher(std::vector<int> & myVect,int nb)
    {
        nbvalue++;
        #ifdef AFFICHER
        std::cout<<"[";
        std::copy(myVect.begin(),myVect.begin()+nb-1,std::ostream_iterator<int>(std::cout,", "));
        std::cout<<myVect[nb-1]<<"]\n";
        #endif
    }
     
    //fonction récussive
    void generate(std::vector<int> & myVect,int & reste ,const  int & nb_precedent,int & level)
    {
    //si reste ==0 alors la somme des chiffres est bien ègale au chiffre de dépard
    if (reste==0) afficher(myVect,level);
    //on interdit que le chiffre que l'on va traiter puisse etre plus grand que le précédent
    for (int i=(reste>nb_precedent) ? nb_precedent:reste;i>0 ;--i)
        {
        myVect[level] = i;
        int nextReste = reste-i;
        int nextLevel =level+1;
        //on traite le prochain chiffre avec le reste
        generate(myVect,nextReste,i,nextLevel);
     
        }
    }
     
    int main()
    {
        clock_t t1=std::clock();
        int n =100;
        std::vector<int> myVect(n);
        int level =0;
        generate(myVect,n,n,level);
        clock_t t2=std::clock();
        std::cout<<nbvalue<<std::endl;
        std::cout<<double(t2-t1)/CLOCKS_PER_SEC<<std::endl;
        return 0;
    }
    mais je suis un peu plus lent que celui de Jean-Marc.Bourguet j'ai pas compris sont code...
    Développeur Windows 8, Windows phone 8 et Nokia Asha, inscrivez vous sur DVLUP

  17. #117
    yan
    yan est déconnecté
    Rédacteur
    Avatar de yan
    Homme Profil pro yan verdavaine
    Ingénieur expert
    Inscrit en
    mars 2004
    Messages
    9 961
    Détails du profil
    Informations personnelles :
    Nom : Homme yan verdavaine
    Âge : 32
    Localisation : France, Ille et Vilaine (Bretagne)

    Informations professionnelles :
    Activité : Ingénieur expert
    Secteur : High Tech - Multimédia et Internet

    Informations forums :
    Inscription : mars 2004
    Messages : 9 961
    Points : 12 421
    Points
    12 421

    Par défaut Question

    Pour les version fonctionnelles qui font de super score, il créé un arbre dont les solutions sont tous les trajet/graph entre la base et les feuilles. C'est bien cela?
    Malheureusement leur score correspond uniquement à la création de cette arbre, non?
    Si c'est bien cela, ne devrait il pas ajouter les parcours pour que l'on puisse réellement comparer les différent résultats?
    Développeur Windows 8, Windows phone 8 et Nokia Asha, inscrivez vous sur DVLUP

  18. #118
    Membre confirmé Avatar de Steki-kun
    Profil pro
    Inscrit en
    janvier 2005
    Messages
    222
    Détails du profil
    Informations personnelles :
    Âge : 31
    Localisation : France, Paris (Île de France)

    Informations forums :
    Inscription : janvier 2005
    Messages : 222
    Points : 255
    Points
    255

    Par défaut

    Si tu parles de la version d'alex pi, oui, et il y a je sais pas combien de posts où il est question de cela au cours de cette discussion

    Les miennes visitent toutes les solutions en revanche, et leur fonctionnement est à peu près le même que celui de JMB, à savoir :
    * on part de la décomposition triviale n = n
    * on prend le premier terme à droite k qui soit > 1 dans la décomposition (s'il n'y en a pas, on a terminé)
    * on le remplace par (k-1) + ... + (k-1) + r où (k-1) est présent q fois et où q(k-1)+r est la division euclidienne de (k+tous les 1 qui sont à droite) par (k-1), on a donc une nouvelle décomposition qui est la plus grande possible, tout en étant plus petite que la précédente (dans l'ordre lexicographique)
    * on retourne à l'étape 2

    Cet algo permet de visiter toutes les décompositions où les entiers sont rangés dans l'ordre décroissant, de n à 1 + 1 + .... + 1, dans l'ordre inverse de l'ordre lexicographique donc.

    Dans sa 2ème version, JMB optimise en ne stockant pas les 1, il stocke juste le nombre de 1 dans remainder. Dans ma deuxième version, je généralise cette idée pour tous les entiers de la décomposition (pour minimiser la taille de mes listes). Et dans mes 2 versions, je traite spécialement le cas où k = 2 puisqu'il est fréquent et simple (idée donnée par Knuth dans le Volume 4 Fascicule 3 du Art of Computer Programming, by the way). Voilou
    I'm the kind of guy that until it happens, I won't worry about it. - R.H. RoY05, MVP06

  19. #119
    yan
    yan est déconnecté
    Rédacteur
    Avatar de yan
    Homme Profil pro yan verdavaine
    Ingénieur expert
    Inscrit en
    mars 2004
    Messages
    9 961
    Détails du profil
    Informations personnelles :
    Nom : Homme yan verdavaine
    Âge : 32
    Localisation : France, Ille et Vilaine (Bretagne)

    Informations professionnelles :
    Activité : Ingénieur expert
    Secteur : High Tech - Multimédia et Internet

    Informations forums :
    Inscription : mars 2004
    Messages : 9 961
    Points : 12 421
    Points
    12 421

    Par défaut

    ok, merci, je vais essayer de comprendre

    Par contre j'ai n'ai pas trop compris le temps de tes résultats...
    pour 100 tu arrive à 5.236s ??!!!!
    tu as comparrai par rapport au code C++ sur t'as machine?
    Sinon c'est marrant, mon code donne le même ordre de résultat que celui de JMB mais il ne fait pas la même chose
    Développeur Windows 8, Windows phone 8 et Nokia Asha, inscrivez vous sur DVLUP

  20. #120
    Membre confirmé Avatar de Steki-kun
    Profil pro
    Inscrit en
    janvier 2005
    Messages
    222
    Détails du profil
    Informations personnelles :
    Âge : 31
    Localisation : France, Paris (Île de France)

    Informations forums :
    Inscription : janvier 2005
    Messages : 222
    Points : 255
    Points
    255

    Par défaut

    J'arrive même a 2.6s sur la version impérative qui travaille à espace mémoire constant ; et non je n'ai pas compilé la version C++ chez moi, de tte façon j'ai pas un Cray chez moi c'est un AMD64 assez standard (et je n'utilise qu'un core) Il faut bien voir que quand n=100, il y a presque 80% des 191millions de partitions qui sont de la forme .... + 2 + 1 + 1 ... + 1 donc traiter ce cas là 'en place' au lieu de faire une boucle qui va remplacer les 1 par des 1 ça peut faire gagner beaucoup. Et la proportion va en augmentant quand n augmente.
    I'm the kind of guy that until it happens, I won't worry about it. - R.H. RoY05, MVP06

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
  •