Discussion :

[gilims]

Bonsoir à tous.
Je poste ce sujet car les temps sont difficiles.
Voici le problème : J'ai un fichier de 16000 lignes, chaque ligne étant de la forme suivante => "111:BBE|24". Le programme lit le fichier et est censé enregistré dans un container de type map les informations de ce fichier, la clé étant "111:BBE" de type string et la valeur étant un entier (ici 24). Le souci c'est que, pour lire et enregistrer mes 16000 lignes, le programme met environ 20 ms sur mon ordinateur. Sachant que les autres taches (qui consiste à lire des fichiers aussi long, à les interpréter et effectuer des calculs de toutes sortes) mettent 10 ms. En tout, ces 16000 lignes représentent 66% de temps d'utilisation, et c'est 66% inutiles. Je veux bien 1ms mais pas 20 !!!

Ma question est ainsi la suivante : Comment faire pour éviter autant de temps perdu ???!!!!

J'ai essayé de séparer les deux données (clé et valeur) dans deux vectors, c'est légèrement mieux mais insuffisant.
J'ai essayé d'intégrer les 16000 lignes dans le programme directement, je vous parle pas de l'horreur (je le savais dès le départ, je voulais savoir ce que ca donnais !! )

En gros je suis un peu perdu... un coup de main !!
Merci d'avance.

Voici le code:

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
 
map<string,int>PH4_pos;
string str;
char[512] buffer;
FILE *fp = fopen("fichier","r");
 while (!feof(fp))
    {
       fgets(buffer,511,fp);str=buffer;
PH4_pos.insert(pair<string, int>(str.substr(0,8),atoi(str.substr(9))));
    }
 
    fclose(fp);

Je sais pour les puristes,c'est moche désolé !!!
Merci encore !!

[screetch]

ca fait beaucoup d'allocations memoires ca

Code :

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

1
2
3
4
5
6
7
8
9
 while (!feof(fp))
    {
        fgets(buffer,511,fp);
        str=buffer; // 1 allocation
        PH4_pos.insert( // 1 allocation pour le noeud dans l'arbre
                 pair<string, int>( // 1 copie de la clé dans l'arbre
                      str.substr(0,8), // 1 allocation dans substr
                      atoi(str.substr(9)))); // 1 allocation dans substr
    }

essaye:

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
 
map<string,int>PH4_pos;
char[512] buffer;
char[512] key;
int value;
FILE *fp = fopen("fichier","r");
while (!feof(fp))
{
    fgets(buffer,511,fp);
    sscanf(buffer, "%s|%d", key, &value);
    PH4_pos.insert(std::make_pair(key, value));
}

qui devrait largement diminuer le nombre d'allocations (3 je crois, peut etre 2).
apres, ca reste des std::string et des std::map

[gilims]

Merci pour ta réponse, screetch.
Je viens d'essayer ta méthode, et hélàs ... c'est pire !!!!
J'obtiens 26 ms par test au lieu des 20 auparavant !!

Après je vois qu'un seul moyen brutal de faire ca, c'est de créer deux tableaux de taille fixe et d'enregistrer les données dedans ... pas de vérification, pas d'allocation en plus, rien que le strict minimum ... mais bon, c'est moyen ...

[Goten]

Utilise spirit.

[3DArchi]

Salut,
Quand tu étais sur std::vector, as-tu utiliser std::vector::reserve au départ ?
Comme dit screetch, tu devrais chercher à minimiser (supprimer) les allocations dans ta boucle.
En particulier, pour le coup, remplace std::string soit par un std(ou boost)::array<char,5>
J'ai fais quelques tests à l'arrache avec visual et gcc en mode release sur un fichier avec 640 000 entrées :

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
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
#include <iostream>
#include <fstream>
#include <map>
#include <string>
#include <iomanip>
#include <vector>
#include <cstdlib>
#include <boost\timer.hpp>
#include <boost\array.hpp>
#include <algorithm>
#include <utility>
 
static std::string const directory = "D:\\Informatique\\cpp\\projets\\Tests\\TestCpp\\TestCpp\\";
static const int nbr_element = 640000;
 
typedef boost::array<char,8> fixed_size_string_t;
typedef std::pair<fixed_size_string_t,int> element_t;
 
inline int compare(char const *first, char const *second, int count)
{
   for (; 0 < count; --count, ++first, ++second)
	   if (*first!=*second)
		   return (*first < *second ? -1 : +1);
   return (0);
}
 
inline bool operator<(element_t const& lhs_, element_t const & rhs_)
 
{
   return compare(lhs_.first.begin(),rhs_.first.begin(),8)<0 ?true:false;
}
 
 
 
void read_1(FILE *pf_)
{
   std::map<std::string,int>PH4_pos;
   std::string str;
   char buffer[512];
   while (!feof(pf_))
   {
      fgets(buffer,511,pf_);str=buffer;
      PH4_pos.insert(std::pair<std::string, int>(str.substr(0,8),atoi(str.substr(9).c_str())));
   }
}
 
int read_2(FILE *pf_)
{
   std::map<std::string,int>PH4_pos;
   char buffer[512];
   while (!feof(pf_))
   {
      fgets(buffer,511,pf_);
      PH4_pos.insert(std::pair<std::string, int>(std::string(buffer,buffer+8),atoi(buffer+8)));
   }
   return PH4_pos.size();
}
 
