Discussion :

[darkman19320]

Bonjour tout le monde,

Je ne trouve d'information sur la complexité en temps pour construire un objet std::time.
On m'a affirmé que c'est coûteux sans plus de précision alors que je suis persuadé que c'est en temps constant comme la plupart (tous?) des objets de la stl...

De plus, est-ce que quelqu'un utilise boost::timer pour calculer le temps cpu. Est-ce que vous en êtes satisfait (niveau précision, information & co)?

Merci pour tout.

[ternel]

La complexité n'a pas de sens, ici, parce qu'il n'y a pas de "n" à faire varier
La complexité a toujours un rapport avec une quantité.

"toujours 1ms" et "toujours 2ans" sont deux o(1), mais pas du tout équivalent en pratique.
C'est ce qu'on a du vouloir te dire

[darkman19320]

Merci pour ta réponse,

Ce que l'on m'a dit exactement c'est que la construction d'un objet de type std::time prend plus de temps que de faire un "count" au niveau d'un std::set<std::string>....
Donc à moins que je sois complètement à l'ouest, je pense que cette affirmation est complètement fausse non?
Mais vu que je travaille dans un environnement où il faut des preuves pour tout, je me demandais si dans la norme C++ il y avait un passage indiquant comment doit être créé un std::time.

[koala01]

Salut,

Merci pour ta réponse,

Ce que l'on m'a dit exactement c'est que la construction d'un objet de type std::time prend plus de temps que de faire un "count" au niveau d'un std::set<std::string>....
Donc à moins que je sois complètement à l'ouest, je pense que cette affirmation est complètement fausse non?
Mais vu que je travaille dans un environnement où il faut des preuves pour tout, je me demandais si dans la norme C++ il y avait un passage indiquant comment doit être créé un std::time.

Attention, cela n'a rien à voir.

D'un coté, la complexité représente l'évolution du temps nécessaire à effectuer une action en fonction du nombre d'éléments qu'il faut trier.

Comme le faisait remarquer leternel, "toujours 1ms" et "toujours 2ans" ont la même complexité, bien que représentant des échelles de temps diamétralement opposées.

ce que la phrase que tu cite tente de t'expliquer, c'est qu'il faudra "d'avantage de cycles d'horloges cpu" pour arriver à te fournir un objet de type std::time que pour te fournir le nombre d'élément qu'un set de string contient.

Cette assertion est "globalement" juste dans le sens où la construction d'un objet peut prendre énormément de temps (même si elle a une complexité en o(1) !!!) parce qu'elle va devoir initialiser tous les membres du dit objet, et donc appeler le constructeur de chaque membre, et cela de manière récursive, alors que la récupération du nombre d'éléments dans un vecteur ne fait qu'aller chercher une valeur à une adresse parfaitement connue (ce qui doit tourner aux alentours d'une dizaine de cycles d'horloges, grand maximum).

De fait, l'initialisation de time a de bonnes chances de devoir recourir à un appel système (afin de récupérer une donnée de l'horloge interne), plus sans doute deux ou trois petites choses à coté

Du coup, le nombre de cycle d'horloge nécessaire à l'initialisation d'un objet de type std::time a, en effet, de bonne chances d'être supérieur au nombre de cycles d'horloge nécessaire à obtenir un nombre d'élément dans une structure dynamique

[darkman19320]

Merci koala01 pour cette très bonne explication.

Donc si je résume bien, si mon set de string est de petite taille, il serait plus avantageux de faire un count dessus que de construire le time vu que le nombre de cycle d'horloge à des chances d'être plus faible.

Est-ce qu'il est possible de connaitre/calculer le nombre de cycle d'horloge pour telle ou telle opération?

[ternel]

oui … et non.

Le problème principal est que ton programme n'est pas le seul à tourner.
Il y a aussi l'OS, et tous les autres.
Chacun travaillant en entrelaçant leurs instructions avec les tiennes.

Du coup, tu peux mesurer l'écart de temps entre deux instructions, mais ce ne serait qu'une indication.

Par contre, il me semble qu'il existe une méthode pour demander au système le temps passé dans un programme, mais c'est un vague souvenir…

Une solution de base:
mesurer l'heure avant et après 100 000 appels (avec time ou std::time)

[koala01]

Merci koala01 pour cette très bonne explication.

Donc si je résume bien, si mon set de string est de petite taille, il serait plus avantageux de faire un count dessus que de construire le time vu que le nombre de cycle d'horloge à des chances d'être plus faible.

