Discussion :

[hurukan]

Salutations !!

J'ai essayé d'expliquer à mes élèves qu'il valait mieux utiliser des structures plutôt que des tableaux dans le cas où nous cherchions à trier des données qui sont liées entre elles de manière "logique": par exemple un tableau de scores obtenus
dans un jeu vidéo.

Il y a le nom du joueur qui est lié à son score: DAR 3000, FLA 2000,JUL 1000,JAS 5000 et DRA 4000...
Nous voudrions obtenir la liste des joueurs triée sur le score... si nous nous contentons de trier les scores antichronologiquement sans utiliser de structures nous voyons directement que les noms des joueurs ayant obtenu
ces scores ne sont plus cohérents par rapport à la situation initiale. Nous devons "rattrapper le coup" en attaquant l'autre tableau contenant les noms de la même manière que celui qui contient les scores.

Mon soucis c'est que les deux programmes, l'un utilisant les tableaux et l'autre utilisant les structures ont des "performances" similaires (j'utilise une manière de trier peu performante)... je n'arrive pas, avec cet exemple, à démontrer
que le mécanisme des structures en langage ANSI C nous permet, selon mon hypothèse, d'obtenir de meilleurs résultats que si nous utilisions un tableau pour chaque élément de la structure, mis à part au niveau du code source.
En effet, dans la version "tableau" il faut opérer "les échanges" des chaînes de caractères, chaque fois que nous avons découvert un élément plus grand dans le sous-ensemble des scores qui doivent être encore triés... dans la version
"structures", nous échangeons la structure complète en utilisant le mécanisme "de la variable temporaire"... je pensais que la fonction strcpy() était lente... pourtant les différences au niveau du temps d'exécution entre les deux
"versions" est quasiment identique...

"version tableaux"

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
 
// sauvegarder la valeur de tabScores[0]
 
tmp=tabScores[posFinale];			
strcpy(strTmp,tabNoms[posFinale]);
 
// placer dans tabScores[0] la valeur de tabScores[idxplusgrand]
 
tabScores[posFinale]=tabScores[idxplusgrand];
strcpy(tabNoms[posFinale],tabNoms[idxplusgrand]);
 
// placer la valeur de tabScores[0] dans tabScores[idxplusgrand]
 
tabScores[idxplusgrand]=tmp;
strcpy(tabNoms[idxplusgrand],strTmp);

"version structure"

Code :

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

1
2
3
4
5
 
struct s_Scores tmp;
tmp=NosScores[posFinale];
NosScores[posFinale]=NosScores[idxplusgrand];
NosScores[idxplusgrand]=tmp;

Je cherche à montrer que les tableaux permettent de regrouper plusieurs variables de mêmes type sous un même nom et que les structures permettent de regrouper plusieurs variables de types différents sous un même nom également. Cependant je pensais que l'utilisation des structures avaient aussi un impact sur l'accès en mémoire des "champs", ce qui apparemment n'est pas le cas.

Les crochets des tableaux [] et le 'point' des structures indiquent tous deux un déplacement à effectuer en mémoire à partir de l'adresse de base correspondant au nom du tableau ou de la structure...

tabNoms[3]: indique qu'il faut se déplacer de 3 fois la taille du type de tabNoms à partir de l'adresse de tabNoms
et NosScores[3].strNom indique qu'il faut se déplacer de 3 fois la taille de la structure correspondant à NosScores et de se déplacer sur le champs "strNom" à partir de l'adresse de NosScores

Code :

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

1
2
3
4
5
6
 
struct s_Scores
{
	int 	score;
	char 	strNom[4];
};

...donc dans notre exemple, nous devons "sauter" la taille d'un "int" pour accéder au champs "strNom" en mémoire...

