Discussion :

[Syuhkua]

Bonjour à tous,

Comme l'indique le titre, mon problème est le suivant :

Je cherche à trouver les occurrences de chaque valeur dans un tableau de données.


Le problème est qu'ici je sors toutes les valeurs du tableau "TabClasse" ainsi que les occurrences de chaque valeur de manière récursive.

L'objectif est de pouvoir tracer le nombre de classe en fonction de leur fréquence. Donc avoir en sortie deux tableaux : un qui contient toutes les classes "écrites" une seule fois avec un tableau qui contenant leurs fréquences.

Le code que j'ai écrit :

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
for(i = 0; i < n ; i++) TabFreq[i] = 0 ;
 
for(i = 0; i < n ; i++)
{
 
    for(j = 0; j < n ; j++)
    {
        if(TabClasse[i] == TabClasse[j])
        TabFreq[j] += 1;
 
    }
 
 
    cout << "\nClasse " << TabClasse[i] << " : " << TabFreq[i] << "fois" << endl ;
 
 
}

En vous remerciant par avance,

Syuhkua

[foetus]

C'est l'erreur classique du Padawan

Prenons un exemple
Si ton tableau TabClasse est |1|2|1|2|1|1|1|1|2|

ton tableau TabFreq ne peut avoir une taille de 9, mais de 2.
Et de plus il faut un tableau associatif: |1 -> 6|2 -> 3|

Cela va aussi éviter de faire un parcours en n²

Et suivant l'algo, ce n'est pas déconnant de mettre la fréquence dans tes classes

[Syuhkua]

Merci de ta réponse; bien que tout ne soit pas clair.

La sortie de résultats que je voudrais serait la suivante :

Numéro de classe : Fréquence :
0 12
1 19
2 9
3 54
... ...

Mon idée est donc de parcourir mon tableau TabTrie qui contient des valeurs triées en ordre croissant (0,0,0, 1,1,1,1,1,2,2,3,3...)
Si les valeurs i et i+1 sont identiques alors on incrémente le "compteur_occurrence"
Lorsque la condition n'est plus remplie, je voudrais obtenir le numéro la classe précédente ainsi que son nombre d'occurrence
Le tout sortant dans un fichier.

Mon idée est donc d'utiliser la fonction push_back des vectors.

Mais je n'obtiens que des 0 ou des valeurs abérrantes.


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
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
for(i = 0; i < compteur_tirage ; i++) TabFreq[i] = 0 ;
 
 
	for(i = 0; i < compteur_tirage ; i++)
	{
 
		for(j = 0 ; j < compteur_tirage ; j++)
		{
			if(TabTrie[i] == TabTrie[j])
			{
				compteur_occurrence += 1 ;
 
			}
			else
			{
				TabNumClasse.push_back(TabTrie[i-1]) ;
				TabFreq.push_back(compteur_occurrence) ;
 
				Format(TabNumClasse[i], temp2); fputs(temp2, CS); fputs("\t", CS);
				Format(TabFreq[i], temp2); fputs(temp2, CS); fputs("\n", CS);
 
				cout << "\nNuméro de classe " << TabNumClasse[i] << " : " << TabFreq[i] << endl ;
 
			}
 
		}
 
	}

Merci pour votre aide

[foetus]

Réponse en vrac:
1) Donc tu ne connais pas la complexité des algorithmes

Tu as 2 boucles for imbriquées. Ta complexité est de n² est c'est très mauvais
Imagine que compteur_tirage vaut 1000. Tu vas faire 1000 x 1000 tours de boucles

2) Dans ton deuxième algo jamais tu remets à jour la variable compteur_occurrence à zéro

3) Trier ton tableau avant. Ce n'est pas vraiment une bonne idée. Le meilleur algo de tri a une complexité log2(n).
Tu vas me dire qu'avec un parcours en n² c'est cacahuète

Ce qu'il faut faire c'est utilisé un std:map: c'est un tableau associatif

Code :

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

1
2
3
4
5
6
7
8
9
10
1) Tu crées ton std:map et tu l'initialises à zéro
2) Pour count: de 1 à compteur_tirage
2.a) Tu prends dans ton std:map l'élément Tab[count]
-> La bibliothèque std a bien faite les choses. Si l'élément Tab[count] n'existe pas, elle le crée.
Après il faut tester la valeur de la fréquence associée

2.b) Tu incrémentes de 1 la fréquence qui est associée avec l'élément Tab[count]

3) Avec un itérateur tu parcours ton std:map
-> La bibliothèque std a bien faite les choses. Avec des entiers, tout est trié ... en théorie

[Iradrille]

Le meilleur algo de tri a une complexité log2(n).

Complexité linéaire pour le meilleur (il faut, au minimum parcourir tous les éléments) : O(n).
Mais généralement un tri se fait en O(n * log2(n)).

Sinon comme dit @foetus, tu n'as pas besoin de trier tes données, compter les occurrences c'est une opération en O(n) sur un tableau non trié (avec un unordered_map, O(n * log(n)) en utilisant une map), et en O(m * log2(n)) sur tableau trié (m le nombre de valeurs différentes, n la taille tu tableau, avec une unordered_map et pareil O(m * log2(n)²) avec une map)

Si tu as besoin d'avoir tes données triées par la suite, alors oui tu peux trier avant de compter les occurrences, sinon c'est plus coûteux.

Globalement ça donne:

Code :

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

1
2
3
4
5
std::map<TabClasseType, int> occurences;
std::foreach(TabClasse.begin(), TabClasse.end(), [&occurences](const TabClasseType& item) { ++occurences[item]; });
std::foreach(occurences.begin(), occurences.end(), [](const std::pair<TabClasseType, int>& item) {
   std::cout << "Item " << item.first << ": " << item.second << " occurences\n";
});

[robinsondesbois]

Bonjour,

Si ton tableau est contient des valeurs continues tu peut utiliser cet algo en O(n).

Code :

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

1
2
3
4
int tab[20] = {1,1,5,4,3,6,1,5,9,6,3,5,8,7,4,6,3,2,1,6};
int tabOccurrence[10] = {0};
for (int i=0; i<20; i++)
	tabOccurrence[tab[i]]++;