STL moins rapide :?

**yan** · 11/12/2007, 21h10

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** · 12/12/2007, 14h35

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** · 12/12/2007, 14h42

Envoyé par Pacorabanix

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** · 12/12/2007, 14h46

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** · 12/12/2007, 16h17

Envoyé par Pacorabanix

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** · 12/12/2007, 17h06

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

.

**yan** · 12/12/2007, 19h40

Bonjour,
merci pour toute c'est réponse

Envoyé par aoyou

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.

ce morceau de code est une optimisation du code de millie. Il recherche, à partir du début, la dernière position ou le test est validé. Il est donc toujours préférable de partir de la fin. Cela fait moins de teste.

Envoyé par Kujara

C'est connu qu'utiliser les iterators pour parcourir un vector, c'est lent.

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...

Avec les optimisations et un vector, un iterator est aussi rapide qu'un pointeur. C'est même le même chose.Et parcourir un tableau a l'envert n'est pas plus lent.
Jusqu'a preuve du contraire

Envoyé par 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.
Si tu regardes le code, je ne fais jamais de resize du tableau

.

Ou voit tu des réallocation?
un resize ne réalloue pas si il n'y as pas besoin

Bon je peut me tromper bien sur

**jmelyn** · 12/12/2007, 21h36

Mongaulois, si tu veux faire des essais, tu peux extraire le resize() de la fonction generationSolutionMongaulois() pour le mettre dans la fonction generationSommeMongaulois(), puis tu passes un pointeur dessus. Il faut simplement connaître la limite du tableau. C'est ce que j'ai fait, et je pense que c'est le resize() qui perd du temps.

J'ai repris mon programme à la maison (même type de machine) et j'ai changé le vector en tableau simple (new int[maxSize]). J'ai compilé en optimisant (-O3) les deux versions. Les temps d'exécution sont maintenant avec vector ou avec new: environ 0m0.070s toujours pour une taille de 200.

Tout ça sur un quadproc Q6600 qui tourne Linux (Fedora 8) et g++ version 4.1.2.

**yan** · 13/12/2007, 15h08

Envoyé par jmelyn

Mongaulois, si tu veux faire des essais, tu peux extraire le resize() de la fonction generationSolutionMongaulois() pour le mettre dans la fonction generationSommeMongaulois(), puis tu passes un pointeur dessus. Il faut simplement connaître la limite du tableau. C'est ce que j'ai fait, et je pense que c'est le resize() qui perd du temps.

J'ai repris mon programme à la maison (même type de machine) et j'ai changé le vector en tableau simple (new int[maxSize]). J'ai compilé en optimisant (-O3) les deux versions. Les temps d'exécution sont maintenant avec vector ou avec new: environ 0m0.070s toujours pour une taille de 200.

Tout ça sur un quadproc Q6600 qui tourne Linux (Fedora 8) et g++ version 4.1.2.

Juste pour info, ces code ne donne pas tout les solutions

Ton code est le recodage de ce que j'avais fait?
Pour le resize, je suis septique :
http://www.cplusplus.com/reference/s...or/resize.html

merci pour ton aide.
Je vais regarder tout ca

**yan** · 13/12/2007, 15h36

Bon j'ai refait des testes avec 200 sur les 3 codes qui donne le même nombre de solution (bien sur il y en as beaucoup plus)
alors :
moi : 0.187
jmelyn : 0.109
millie : 0.124

J'ai du me mélanger les pinceaux

donc le code STL n'est pas plus lent. Ouf!!!!
A mon avis la différence est juste dû aux appels de fonction et à l'allocation de la mémoire

Si tu veut, j'ai refait un code qui calcul bien toute les solutions. Tu peut essayer de l'améliorer

http://www.developpez.net/forums/sho...=378299&page=9

STL moins rapide :?

SL & STL C++

Discussions similaires

Partager

Partager