Discussion :

[Iradrille]

Hello,

J'ai hésité à poster ici ou dans algo, j'espère avoir fait le bon choix ^^"

J'ai une méthode qui à une complexité en O(1), mais son temps d'exécution augmente avec la taille des données
La méthode

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
// unsigned int m_size: nombre d'éléments dans le tableau
// T *m_data: tableau de m_sizeMax éléments (m_sizeMax >= m_size)
// unsigned int m_poped: nombres d'éléments sortis et début du tableau (==0 dans mes tests)
 
template <class T>
bool Foo<T>::pop(T& val) {
   if(!m_size) {
      return false;
   }
   val = m_data[m_poped++];
   --m_size;
   return true;
}

Elle est appelée comme ça

Code :

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

1
2
3
4
5
6
7
8
const unsigned int TEST_REPEAT = 100U;
Foo<int> **foos; //je vous passes l'initialisation ^^
int val;
QueryPerformanceCounter(&start); // vui je bosse sous Windows.
for(unsigned int nbRepeat=0; nbRepeat<TEST_REPEAT; ++nbRepeat) {
   foos[nbRepeat]->pop(val);
}
QueryPerformanceCounter(&end);

Et malgré le fait qu'ici rien ne dépende de la taille du tableau m_data, le temps d'exécution de cette méthode est plus ou moins proportionnel à la taille du tableau.

Si quelqu'un à une explication ou une idée, je prend.

[ternel]

as tu essayé de réduire ta fonction pop, en supprimant expression par expression, jusqu'a arriver à pop(){return --size == 0;}?

[white_tentacle]

Si quelqu'un à une explication ou une idée, je prend.

Qu’entends-tu par « plus ou moins » ?

Cela dit, à vu de nez, plus ton tableau est grand, plus tu as de page faults.

[koala01]

Salut,

La fonction pop en elle meme est en O(1), mais QueryPerformanceCounter est en dehors de la boucle, ce qui fait que tu prend l'ensemble les TEST_REPEAT appels de la boucle comme temps de référence.

Il est donc plus que normal que tu obtiennes un résultat en O(N)

Si tu tiens à vérifier les performances de ta seule fonction, il faut que ton calcul se fasse dans la boucle en elle-même, sans prendre en compte les actions éventuellement effectuées qui ne t'intéresseraient pas (comme, par exemple, le fait de sauvegarder le résultat quelque part)

[Iradrille]

Qu’entends-tu par « plus ou moins » ?

Cela dit, à vu de nez, plus ton tableau est grand, plus tu as de page faults.

Voila ce que ça donne


@koala01: il y a TEST_REPEAT test pour chaque taille de tableau testé, le surcoup de la boucle for est constant et le même quelques soit la taille du tableau. J'ai unroll la boucle à la main (a grand coup de copier collé ^^"), mais les résultats sont les mêmes.

J'ai essayé de réduire la fonction au maximum, pour en arriver à un simple return true;
Le résultat est toujours simililaire



Ca serait donc une histoire de page faults ?

Edit: Je continu les tests mais je comprends pas :/
J'ai recodé ça en Java pour voir si ça venait du langage ou du compilo (on sait jamais ^^"), les résultats sont identiques...
Testé avec des tableaux plus grands (de 1 000 à 200 000 par pas de 1 000, puis jusque 1 000 000 par pas de 100 000). Le temps d'exécution est toujours croissant.
Je comprend vraiment pas comment une fonction qui se résume à

Code :

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

1
2
3
int pop() {
   return m_data[0];
}

peut être en O(log n)


