occurence des lettres

Le problème exposé dans ce sujet a été résolu.

But du programme : compter le nombre de fois que reviennent les lettres dans un tableau de char.

Ouvert a toute correction et critique ou amélioration. Merci

#include <iostream>
#include <vector>

int main ()
{
    std::vector<char> lettres { 'p', 'r', 'o', 'g', 'r', 'a', 'm', 'm', 'e', 'r', 'c', 'e', 's', 't', 'c', 'o', 'n', 'c', 'e', 'v', 'o', 'i', 'r', 'u', 'n', 'a', 'l', 'g', 'o', 'r', 'i', 't', 'h', 'm', 'e' };
    
    for (int i { 0 }; i < std::size(lettres); ++i)
    {
        int occurence_lettre { 0 };

        for(char lettre : lettres)
        {
            if (lettre == lettres [ i ] )
            {
                ++occurence_lettre;
            }
        }

        std::cout << lettres [ i ] << " revient " << occurence_lettre << " fois.\n";
    }

    return 0;
}

Non, il y a plein de choses qui ne vont pas.

Tu as un tableau avec plein de lettres. Ok, admettons.

Ton traitement devrait normalement lire tout ce tableau, faire des calculs, puis ENSUITE, quand les calculs sont finis, afficher des résultats.

Ici, si tout marche bien, ton programme va afficher

p revient 1 fois
r revient 1 fois 
o revient 1 fois
g revient 1 fois 
r revient 2 fois  
etc

A chaque lettre, ton programme va afficher une nouvelle ligne, éventuellement contradictoire avec ce qui a été dit avant (r apparait 1 fois, puis r apparait 2 fois …)

+1 -1

Salut,

Je ne sais pas ce qui est attendu de ton exercice, mais ici si je suis bien ton code le nombre de lettres est affiché plusieurs fois pour chaque lettre (à chaque occurrence de la lettre).

Et avec une structure de données plus adaptée tu devrais pouvoir obtenir une meilleure complexité que O(n²).

Comme gbdivers, ce que je vois est des plus étrange — ah! J’ai mis un moment pour voir que la RAZ du compteur et l’affichage étaient dans la première boucle, le résultat est donc semi-bon.

L’exercice habituel de constitution d’histograme, c’est du O(N). On fait une seule passe et on MAJ les k compteurs de lettres. A la fin, on affiche ce qu’on a trouvé. Avec k=256 (->tableau) en mode fainéant pur ASCII, voire moins si on veut gratter quelques octets, ou bien plus (table de hashage) pour le non ASCII, à priori pas le cas vu la restriction char. Bref.

Là, je vois une double boucle qui va rechercher et afficher plusieurs fois la même information. On est sur du O(N²), ce qui en plus n’est pas efficace.

Je ne sais pas ce qui est attendu de ton exercice, mais ici si je suis bien ton code le nombre de lettres est affiché plusieurs fois pour chaque lettre (à chaque occurrence de la lettre).

Et avec une structure de données plus adaptée tu devrais pouvoir obtenir une meilleure complexité que O(n²).

entwanne

Oui, le nombre de lettres est affiché plusieurs fois à chaque occurrence de la lettre.

Pour ce qui de l’exercice : on voulait afficher le nombre de fois que revient une lettre. Du coup on avait un code limité avec une seule lettre. Ainsi je voulais améliorer ce programme en affichant le nombre de fois que revient chaque lettre du tableau de char.

Je vais réécrire autrement pour qu’il ne soit pas répétitif.

+0 -0

Comme gbdivers,

lmghs

J’ai rien dit, je suis innocent !

En plus de ce qui a été dit, il y a des warnings a corriger :

Start
prog.cc:14:37: warning: implicit conversion changes signedness: 'int' to 'std::__1::vector<char, std::__1::allocator<char> >::size_type' (aka 'unsigned long') [-Wsign-conversion]
            if (lettre == lettres [ i ] )
                          ~~~~~~~   ^
prog.cc:20:32: warning: implicit conversion changes signedness: 'int' to 'std::__1::vector<char, std::__1::allocator<char> >::size_type' (aka 'unsigned long') [-Wsign-conversion]
        std::cout << lettres [ i ] << " revient " << occurence_lettre << " fois.\n";
                     ~~~~~~~   ^
prog.cc:8:25: warning: comparison of integers of different signs: 'int' and 'decltype(__c.size())' (aka 'unsigned long') [-Wsign-compare]
    for (int i { 0 }; i < std::size(lettres); ++i)
                      ~ ^ ~~~~~~~~~~~~~~~~~~
3 warnings generated.
+1 -0