Même si le set est de grande taille, la fonction size du set est assurée d'être en temps constant :
le set (tout comme les autres collections de la S(T)L) dispose d'une donnée mise à jour à chaque ajout / suppression d'un élément qui représente le nombre d'éléments qu'il contient, et qu'il "suffit" au processeur de charger dans un de ses accumulateurs

Est-ce qu'il est possible de connaitre/calculer le nombre de cycle d'horloge pour telle ou telle opération?

Sans prendre en compte la charge du système (tout ce qui tourne sur l'ordinateur et qui pourrait s'intercaler entre deux instructions destinées à ton programme), le seul moyen serait d'aller voir au niveau de l'assembleur et de calculer (en nombre de cycles d'horloge) le temps nécessaire effectuer les instructions correspondantes.

Le tout, en sachant qu'à chaque fonction appelée, il faudra penser à calculer le nombre de cycles d'horloge nécessaire à l'exécution de cette fonction pour avoir la durée globale de la fonction que tu recherches.

Ce n'est pas impossible, mais cela nécessite de très bonnes connaissances en assembleur et d'une bonne table de durées (normalement, il y a moyen de l'avoir note )

Et, de toutes manières, cela ne te donnerait jamais que la "durée théorique" car il resterait le problème de tout ce qui tourne sur le système et qui demande, à un moment ou à un autre d'avoir "un peu de temps pour travailler".

La solution la plus adaptée est donc de travailler par "benchmark" (c'est en gros la solution présentée par leternel )

[darkman19320]

Merci pour vos réponses à tous les deux.

Je viens d'implémenter un petit exemple (pas du tout factoriser) comme me conseille leternel:

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
#include <ctime>
#include <set>
#include <string>
#include <iostream>
 
#include <boost/timer/timer.hpp>
 
using namespace std;
using boost::timer::cpu_timer;
using boost::timer::cpu_times;
using boost::timer::nanosecond_type;
 
#define N 1000000
 
void bigCalculation(int& temp, int i)
{
   std::time_t t1, t2;
   time(&t1);
   temp = i+i;
   time(&t2);
   difftime(t2, t1);
}
 
void alwaysTrue(const set<string>& aSet) //Le test d'appartenance est toujours vrai
{
  int temp = 0;
  cpu_timer timer;
  for(int i = 0; i < N; ++i)
    {
      if(aSet.count("test"))
	{
	  bigCalculation(temp, i);
	}
    }
  cpu_times elapsed(timer.elapsed());
  cout << "Elapsed system time: " << elapsed.system << "; user time: " << elapsed.user << endl;
}
 
void alwaysFalse(const set<string>& aSet) //Le test d'appartenance est toujours faux
{
  int temp = 0;
  cpu_timer timer;
  for(int i = 0; i < N; ++i)
    {
      if(aSet.count("wrongText"))
	{
	  bigCalculation(temp, i);
	}
    }
  cpu_times elapsed(timer.elapsed());
  cout << "Elapsed system time: " << elapsed.system << "; user time: " << elapsed.user << endl;
}
 
void withoutCount() //On fait directement le calcul
{
  int temp = 0;
  cpu_timer timer;
  for(int i = 0; i < N; ++i)
    {
      bigCalculation(temp, i);
    }
  cpu_times elapsed(timer.elapsed());
  cout << "Elapsed system time: " << elapsed.system << "; user time: " << elapsed.user << endl;
}
 
int main()
{
  set<string> aSet;
  aSet.insert("test");
  aSet.insert("test2");
 
  cout << "Test count + bigCalculation" << endl;
  alwaysTrue(aSet);
 
  cout << "Test count" << endl;
  alwaysFalse(aSet);
 
  cout << "bigCalculation" << endl;
  withoutCount();
 
  return 0;
}

Sur ma machine (Mac OS X lion avec Gcc 4.7 et boost 1.53), je constate que les temps suivants: alwaysTrue > alwaysFalse >= withoutCount.

std::set::count ne fait pas qu'un simple size: il teste si la valeur passée est présente dans le std::set avec l'opérateur < (ou std::less si je ne me trompe pas). La comparaison de chaine de caractère n'étant pas triviale, je pense que c'est pour cette raison que j'obtiens ces résultats.

Si vous avez d'autres OS, pouvez-vous me dire si vous avez le même comportement?

Encore merci.

Edit: J'ai réussi à mettre la main sur un Windows (avec VS2012) et un Linux(gcc 4.7) et j'obtiens le même comportement.