(et avant qu'on me troll sur le fait que le java est plus rapide que le c++, l'implémentation en java est minimale, pas de vérification de la taille du tableau, et pas de mise à jour de la taille ni de l'indice de début).

[Klaim]

As tu essayé de remplacer les itérations par index par des iterations de pointeur?

[gbdivers]

Peux tu donner un projet complet compilable ?

[Iradrille]

Peux tu donner un projet complet compilable ?

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
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
#define WIN32_LEAN_AND_MEAN
#include <Windows.h>
#include <iostream>
#include <ctime>
 
const unsigned int NB_TESTS = 100U;
const unsigned int TEST_REPEAT = 100U;
const unsigned int TEST_SIZE_MIN = 1000U;
const unsigned int TEST_SIZE_MAX = 20000U;
const unsigned int TEST_SIZE_INC = 1000U;
 
const double TIME_DIVISOR = (double)NB_TESTS * (double)TEST_REPEAT;
 
 
template <class T>
class IFoo {
 
public:
   virtual ~IFoo() { }
 
   virtual bool getMax(T& val) = 0;
   virtual bool pop(T& val) = 0;
   virtual void push(const T& val) = 0;
 
};
 
template <class T>
class Foo: public IFoo<T> {
 
   T *m_data;
   unsigned int m_size, m_maxSize, m_poped;
   double m_reallocSize, m_beforeRealloc;
 
public:
 
   Foo(const Foo& fp);
   Foo(unsigned int baseSize = 1000, double reallocSize = 1.3, double freeSpaceBeforeRealloc = 0.1);
   ~Foo();
 
   bool getMax(T& val);
   bool pop(T& val);
   void push(const T& val);
 
   // debug
   void print() {
      std::cout << "size: " << m_size << " poped: " << m_poped << std::endl;
      for(unsigned int i=0; i<m_size; ++i) {
         std::cout << m_data[i] << " ";
      }
      std::cout << std::endl;
   }
 
};
 
template <class T>
Foo<T>::Foo(const Foo& fp) {
   m_size = fp.m_size;
   m_maxSize = fp.m_maxSize;
   m_poped = fp.m_poped;
   m_reallocSize = fp.m_reallocSize;
   m_beforeRealloc = fp.m_beforeRealloc;
   m_data = new T[m_maxSize];
   memcpy(m_data, fp.m_data, m_maxSize*sizeof(T));
}
 
template <class T>
void Foo<T>::push(const T& val) {
   double d = (double)m_poped / m_maxSize;
   if(m_size == m_maxSize || d >= m_beforeRealloc) {
      m_maxSize *= m_reallocSize;
      T *ndata = new T[m_maxSize];
      memcpy(ndata+m_poped, m_data+m_poped, sizeof(int)*m_size);
      delete[] m_data;
      m_data = ndata;
   }
   else if(d >= m_beforeRealloc) {
      memmove(m_data, m_data+m_poped, sizeof(int)*m_size);
      m_poped = 0;
   }
 
   bool found = false;
   unsigned int i = 0;
 
   if(m_poped + m_size) {
      unsigned int max = m_size + m_poped, min = m_poped;
      while(!found && min < max-1) {
         i = (max+min) >> 1;
         found = (m_data[i] == val);
         if(val > m_data[i]) {
            max = i;
         }
         else {
            min = i;
         }
      }
   }
 
   if(m_poped && i == m_poped) {
      m_data[i-1] = val;
      --m_poped;
      ++m_size;
      return;
   }
   else if(i != m_size) {
      for(unsigned int cp=m_size+m_poped; cp>i; --cp) {
         m_data[cp] = m_data[cp-1];
      }
   }
   m_data[i] = val;
   ++m_size;
}
 
template <class T>
bool Foo<T>::pop(T& val) {
   if(!m_size) {
      return false;
   }
   val = m_data[m_poped];
   --m_size;
   return true;
}
 
template <class T>
bool Foo<T>::getMax(T& val) {
   if(m_size) {
      val = m_data[m_poped];
      return true;
   }
   return false;
}
 
template <class T>
Foo<T>::~Foo() {
   delete[] m_data;
}
 
template <class T>
Foo<T>::Foo(unsigned int baseSize, double reallocSize, double freeSpaceBeforeRealloc):
   m_size(0), m_poped(0), m_maxSize(baseSize), m_beforeRealloc(freeSpaceBeforeRealloc), m_reallocSize(reallocSize)
{
   m_data = new T[m_maxSize];
}
 
 
int main(int argc, char **argv) {
 
   LARGE_INTEGER freqSec, start, end;
   double freq;
   double tfill, tpop, tpeek;
 
   srand((unsigned int)time(nullptr));
   QueryPerformanceFrequency(&freqSec);
   freq = ((double)freqSec.QuadPart / 1000.0); // ms
 
 
   for(unsigned int size=TEST_SIZE_MIN; size<=TEST_SIZE_MAX; size+=TEST_SIZE_INC) {
      tfill = tpop = tpeek = 0.0;
 
      for(unsigned int nbTests=0; nbTests<NB_TESTS; ++nbTests) {
         // Génération des données
         Foo<int> foo(size);
         int toAdd = rand();
         for(unsigned int j=0; j<size; ++j) {
            foo.push(rand());
         }
 
         Foo<int> **foos = new Foo<int>*[TEST_REPEAT];
 
         for(unsigned int fi=0; fi<TEST_REPEAT; ++fi) {
            foos[fi] = new Foo<int>(foo);
         }
 
         // Push
         QueryPerformanceCounter(&start);
         for(unsigned int nbRepeat=0; nbRepeat<TEST_REPEAT; ++nbRepeat) {
            foos[nbRepeat]->push(toAdd);
         }
         QueryPerformanceCounter(&end);
         end.QuadPart -= start.QuadPart;
         tfill += ((double)end.QuadPart / freq);
 
         // Get Max
         QueryPerformanceCounter(&start);
         for(unsigned int nbRepeat=0; nbRepeat<TEST_REPEAT; ++nbRepeat) {
            foos[nbRepeat]->getMax(toAdd);
         }
         QueryPerformanceCounter(&end);
         end.QuadPart -= start.QuadPart;
         tpeek += ((double)end.QuadPart / freq);
 
         // Pop
         QueryPerformanceCounter(&start);
         for(unsigned int nbRepeat=0; nbRepeat<TEST_REPEAT; ++nbRepeat) {
            foos[nbRepeat]->pop(toAdd);
         }
         QueryPerformanceCounter(&end);
         end.QuadPart -= start.QuadPart;
         tpop += ((double)end.QuadPart / freq);
 
         for(unsigned int fi=0; fi<TEST_REPEAT; ++fi) {
            delete foos[fi];
         }
         delete[] foos;
      }
 
      tfill /= TIME_DIVISOR;
      tpeek /= TIME_DIVISOR;
      tpop /= TIME_DIVISOR;
 
      std::cout << "taille:" << size << " push: " << tfill << "ms peek: " << tpeek
         << "ms pop: " << tpop << "ms push+pop: " << tfill+tpop << "ms\n";
   }
 
   return 0;
}

Il ya un warning pour une conversion int->double->int, mais c'est sans grande importance.

[white_tentacle]

Cela dit, à vu de nez, plus ton tableau est grand, plus tu as de page faults.

Et à vu de tes résultats et de ton code, je vais maintenir.

Quand tu augmentes la taille de tes tableaux, tu te retrouves dans une situation ou chaque tableau est dans une page mémoire différente. Donc le processeur doit attendre que la page soit chargée depuis la mémoire dans son cache pour la traiter, et ça c’est très long comparativement au temps de traitement.

Puisque tu es sous windows, tu dois pouvoir récupérer le compteur de page faults, soit avec perfmon, soit depuis ton code. À mon avis, ce que tu observes vient de là (et explique assez bien le « plateau » que tu as entre 50000 et 200000, qui n’est pas vraiment log(n), ainsi que certaines irrégularités).

[Iradrille]

Ça à l'air d'être effectivement ça, merci.

Le temps d'exec est enfin constant. ^^