Discussion :

[cosmoff]

bonjour,

voila j'utilise dans mon code la fonction std::find() et j'aimerai connaitre le temps moyen qu'elle met pour réaliser sa fonction. J'ai donc fait le code :

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
int main(int argc, char const *argv[])
{
	std::vector<int> tab;
	std::vector<double> tabtime;
	for(int i = 0; i < 100; i++)
	{
		tab.push_back(i);
	}
 
	for (int n = 0; n < 100; n++)
	{
		auto start = std::chrono::system_clock::now();
		if( std::find(tab.begin(), tab.end(), n) != tab.end() )
		{
			//cout << "element find" << endl;
		}
		else
		{
			//cout << "element do not find" << endl;	
		}
		auto end = std::chrono::system_clock::now();
 
		std::chrono::duration<double> elapsed_seconds = end-start;
		tabtime.push_back(elapsed_seconds.count());
	}
	double somme = 0;
	for (int i = 0; i < tabtime.size(); ++i)
	{
		somme+= tabtime[i];
	}
	cout << "time std::find = " << somme/(double)tabtime.size() << endl;
 
	return 0;
}

Le probleme est lorsque je lance le code j'ai des temps qui varie beaucoup :
1er essai : 8.6e-07
second essai :1.74e-06
troisieme essai :5.2e-07
...

et je ne comprend pas pourquoi. Normalement sur 100 lancements de la fonction de devrais avoir une bonne estimation. Avez vous une idée de comment résoudre le probleme ?

Merci d'avance

[dalfab]

Bonjour,
il y a plusieurs problèmes ici:
- pourquoi faut-il autant de temps (rechercher linéairement 1 parmi 100, revient à en moyenne 50 itérations)? on devrait être de l'ordre de la centaine de nanosecondes.
- pourquoi ça fluctue?
Pendant que ton code se déroule, il se passe beaucoup de choses (des interruptions, des changements de contexte, ...) ce que tu mesures dépend de ce contexte et est par conséquent très variable.
De plus ton code est tellement court que la durée pour appeler la fonction now() et stocker son résultat n'est pas négligeable.

Pour avoir un temps moyen, il faut lancer N fois ce que tu veux analyser et diviser par N le résultat. Il y aura beaucoup moins de fluctuations.
Tu pourrais aussi essayer la fonction std::equal_range au lieu de std::find qui est plus rapide si le tableau est trié, ce qui est le cas ici.

[jo_link_noir]

std::equal_range -> std::lower_bound, sinon ça ne fait pas la même chose.

Mais sur un code comme celui-ci, le temps d’exécution est bien trop court pour être mesuré convenablement. Et il faut aussi activer les optimisations sinon un test de vitesse n'a pas de sens. Sauf que les compilateurs sont très malins et peuvent remplacer la boucle de find_if par... rien du tout.

Il y a pas mal de piège lorsqu'on fait des mesures, regarde cette réponse est peut-être aussi google bench ou http://quick-bench.com/.

[cosmoff]

Pour avoir un temps moyen, il faut lancer N fois ce que tu veux analyser et diviser par N le résultat. Il y aura beaucoup moins de fluctuations.

c'est ce que je fais, je recupere 50 temps différents et ensuite je fais la moyenne.

mais ce que tu me dis avec les fluctuations semble me dire que ce n'est pas trop possible de mesurer le temps d'exécution de la fonction std::find

[cosmoff]

merci jo_link_noir, je vais tester ca