En plus de ce qui a été dit, il y a des warnings a corriger :

Start
prog.cc:14:37: warning: implicit conversion changes signedness: 'int' to 'std::__1::vector<char, std::__1::allocator<char> >::size_type' (aka 'unsigned long') [-Wsign-conversion]
            if (lettre == lettres [ i ] )
                          ~~~~~~~   ^
prog.cc:20:32: warning: implicit conversion changes signedness: 'int' to 'std::__1::vector<char, std::__1::allocator<char> >::size_type' (aka 'unsigned long') [-Wsign-conversion]
        std::cout << lettres [ i ] << " revient " << occurence_lettre << " fois.\n";
                     ~~~~~~~   ^
prog.cc:8:25: warning: comparison of integers of different signs: 'int' and 'decltype(__c.size())' (aka 'unsigned long') [-Wsign-compare]
    for (int i { 0 }; i < std::size(lettres); ++i)
                      ~ ^ ~~~~~~~~~~~~~~~~~~
3 warnings generated.

gbdivers

Ah okay je n’avais pas vu les warnings vu que mon compilateur ne les affiche pas. Merci sur ce point

+0 -0

Ah okay je n’avais pas vu les warnings vu que mon compilateur ne les affiche pas. Merci sur ce point

amalure

Il faut configurer son compilateur pour avoir un maximum d’avertissement. Pour Gcc et Clang, les principaux sont -Wall, -Wextra et j’ajoute aussi -pedantic.

J’ai un dépôt qui catégorise les options par version de compilateur et fournit des fonctions pour différents systèmes de build (dossier output): https://github.com/jonathanpoelen/cpp-compiler-options

Comme vous me l’avez dit, j’ai activé les avertissements et corrigé la majorité. Bref je n’arrive pas a comprendre ce message du compilateur :

/usr/bin/ld: test.out: _ZSt4cout: version invalide 2 (max 0)
test.out : erreur lors de l'ajout de symboles : Mauvaise valeur
collect2: error: ld returned 1 exit status

En particulier la première et la deuxième ligne

+0 -0

A mon avis, mes amis sont trop ambitieux.

Ton algorithme est en O(n²), alors qu’il y a des solutions en O(n) : C’est vrai, mais avançons étape par étape. D’ailleurs, sais-tu ce que ça veut dire, qu’un algorithme est en O(n²) ?

A mon avis, l’étape n°1, c’est de faire un traitement qui donne le bon résultat. Et de soumettre le code.

Ensuite, sur cette base, on pourra travailler. On pourra te dire : efface tout, ton algorithme est beaucoup trop lent. Ou bien on pourra te dire : regarde les warnings, l’algorithme fonctionne, mais il y a des détails qui ne sont pas bons. Mais vouloir faire un truc parfait, alors que visiblement, tu es archi-débutant, ça me paraît décalé.

Dans ton dernier message, tu montres des warnings. Ce sont des warnings qui correspondent au code du 1er message, ou bien tu as changé quelque chose?

Dans ton dernier message, tu montres des warnings. Ce sont des warnings qui correspondent au code du 1er message, ou bien tu as changé quelque chose?

elegance

Oui j’ai changé mon code (j’ai toujours l’ancien code avec quelques modifications : la raison est que je voulais rectifier les warnings soulevés avant de faire mieux) comme ci-dessous :

#include <iostream>
#include <vector>

int main ()
{
    std::vector<char> lettres { 'r', 'e', 'n', 't', 'r', 'e' };
    
    for (unsigned int i { 0 }; i < std::size(lettres); ++i)
    {
        int occurence_lettre { 0 };

        for (unsigned int j { 0 }; j < std::size(lettres); ++j)
        {
            if (lettres [ i ] == lettres [ j ] )
            {
                ++occurence_lettre;
            }
        }

        std::cout << lettres [ i ] << " revient " << occurence_lettre << " fois.\n";
    }

    return 0;
}

De même que je compile souvent mes codes depuis la console. Du coup voici ce que j’ai fait pour le compiler (Je ne sais pas si le problème vient des commandes de compilation) :

g++ -std=c++17 test.cpp -o -Wall -Wextra -pedantic test.out

Et mon compilateur affiche le message ci-dessous :

/usr/bin/ld: test.out: _ZSt4cout: version invalide 2 (max 0)
test.out : erreur lors de l'ajout de symboles : Mauvaise valeur
collect2: error: ld returned 1 exit status

Ton algorithme est en O(n²), alors qu’il y a des solutions en O(n) : C’est vrai, mais avançons étape par étape. D’ailleurs, sais-tu ce que ça veut dire, qu’un algorithme est en O(n²) ?

