Discussion :

[cimestro]

Bonjour, je travailles actuellement sur un petit programme qui a pour but de compter le nombre d'occurence de chaque mot dans un fichier texte. Cependant je souhaites optimiser mon programme a l'aide d'unordored_map de sorte a ne pas rechercher betement. Je recupere donc un mot aléatoire dans mon fichier texte puis je verifie si je l'ai deja stocker. Si oui alors j'ajoute 1 au int de ma map sinon je rajoute une case dans ma map avec ce nouveau mot et avec un indice de 1.Une fois fais j'ai donc décidé de recupérer les temps d'execution d'une recherche/insertion a une intervalle. Je vais donc tous les 20 mot inserer (par exemple) calculer le temps que je mets pour inserer/rechercher le mot. Je devrais m'attendre a trouver des temps qui ne cesse de monter car la recherche va se faire sur un tableau de plus en plus rempli mais aussi des temps très bas qui correspond a des mots deja present dans ma map. Cependant j'ai des temps qui ne cesse de grandir. Je n'ai jamais des temps qui sont inferieur a leurs precedant.

Voici mon code: sachant que nous avons deux parametres lors de l'execution qui corresponds au nombre de mot a tester et a l'intervalle entre chaque temps recuperé d'une insertion

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
 
 
 
 
int main (int argc,char** argv) 
{
	string const fichier="text.txt";
	vector<float> vectortemp;
	lecturefichier(fichier);
	unordered_map<string, int> maMap;
	unordered_map<string,int>::iterator it;
	int compteur = strtol(argv[1], NULL, 10);
	int veriftaille = strtol(argv[2], NULL, 10);
	auto start = std::chrono::steady_clock::now();
	auto end = std::chrono::steady_clock::now();
	std::random_device r;
	std::default_random_engine nombrerand(r());
	for(unsigned i=0;0<compteur;i++)
	{	
		std::uniform_int_distribution<int> distribution(0,vecteur.size()-1);
		int nbr = distribution(nombrerand);
		cout<<nbr<<endl;
		if(i%veriftaille==0)
		{
		auto start = std::chrono::steady_clock::now();
 
		}
 
		it = maMap.find(vecteur[nbr]);
 
		if(it!= maMap.end())
		{
			maMap.at(vecteur[nbr]) += 1;
		}
		else
		{			
			maMap.insert(make_pair(vecteur[nbr],1));
		}
 
		vecteur.erase(vecteur.begin()+nbr);
		compteur--;
 
		if(i%veriftaille==0)
		{
			auto end = std::chrono::steady_clock::now();
			vectortemp.push_back(i);
			auto diff= std::chrono::duration_cast<std::chrono::nanoseconds>(end - start);
			vectortemp.push_back(diff.count());
		}
 
	}

j'espere que vous pourriez m'aider

[dalfab]

Bonjour,

- le temps nécessaire dans le cas où le mot est connu peut être estimé à :
DuréeFixe + (K/2).log( TailleDeLaMap )
- pour faire la mise à jour tu décides de refaire la recherche (par l'utilisation de la fonction at), il faut ajouter :
DuréeFixe + (K/2).log( TailleDeLaMap )

- le temps nécessaire dans le cas où le mot est inconnu peut être estimé à :
DuréeFixe + K.log( TailleDeLaMap ) (parcours 2 fois plus long pour voir que l'élément n'est pas trouvé)
- auquel on doit ajouter le temps d'insertion du mot nouveau (où tu utilises insert et donc tu refais une recherche d'où mettre cette entrée et tu amplifies dans le sens ce que que tu veux voir)
DuréeFixe + K.log( TailleDeLaMap )

Ce sont des temps très courts et la part variable est petite si TailleDeLaMap vaut moins de 10000 mots.
Par contre tu appelles vecteur.erase(vecteur.begin() + nbr) qui lui est extrêmement coûteux (avec un temps en K.TailleDuVecteur)

[koala01]

Salut,

Je ne suis déjà pas sur qu'une unorederd_map soit réellement avantageuse, car elle implique de calculer la valeur de hashage pour chaque mot que l'on va lire. que cela prend du temps, et que, comme tout clé de hashage, le risque de collision (de se retrouver avec deux mots différents présentant la même clé) existe.

Ensuite, tu vas me faire le plaisir de virer cette directive using namespace std; qui doit trainer dans ton code, bien que tu aies pris la précaution de ne pas la monter -->voici pourquoi<--.

En outre, tu devrais respecter d'avantage le SRP, car, là, ta fonction main, elle prend au moins trois responsabilités différentes, ce qui en fait décidément deux de trop

Enfin, tu vas me faire le plaisir de virer les lignes

Code :

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

1
2
3
 
	auto start = std::chrono::steady_clock::now();
	auto end = std::chrono::steady_clock::now();

qui se trouvent au lignes 10 et 11 du code que tu nous montre, car les variables définies sur ces lignes seront de toutes manière cachées par les lignes 21 et 41.

C'est d'ailleurs sans doute l'origine du problème, car, lors que tu calcule la différence de diff à la ligne 43, quelle est -- selon toi -- la valeur de la variable begin utilisée pour le calcul Je te le met dans le mille: c'est la valeur de la variable déclarée à la ligne 10, qui n'est absolument pas modifiée par la ligne 21

[cimestro]

Merci. Du coup oui je sais pas pourquoi j ai initialisé deux fois mes variable start et end. 😂😂. Du coup j ai modifié et cela correspond plus a mes attentes. Mais je ne suis tout de meme pas sur. En effet plus on mets de mot dans la table de hashage plus la recherche devrais etre longue. Cependant sur une recherche de 70000 mot avec recuperation du temps tous les 100 mot je trouve une droite x=y+[500;600] avec cependant des valeurs qui monte a y+[1000;1500] Aucune valeurs n est aperçu en dessous de 500. Es-ce normal?

[koala01]

Comme l'a si bien fait remarquer daflab, le temps de recherche dans un arbre binaire de recherche (ce qui est réellement utilisé par une std::unordered_map) évolue de manière logarithmique par rapport au nombre d'élément.

C'est à dire que l'évolution du nombre d'éléments à tester va suivre à peu près le tableau qui suit:

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
nbre élém | éléments à tester (dans le pire des cas)
----------|--------------
      1   |       0
      2   |       1
      4   |       2
      8   |       3
     16   |       4
     32   |       5
     64   |       6
    128   |       7
    256   |       8
    512   |       9
   1024   |      10
   2048   |      11
   4096   |      12
   8192   |      14
  16384   |      15
   ...    | ...
4294967295|    32

Parce que, à chaque fois que l'on décide de prendre l'un des coté de l'arbre, on abandonne automatiquement la moitié des données restantes (c'est ce que l'on appelle la "dichotomie"). Il est donc tout à fait normal que tu ne voies pas d'évolution flagrante du temps de recherche, peu importe les éléments ajoutés à partir du moment où ta map en contient 512 et jusqu'à ce qu'elle finisse par en contenir 1024, parce que la dichotomie nous permet de retrouver le 724eme élément aussi vite que le 512eme .

On peut même aller plus loin en disant que plus tu auras d'éléments dans ta map, plus il faudra en ajouter pour voir l'évolution du temps nécessaire à retrouver un élément dedans. Et c'est, d'ailleurs, l'énorme avantage de ce genre de collection