Discussion :

[yan]

Bonjour,
en regardant ce code millie
http://www.developpez.net/forums/sho...0&postcount=55
j'ai vue qu'il y avait encore une optimisation a faire.

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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]++;
}

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

le voila avec la STL

Code C++ :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
 
#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 m'aider à comprendre?
Bien sur j'ai testé sans l'affichage pour ne pas avoir le problème de temps avec les cout.
J'ai testé avec GCC minGw
merci

[EDIT]
Le code est incomplé. il ne calcule pas tout, mais ma question reste la même. Pourquoi y as t'il une differencesde perf entre ces deux code qui donne le même résultat!!!!

[Pacorabanix]

euh ben à ce que je connais :

* le code sans stl accède directement à des ints, via un tableau -> donc adresse mémoire directe

* le code avec stl passe via des itérateurs. vector est le conteneur le plus simple *mais* il y a quand même des étapes en plus (de sorte qu'il est plus robuste et "sur" à utiliser, pas de risque de déborder du tableau en faisant une faute de frappe)

Ce n'est pas deja une bonne explication ?

PS pourquoi (*it)++ et pas ++(*it) ?

[aoyou]

le code sans stl accède directement à des ints, via un tableau -> donc adresse mémoire directe

Je ne vois aucunement un code avec un tableau. Si ce que tu appeles le code sans stl est le code ci-dessous, c'est bien un vecteur de la STL qui est utilisé ici, même si la notation est trompeuse.

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
 
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]++;
}

[Pacorabanix]

oula oui pardon ^^.

Alors la question est : est ce que operator[] accède directement à la mémoire, ou en tout cas plus vite qu'avec un iterator (qu'un reverse iterator devrais-je dire plutot), pour std::<vector> , à la manière d'un tableau ? Ce serait possible, vu qu'un vector est stocké dans une zone continue de mémoire.


EDIT : mouais, en relisant, j'ai cru avoir compris l'algo bien, mais en fait, je ne vois pas vraiment en quoi le deuxième est une optimisation du premier, pardonnez moi et en tenez pas compte de ma remarque, je pense pas qu'elle soit pertinente.

[Kujara]

lors la question est : est ce que operator[] accède directement à la mémoire, ou en tout cas plus vite qu'avec un iterator (qu'un reverse iterator devrais-je dire plutot), pour std::<vector> , à la manière d'un tableau ? Ce serait possible, vu qu'un vector est stocké dans une zone continue de mémoire.

Vivi, c'est le cas.

C'est connu qu'utiliser les iterators pour parcourir un vector, c'est lent.
Fait le test, vous verrez ^^.

Reverse iterator c'est encore pire, puisque tu parcours un tableau a l'envers, ce qui est quasiment toujours une mauvaise idée( probleme de cache). Mais bon, si tu n'a pas le choix...

[jmelyn]

Bonjour,

Je crois que tout est dans la manière d'utiliser la STL, et le C++ en général: les allocations sont très faciles et donc on les utilise sans trop regarder.

J'ai pris le code pointé, compilé et testé avec une taille de 200 sur ma machine: j'obtiens 12s (0m12.039s). Puis en voyant les résultats, j'ai recodé l'ensemble, mais en faisant attention aux allocations "lourdes". J'obtiens alors un peu plus de 2s (0m2.773s) soit un peu plus de 4 fois plus rapide. Le code est simple, d'un côté comme de l'autre, donc je pense que tout est dans les allocs... à moins d'une erreur .

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
#include <iostream>
#include <vector>
 
using namespace std;
 
int main(int argc, char* argv[])
{
    // create values vector
    int maxSize = 200;
    vector<int> valVec_(maxSize);
 
    // scan all possible sizes
    for(int currentSize = maxSize; currentSize > 0; --currentSize)
    {
        // scan possible values for the first place
        for (int val = maxSize / currentSize; val <= maxSize; ++val)
        {
            // init vector
            valVec_[0] = val;
            for(int i = 1; i < currentSize; ++i)
            {
                valVec_[i] = 1;
            }
            // scan all possible values for the current val
            int indexToInc = 0;
            do
            {
                // compute sum
                int sum = 0;
                for (int i = 0; i < currentSize; ++i)
                {
                    sum += valVec_[i];
                }
                // if all possible values have already been found
                if(sum > maxSize)
                {
                    break;
                }
                // if one solution has just been found
                if(sum == maxSize)
                {
/*                 // display values
                    cout << "[";
                    for (int i = 0; i < currentSize - 1; ++i)
                    {
                        cout << valVec_[i] << ", ";
                    }
                    cout << valVec_[currentSize - 1] << "]" << endl;
*/              }
                // set new values to try
                indexToInc = (indexToInc >= currentSize - 1) ? 1 : indexToInc + 1;
                ++valVec_[indexToInc];
                if (valVec_[indexToInc] > val)
                {
                    break;
                }
            } while (currentSize > 1);
        }
    }
    return 0;
}

Si tu regardes le code, je ne fais jamais de resize du tableau .