elegance

D’après ce que j’ai compris d’ici, je pense que c’est un algorithme qui n’est pas efficace puisqu’il se répète en faisant le même traitement d’informations deux fois. En tout cas je suis en train de faire une recherche sur le sujet. Des éclaircissements sur ce dernier seraient aimables.

Ensuite, sur cette base, on pourra travailler. On pourra te dire : efface tout, ton algorithme est beaucoup trop lent. Ou bien on pourra te dire : regarde les warnings, l’algorithme fonctionne, mais il y a des détails qui ne sont pas bons. Mais vouloir faire un truc parfait, alors que visiblement, tu es archi-débutant, ça me paraît décalé.

elegance

Oui c’est vrai je suis archi-débutant pour le moment mais avec le temps je pourrai peut-être améliorer cet algorithme et le rendre encore plus efficace. Vouloir faire parfaitement peut être vu aussi comme faire au moins quelque chose de bon sans forcément prétendre la perfection. Bref je suis à des kilomètres derrière un résultat parfait voire bon et je suis parfaitement conscient de ceci.

Merci à vous sinon

+0 -0

Mon diagnostic était le bon… "le même traitement d’information 2 fois" : non, ce n’est pas du tout ça qu’on entend quand on parle de complexité en O(n²).

Partons d’une chaine de 1000 caractères par exemple. Le traitement va prendre un certain temps T (Quelques millièmes de secondes).

Et maintenant, relançons le traitement avec une chaine 10 fois plus longue, une chaine de 10000 caractères. Avec ton algorithme, le traitement va etre 100 fois plus long que dans la 1ère situation. On multiplie le volume de données à traiter par 10, et le temps de traitement est multiplié par 10²=100. Et donc, on parle de complexité en O(n²).

Avec un algorithme bien écrit, sur cet exercice précis, quand on multiplie la taille de la chaîne par 10, le temps de traitement doit être multiplié par 10 seulement, et pas par 100.

C’était pour répondre à tes interrogations. Mais oublie tout ça, tu as des tas de choses à apprendre avant de parler de complexité d’algorithmme. Clairement, si tu ressors ces trucs sur la complexité en O(n²), tout le monde autour de toi va voir que tu parles d’un truc qui te dépasse complètement.

Le programme que tu testes actuellement est le même ou quasiment que celui du début. Il donne un résultat FAUX. Fais déjà en sorte qu’il donne un résultat juste. Que ce soit optimisé ou pas, peu importe à ce stade.

Partons d’une chaine de 1000 caractères par exemple. Le traitement va prendre un certain temps T (Quelques millièmes de secondes).

Et maintenant, relançons le traitement avec une chaine 10 fois plus longue, une chaine de 10000 caractères. Avec ton algorithme, le traitement va etre 100 fois plus long que dans la 1ère situation. On multiplie le volume de données à traiter par 10, et le temps de traitement est multiplié par 10²=100. Et donc, on parle de complexité en O(n²).

Avec un algorithme bien écrit, sur cet exercice précis, quand on multiplie la taille de la chaîne par 10, le temps de traitement doit être multiplié par 10 seulement, et pas par 100.

elegance

Bon jusqu’à là je vous suis et comprends très bien vos propos.

Le programme que tu testes actuellement est le même ou quasiment que celui du début. Il donne un résultat FAUX. Fais déjà en sorte qu’il donne un résultat juste. Que ce soit optimisé ou pas, peu importe à ce stade.

elegance

Je voulais juste corriger les warnings (vu qu’ils étaient dus au fait que le programme faisait des comparaisons entre deux types différents). Le seul message que le compilateur m’affiche est celui vu plus haut et que je n’arrive pas à comprendre. j’ai fait le test et d’après ce que je vois ça marche (mais il y a toujours ce message) :

r revient 2 fois.
e revient 2 fois.
n revient 1 fois.
t revient 1 fois.
r revient 2 fois.
e revient 2 fois.

Clairement, si tu ressors ces trucs sur la complexité en O(n²), tout le monde autour de toi va voir que tu parles d’un truc qui te dépasse complètement.

elegance

Perso c’est la première fois que j’entends la complexité en O(n²) grâce à toutes ces réponses, j’ai seulement eu une certaine idée en lisant les avis des autres sur mon code et c’était elle (idée) que je t’avais donnée comme définition.

Bon j’ai l’impression d’avoir oublier de préciser que je suis débutant que ce soit dans ce langage ou encore en informatique avant de poster ce sujet et préciser certains points.

+0 -0

Pour ce qui est du message d’erreur sur