Ma question est la suivante: laquelle de ces deux approches aurait une performance notable à l'exécution du programme qui les utilise, moi je n'en vois pas, et du coup si le mécanisme n'offre pas de meilleures performances, quels seraient les avantages de recourir à une structure plutôt qu'à des tableaux créés pour chaque "champs" à manipuler ?
Bon, ici je n'ai utilisé que deux tableaux tabScores et tabNoms, peut-être que si nous avions ajouté des champs supplémentaires, la nécessité du recours aux structures aurait été plus flagrante.

[chrtophe]

peut-être que si nous avions ajouté des champs supplémentaires, la nécessité du recours aux structures aurait été plus flagrante.

Tu répond toi-même à la question.

L'ajout d'un champ aura un impact ridicule de modification sur ton code.

Et avec ta structure tu peux faire une liste chainée en y intégrant des champs te permettant de facilement passer à l'élément suivant. Pour trier, tu as juste à mettre à jour les pointeurs de la liste chainée.

[foetus]

En effet, dans la version "tableau" il faut opérer "les échanges" des chaînes de caractères, chaque fois que nous avons découvert un élément plus grand dans le sous-ensemble des scores qui doivent être encore triés...

Version "Mickey - niveau 0" repérée

Si tu es un prof, c'est un peu dérangeant

Il faut trier une table d'indexes - ou une table de pointeurs soit vers des structures justement soit vers des maillons d'une liste chaînée

Et si tu es balèze tu as les versions plus sophistiquées :

• Version + : le tri bucket (Bucket sort <- lien Wiki), éventuellement le tri radix (Radix sort <- lien Wiki), si cela est possible, ou autre tri qui gère des tableaux d'ensemble
• Version +++ : table de hachage, B-Tree, ... mais là on se rapproche d'une base de données

[hurukan]

Oui je le dis moi-même l'exemple n'est pas forcément celui le mieux choisi... en général, pour valoriser les pointeurs, j'utilise un autre algorithme.
Il faut bien vous dire que j'ai des élèves de 17, 18 ans qui n'ont aucune expérience en programmation. Donc les listes chainées j'ai fait une librairie pour qu'ils puissent les utiliser mais je n'en parle que superficiellement aux cours (en sachant que les pointeurs certaines années je ne fait que le survoler, le chapitre).

Je sais qu'ici, et c'est la suite de la démonstration, il est possible d'obtenir des performances plus intéressantes si on trie les informations en constituant un tableau d'indexes (ou une liste)...

Dites vous bien que je suis en train d'essayer de "vendre" le mécanisme des structures, j'ai à peine abordé la notion de pointeurs avec les tableaux (autant numériques que les chaînes de caractères)... ne sautons pas les étapes, non plus.

[Sve@r]

Bonjour

ne sautons pas les étapes, non plus.

Ben tu es un peu quand-même en train de les sauter gravement les étapes. Tu as des élèves qui n'ont aucune expérience de programmation ; et au lieu de leur expliquer les bases du C (les pointeurs, les tableaux, les structures, leurs buts, leur utilisation) tu ne fais que survoler ces notions pourtant essentielles à la compréhension du langage et tu pars direct sur l'optimisation du code ; code auquel ils doivent comprendre que dalle !!!

Donc les listes chainées j'ai fait une librairie pour qu'ils puissent les utiliser

Ben oui mais non. Ton but c'est que ce soient eux qui arrivent à faire la librairie !!!

Nous voudrions obtenir la liste des joueurs triée sur le score... si nous nous contentons de trier les scores antichronologiquement sans utiliser de structures nous voyons directement que les noms des joueurs ayant obtenu
ces scores ne sont plus cohérents par rapport à la situation initiale. Nous devons "rattrapper le coup" en attaquant l'autre tableau contenant les noms de la même manière que celui qui contient les scores.

Ben oui. Mais même pas besoin de parler de "tri" pour expliquer ça. La structure est un outil qui sert à grouper des données diverses mais qui ont besoin d'avoir une notion d'atomicité. Exemple une date sera composée d'un jour, d'un mois et d'une année. Ces 3 éléments sont tous distincts mais ils ont besoin d'être regroupés pour que la notion de "date" puisse apparaitre et puisse se manipuler.