void read_3(FILE *pf_)
{
   std::vector<fixed_size_string_t> vect_cles;
   std::vector<int>vect_valeurs;
   fixed_size_string_t cles;
   char buffer[512];
   vect_cles.reserve(nbr_element);
   vect_valeurs.reserve(nbr_element);
   while (!feof(pf_))
   {
      fgets(buffer,511,pf_);
      std::copy(cles.begin(),cles.end(),buffer);
      vect_cles.push_back(cles);
      vect_valeurs.push_back(atoi(buffer+8));
   }
}
 
 
void read_3_bis(FILE *pf_)
{
   std::vector<fixed_size_string_t> vect_cles;
   std::vector<int> vect_valeurs;
   char buffer[512];
   vect_cles.resize(nbr_element);
   vect_valeurs.resize(nbr_element);
   std::vector<fixed_size_string_t>::iterator it_cles = vect_cles.begin();
   std::vector<int>::iterator it_valeurs = vect_valeurs.begin();
   while (!feof(pf_))
   {
      fgets(buffer,511,pf_);
      std::copy(it_cles->begin(),it_cles->end(),buffer);
      *it_valeurs = (atoi(buffer+8));
   }
}
 
 
void read_4(FILE *pf_)
{
   std::vector<element_t> vecteur;
   fixed_size_string_t cles;
   char buffer[512];
   vecteur.reserve(nbr_element);
   while (!feof(pf_))
   {
      fgets(buffer,511,pf_);
      std::copy(cles.begin(),cles.end(),buffer);
      vecteur.push_back(element_t(cles,atoi(buffer+8)));
   }
}
 
void read_4_bis(FILE *pf_)
{
   std::vector<element_t> vecteur;
   char buffer[512];
   vecteur.resize(nbr_element);
   std::vector<element_t>::iterator it=vecteur.begin();
   while (!feof(pf_))
   {
      fgets(buffer,511,pf_);
      std::copy(it->first.begin(),it->first.end(),buffer);
      it->second = atoi(buffer+8);
   }
}
 
 
void read_5(FILE *pf_)
{
   typedef boost::array<char,8> fixed_size_string_t;
   typedef std::pair<fixed_size_string_t,int> element_t;
   std::vector<element_t> vecteur;
   fixed_size_string_t cles;
   char buffer[512];
   vecteur.reserve(nbr_element);
   while (!feof(pf_))
   {
      fgets(buffer,511,pf_);
      std::copy(cles.begin(),cles.end(),buffer);
      vecteur.push_back(element_t(cles,atoi(buffer+8)));
   }
 
   std::stable_sort(vecteur.begin(),vecteur.end());
}
 
void read_5_bis(FILE *pf_)
{
   std::vector<element_t> vecteur;
   char buffer[512];
   vecteur.resize(nbr_element);
   std::vector<element_t>::iterator it=vecteur.begin();
   while (!feof(pf_))
   {
      fgets(buffer,511,pf_);
      std::copy(it->first.begin(),it->first.end(),buffer);
      it->second = atoi(buffer+8);
   }
 
   std::stable_sort(vecteur.begin(),vecteur.end());
}
 
template<class callable_>
void fonction(callable_ f_)
{
   std::string file = directory + "fichier.txt";
   FILE *fp = fopen(file.c_str(),"r");
   boost::timer timer;
   f_(fp);
   double elapsed = timer.elapsed();
   std::cout<<"elapsed = "<<elapsed<<"\n";
 
   fclose(fp);
}
 
 
int main()
{
   std::string s;
   fonction(read_1);
   fonction(read_2);
   fonction(read_3);
   fonction(read_3_bis);
   fonction(read_4);
   fonction(read_4_bis);
   fonction(read_5);
   fonction(read_5_bis);
   return 0;
}

J'obtiens comme temps :

elapsed = 0.947
elapsed = 0.892
elapsed = 0.178
elapsed = 0.174
elapsed = 0.182
elapsed = 0.175
elapsed = 0.466
elapsed = 0.453

elapsed = 1.152
elapsed = 0.88
elapsed = 0.178
elapsed = 0.187
elapsed = 0.191
elapsed = 0.191
elapsed = 0.663
elapsed = 0.659

read_1 : tel que tu l'as présenté
read_2 : ce que tu as présenté sans les std::string intermédiaire
read_3 : 2 vecteurs avec boos::array<char,8> à la place de std::string + reserve
read_3_bis : idem read_3 mais avec des std::vector::resize et un itérateur à la place d'un reserve+push_back
read_4 : un seul vecteur avec un élément std::pair<boost::array<char,8>, int>
read_4_bis : idem read_4 mais avec resize + itérateur ) la place de reserve + push_back
read_5 : idem read_4 + stable_sort
read_5_bis : idem read_4_bis + stable_sort

Il n'est pas très honnête de comparer brutalement les std::vector aux std::map car un map est un conteneur plus 'évolué' : la recherche sur une map est moins cher que sur un vecteur, cette différence de cout étant payée à la construction. C'est pour cela que j'ai mis les tests 5 et 5_bis avec le tri en plus. Là, les temps de recherche redeviennent comparable.

Conclusion : vecteur toujours plus performant. Si ensuite la recherche n'est pas pénalisante, utiliser uniquement un vecteur. Sinon, faire un tri : vecteur + tri reste moins cher que map.


Il resterait probablement à travailler sur la lecture et la conversion (atoi)

[gilims]

C'est parfait !!! Merci 3DArchi !!! J'ai utilisé la méthode 3, qui prends que 2ms au lieu des 20ms auparavant. Cela reste long pour ce que c'est bien bien mieux qu'avant donc j'en suis content !!! Merci encore