g++ -std=c++17 test.cpp -o -Wall -Wextra -pedantic test.out

J’ai personnellement pris l’habitude que ce qui suit le -o doit être le nom de l’exécutable. Je ne sais pas si l’erreur vient de là. Sinon, vu que je suis sur des systèmes GNU bien configurés (i.e. pas MinGW, là c’est la loose), je compilerai même (indirectement, merci mon IDE — gvim) avec

# Attention impératif de pas de fichier `Makefile` dans le répertoire courant
CXXFLAGS='-std=c++17 -Wall -Wextra -pedantic` make test

Voire en mode abusé

export CXXFLAGS='-std=c++17 -Wall -Wextra -pedantic`
# Sans Makefile toujours
make test
# corrige le code
make test
# yeah ça compile
./test
# mais les résultats ne sont pas bons, donc corrige puis
make test
Code "faux" & pas KISS la complexité

Il donne un résultat FAUX

Où voyez-vous (vu que vous êtes deux) qu’il est faux? Pour chaque lettre, l’ensemble des lettres est parcouru "deux" fois, et en commençant à 0, la lettre courante est bien comptée une et une seule fois quand i == j. C’est moi qui ne suis pas réveillé?

Après, il y a bien un hic : un même résultat est affiché k fois. Il manquerait un | sort -u

Et quand bien même il serait faux, cela ne peut que me renforcer dans le besoin de la simplification de l’algo. Entre un algo simple et un complexe qui fait la même chose, je pense que l’on a tous appris (avec l’expérience) l’importance de la simplicité. Ce n’est pas une question d’optimisation. Et si on veut virer la redondance, à part sortir des enclumes pour stocker les résultat et enchainer sur sort + uniq, on en revient à la version type en O(N).

Est-ce moi qui associe simplicité avec table associative ici dans ce kata bien éprouvé?

Accessoirement, je range l’algorithmie dans les bases du développement, et dans l’algorithmie les notions de complexité. Et cet exo (résolu par l’OP dans sa forme maladroite) est un exemple type de kata algorithmique. Je suis quelque peu surpris du message de ne pas s’embêter avec ça.

@OP, "complexité" en trop peu de mots

Pour faire simple quand pour réaliser quelque chose :

  • si on trouve directement, on parle de O(1)
  • si il faut faire une/quelques boucles de k*N+a itérations fictives (k et x nombres constants), on parle de O(N) car la quantité de traitements est fonction linéaire du nombre d’itérations N
  • si on a 2, 3, 4, 42… boucles l’une après l’autre, on est O(N) toujours — je passe les cas où le nombre d’éléments n’est pas exactement le même, ce qui est le cas de l’algo type de calcul + exploitation d’histogramme
  • si on a 2 boucles imbriquées, là ça multiplie: O(N x N) -> O(N²)
  • si on a 3 boucle imbriquées, là ça multiplie: O(N x N x N) -> O(N3) — on rejoint ce qu’à expliqué mon voisin du dessus, pour 10 éléments en plus, on se prend un x100 (en N²), un x1000 en N3, etc
  • et il y a les cas de compléxités polynomiale O(NM) — arg!
  • et les cas de recherche dichotomique: quand on peut couper la poire en deux (cf l’exo de recherche d’un nombre entre 1 et 100 qui peut se faire en 7 coups max) -> O(ln N) — voire les tris efficaces en O(N ln N), etc

Après, les difficultés, c’est que les algos se mêlent avec des structures de données qui vont nous aider à mémoriser de façon plus ou moins intuitive des résultats intermédiaires.

Ici, on passe à la complexité inférieure en utilisant des tables associatives, qui de préférence permettent de faire l’association {lettre -> nombre d’occurrences de la lettre} en un coup (i.e en O(1))

J’ai personnellement pris l’habitude que ce qui suit le -o doit être le nom de l’exécutable. Je ne sais pas si l’erreur vient de là.

lmghs

Oui l’erreur venait de là, j’ai donc compilé comme ceci :

g++ -std=c++17 test.cpp -Wall -Wextra -pedantic -o test.out

et c’est résolu l’erreur précédente. Merci sur ce point.

Pour info, je n’ai pas dit qu’il est faux mais a part que ça marche et que j’ai toujours le message (message dû au fait que je n’ai pas mis l’exécutable après l’option -o comme l’avez précisé).

+0 -0
Connectez-vous pour pouvoir poster un message.
Connexion

Pas encore membre ?

Créez un compte en une minute pour profiter pleinement de toutes les fonctionnalités de Zeste de Savoir. Ici, tout est gratuit et sans publicité.
Créer un compte