Dites vous bien que je suis en train d'essayer de "vendre" le mécanisme des structures

Pas besoin de "vendre" quoi que ce soit. Demande leur de gérer une date de naissance, de décès, de mariage et de divorce et quand ils en auront marre de se coltiner des "jj_naissance", "mm_naissance", "aa_naissance", "jj_deces", "mm_deces", "aa_deces", "jj_mariage", "mm_mariage", "aa_mariage", "jj_divorce", "mm_divorce", "aa_divorce" ils adhèreront à la structure tout seuls !!!

[hurukan]

Ben tu es un peu quand-même en train de les sauter gravement les étapes. Tu as des élèves qui n'ont aucune expérience de programmation ; et au lieu de leur expliquer les bases du C (les pointeurs, les tableaux, les structures, leurs buts, leur utilisation) tu ne fais que survoler ces notions pourtant essentielles à la compréhension du langage et tu pars direct sur l'optimisation du code ; code auquel ils doivent comprendre que dalle !!!

...je ne vais pas non plus m'étendre sur ce qu'ils savent déjà... nous sommes sur le projet depuis septembre.
cependant, lorsque j'estime que les tableaux de chaînes de caractères sont utiles pour pouvoir afficher des informations tangibles à l'écran, je "soulève" le concept des "pointeurs" sans entrer dans les détails car j'estime que c'est trop tôt pour en parler...
c'est pour cela que je dis que je "survole le concept" pour y revenir plus en profondeur lorsque l'agenda le permet... dans leurs études supérieures ils en boufferont des pointeurs, mais après avoir compris ce qui caractérise une variable et l'importance
du typage en C (et autres langages dérivés), ...

Je ne me focalise pas sur l'optimisation du code, j'étais parti de l'hypothèse que si on supprime les fonctions strcpy() du programme nous devrions "observer" que le programme s'exécute plus vite. Je me suis trompé. Mais aux cours je n'ai pas (encore) parlé de ces observations, ...

Ben oui mais non. Ton but c'est que ce soient eux qui arrivent à faire la librairie !!!

Non, justement, les listes chaînées c'est pas dans le programme des cours (même si j'en ai rien à foutre -- si je le suivais on ferait de la bureautique et du wordpress pendant deux ans, bonjour l'angoisse), je m'en sers juste comme outil... quand on utilise une fonction comme strtok() on l'utilise sans forcément essayer de comprendre en profondeur comment elle fonctionne ligne par ligne...
La librairie permettant l'utilisation des listes chaînées est mise à la disposition des élèves, je leur explique comment on l'utilise, dans quel cadre/contexte, comme j'expliquerais comment on utilise une fonction de la librairie glibc, sans plus.
Ils auront l'occasion de programmer/implémenter eux-mêmes les classes "container" quand ils verront les "templates" en C++ (types génériques) en seconde année dans leurs études supérieures, en tant que bacheliers et mangeront des listes triées, des piles et des structures de tous poils, en première année, pendant l'apprentissage plus approfondi du langage C.

Ben oui. Mais même pas besoin de parler de "tri" pour expliquer ça. La structure est un outil qui sert à grouper des données diverses mais qui ont besoin d'avoir une notion d'atomicité. Exemple une date sera composée d'un jour, d'un mois et d'une année. Ces 3 éléments sont tous distincts mais ils ont besoin d'être regroupés pour que la notion de "date" puisse apparaitre et puisse se manipuler.

Oui mon hypothèse n'est pas vérifiée, j'ai essayé un truc, et j'observe que les résultats sont similaires, je m'arrêterais donc sur ce que j'ai dis aux cours: les tableaux permettent de regrouper plusieurs variables du même type sous le même nom, et la structure vous permet de regrouper des variables de type différent sous un même nom de structure...

Définition utilisée aux cours...

Exercices proposés...

[foetus]

Déjà dire qu'une structure c'est le même principe qu'un tableau c'est n'importe quoi

La structure, comme l'a dit Sve@r, c'est de regrouper de façon logique des informations.

Un tableau c'est de regrouper dans un bloc contigüe des données afin d'être parcourues/ triées/ ajoutées - supprimées (avec la notion de complexité algorithmique)

Et d'ailleurs , même en C, tu peux faire également des tableaux génériques qui mélangent les types.

je "soulève" le concept des "pointeurs" sans entrer dans les détails car j'estime que c'est trop tôt pour en parler...

Et à propos, tu fais faire des structures voire même des structures de structures (ce qui ne veut dire pas grand chose ), mais tu enseignes les bonnes pratiques quand : initialisation, propriété, destruction
Déjà sans les pointeurs c'est mal barré

[Bktero]

Je pense surtout que ta volumétrie est tellement faible que le temps d'exécution n'est pas du tout représentatif. J'espère aussi que tu ne comptes pas le temps d'affichage car sinon le temps d'exécution sera a peu près le temps d'affichage.

[Sve@r]

J'espère aussi que tu ne comptes pas le temps d'affichage car sinon le temps d'exécution sera a peu près le temps d'affichage.

[dinobogan]

Bktero a soulevé un point très important : il faut d'abord être sûr que le chronométrage se fait au même endroit entre les deux programmes.
Ensuite, il faut largement augmenter la volumétrie. Calculer un temps de tri aussi petit n'a pas beaucoup de sens : la moindre perturbation de la machine (écriture disque, un autre programme qui se lance, ...) va fortement dégrader le temps d'exécution.
Selon ton processeur et ta façon de coder, le petit tableau à trier est même peut-être entièrement en cache processeur.

Pour ton test, augmente la taille du tableau jusqu'à avoir un temps d'exécution proche de 2 ou 3 secondes. Ce sera déjà plus flagrant comme chronométrage.
Ensuite, tu parles de strcpy et de ta surprise de sa vitesse d'exécution. Cette fonction est appelée environ une dizaine de fois pour trier un tableau de 5 éléments (environ car tu ne parles pas de ton algo de tri), donc le surcoût d'appel à une fonction externe est largement négligeable.

Pour le tri, peut-être la version du quicksort dans sa première version, en quelques lignes : tu pourras aborder facilement la récursivité, le temps de tri sera très bon et le code sera très court.

[Sve@r]

je pensais que la fonction strcpy() était lente... pourtant les différences au niveau du temps d'exécution entre les deux
"versions" est quasiment identique...

Moi je voudrais revenir sur cette phrase. Parce que, en fait, strcpy() est plus rapide. En effet, elle ne copie que le nombre d'octets utiles. Alors que copier une structure copiera toute la structure.

Exemple

Code c :

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

1
2
3
4
// Copie de chaine
char orig[1000]="toto";
char dest[1000];
strcpy(dest, orig);  // Ici recopie de 5 octets ('t', 'o', 't', 'o' et '\0')

Code c :

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

1
2
3
4
5
6
7
8
// Copie de structure
typedef struct {
    char str[1000];
} t_str;
 
t_str orig, dest;
strcpy(orig.str, "toto");
dest=orig;                 // Ici recopie de 1000 octets

La chose aurait été différente via memcpy()

Code c :

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

1
2
3
char orig[1000]="toto";
char dest[1000];
memcpy(dest, orig, 1000);  // Ici recopie de 1000 octets

Donc dans l'absolu, si tu veux aller très vite il te faut traiter tes chaines à part. Mais cela n'a de valeur que si tu as des chaines dans l'équation. Exemple

Code c :

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

1
2
3
4
// Copie de double
double orig;
double dest;
dest=orig;     // Ici recopie de 8 octets

Code c :

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

1
2
3
4
5
6
7
// Copie de structure
typedef struct {
    double dbl;
} t_str;
 
t_str orig, dest;
dest=orig;                 // Ici recopie de 8 octets