Discussion :

[Sh4dow49]

Bonjour à tous,

Voila je dois réaliser un programme en C effectuant un tri par fusion en utilisant les pthreads, et tout cela en 1semaine et sans connaître le C

on m'a donné le gros de l'algorithme à utiliser (que voici) :

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
83
84
85
86
87
88
89
90
91
92
93
 
#define SIZE_TAB 5
 
void fusion(int tableau[], int deb1, int fin1, int fin2);
void tri_fusion_bis(int tableau[], int deb, int fin, int count);
void tri_fusion(int tableau[], int longueur);
 
void affiche_tab(int *tab)
{
	int i;
	for (i = 0; i <= SIZE_TAB; i++)
	{
		printf (" %d ", tab[i]);
	}
}
 
void fusion(int tableau[], int deb1, int fin1, int fin2)
{
	int *table1;
	int deb2 = fin1 + 1;
	int compt1 = deb1;
	int compt2 = deb2;
	int i;
 
	printf (" [deb fusion] --> ");
	affiche_tab(tableau);
	printf("\n");
 
	table1 = malloc((fin1 - deb1 + 1) * sizeof(int));
 
	//on recopie les éléments du début du tableau
	for (i = deb1; i <= fin1; i++)
	{
		table1[i-deb1] = tableau[i];
	}
 
	printf (" cpy tableau \n");
	for (i = deb1; i <= fin2; i++)
	{
		printf (" Elements %d \n", i);
		if (compt1 == deb2)
		{
			printf (" Tous les éléments sont classés. \n");
			break;
		}
		else if (compt2 == fin2 + 1)
		{
			tableau[i] = table1[compt1 - deb1];
			compt1++;
		}
		else if (table1[compt1 - deb1] < tableau[compt2])
		{
			tableau[i] = table1[compt1 - deb1];
			compt1++;
		}
		else
		{
			tableau[i] = tableau[compt2];
			compt2++;
		}
	}
	free(table1);
 
	printf (" [fin fusion] --> ");
	affiche_tab(tableau);
	printf (" \n");
}
 
void tri_fusion_bis(int tableau[], int deb, int fin, int count)
{
	sleep(3);
 
	printf ("[%d] Itération debut %d fin %d \n", count, deb, fin);
 
	if (deb != fin)
	{
		int milieu = (fin + deb) / 2;
 
		tri_fusion_bis (tableau, deb, milieu, count + 1);
 
		tri_fusion_bis(tableau, milieu + 1, fin, count + 1);
 
		fusion(tableau, deb, milieu, fin);
	}
}
 
void tri_fusion(int tableau[], int longueur)
{
	if (longueur > 0)
	{
		tri_fusion_bis(tableau, 0, longueur - 1, -1); 
	}
}

1ère question : à quoi sert le "#define SIZE_TAB 5" au tout début ??

J'ai essayé de créer le main pour pouvoir utiliser le programme sans les threads dans un premier temps. J'ai donc fait un truc dans ce genre :

Code :

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

1
2
3
4
5
6
7
8
9
10
 
int main(void)
{
	int tableau[8] = {26, 7, 15, 6, 1};
	int longueur = sizeof(tableau);
 
	tri_fusion(tableau, longueur);
 
	return 0;
}

Lorsque je lance le programme, au début tout va bien a part un détail : il affiche 6 nombres alors que le tableau n'en contient que 5 (un zero apparait à la fin).

Ensuite, plus on avance, plus ça "part en live". les nombres du ableau sont au fur é a mesure remplacés par des zeros, seuls le 1 3 et 6 restent, et sont mis après trois zero.

Enfin une erreur se produit sur la fin

Code :

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

1
2
3
 
5 [main] a 1780 _cygtls::handle_exception: Error while dumping state (probably corrupted stack)
Segmentation fault (core dumped)

Je n'ai pas bien saisi l'erreur donc bon...

Pour info, je teste sous cygwin (un émulateur unix) en compilant le fichier via la commande gcc

Grand merci d'avance pour votre aide

[alaparra]

j'ai pas tout regardé mais essaye deja avec comme main :

Code :

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

1
2
3
4
5
6
7
8
9
10
11
 
 
int main(void)
{
	int tableau[5] = {26, 7, 15, 6, 1};
	int longueur = 5;
 
	tri_fusion(tableau, longueur);
 
	return 0;
}

[Sh4dow49]

En effet ca marche mieux

Mais toujours la meme question : à quoi sert la 1ère ligne "#define SIZE_TAB 5" car pour moi elle a un rapport avec la taille du tableau (je n'ai rien trouvé dessus donc je suis pas sur)

Et pourquoi ca marche si je donne une valeur directe à longueur et pas si je lui donne comme valeur le sizeof du tableau ?

J'essaye de comprendre pour pouvoir avancer ...

Merci d'avance pr les réponses

[Sh4dow49]

Autre remarque, il affiche 6 nombres, quelle que soit la taille du tableau

Si j'ai un tableau à 5 cases j'ai un 47 qui apparait à la fin du tableau, et si j'ai plus de 6 cases il n'affiche que les 6 premières

[Médinoc]

C'est parce que la fonction d'affichage est erronée.
Il faut:

1. remplacer le <= par <
2. soit utiliser SIZE_TAB correctement, soit passer la longueur en paramètre (de type size_t)
3. changer le type de i en size_t.

[Sh4dow49]

[*]soit utiliser SIZE_TAB correctement, soit passer la longueur en paramètre (de type size_t)[/LIST]

Justement, je ne sais pas à quoi sert ce SIZE_TAB ... pourrais-tu m'expliquer ?

[alaparra]

le sizeof(tableau) si je ne me trompe pas te donne la taille d'un int soit 4.
car faire sizeof(tableau) c'est comme faire sizeof(tableau[0]) soit la taille du premier element du tableau, soit la taille en memoire d'un entier.

le sizeof est utilisé pour avoir la taille memoire la ce qu'on te demande c'est le nombre d'elements de ton tableau.

ensuite le #define sert a definir la variable SIZE_TAB qui ser dans la fonction d'affichage de ton tableau et limite le nombre le nombre a SIZE_TAB ce qui est stupide.
la fonction d'affichage affiche SIZE_TAB element quoi qu'il arrive alors que la taille de ton tableau peu etre variable.

[Médinoc]

SIZE_TAB est une constante, égal à 5.
Partout où on utilise SIZE_TAB, on considère que c'est 5.

Donc, si je fais ceci:

Code C corrigé :

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

1
2
3
4
5
6
7
8
void affiche_tab(int const *tab)
{
	size_t i;
	for (i = 0; i < SIZE_TAB; i++)
	{
		printf (" %d ", tab[i]);
	}
}

Cette fonction supposera toujours que le tableau a une taille de 5. Si on change SIZE_TAB, ça affectera toutes les fonctions qui l'utilisent.

[Sh4dow49]

Ah ouai ok merci beaucoup je comprends mieux maintenant.

Su coup j'ai modifié mon programme pour qu'il fasse l'affichage en fonction de la longueur du tableau et non du SIZE_TAB (que j'ai enlevé).

Par contre, je ne trouve pas la syntaxe de la fonction foreach (qui me permettrait de récupérer la taille du tableau "dynamiquement", et non en affectant directement un nombre à la variable longueur, ce qui me permettrait par la suite d'essayer d'implémenter la saisie du tableau par l'utilisateur si j'ai le temps de trouver comment faire).

Je n'ai rien trouvé dans la FAQ du site, quelqu'un pourrait-il m'éclairer ? (une nouvelle fois ^^ )

Merci d'avance encore pour vos réponses qui me font vraiment avancer !

[Médinoc]

Tu ne peux.
Un tableau en C ne stocke pas sa taille, tu dois la mémoriser à part (ou utiliser une "valeur sentinelle", comme les chaînes de caractères).

[Sh4dow49]

erf c'est embêtant ça ...

Qu'appelles tu par "valeur sentinelle" ? Je ne vois pas trop ...

[Médinoc]

N'as-tu jamais appris ce qu'est une chaîne de caractères en langage C ?
C'est un tableau de char terminé par un char dont la valeur est zéro.
En clair, char str[] = "bonjour"; équivaut à:

Code C :

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

char str[] = {'b', 'o', 'n', 'j', 'o', 'u', 'r', 0};

Ici, ce caractère de valeur zéro, dit "caractère nul", est la valeur sentinelle pour les chaînes de caractères: Il signale la fin de la chaîne.

Et en fait, la fonction strlen(), qui retourne la longueur d'une chaîne, ne fait rien d'autre que compter les caractères jusqu'à la sentinelle.
Pour ceux qui connaissent un minimum la théorie de la complexité, c'est une opération linéaire (une opération en O(n), où n est le nombre de caractères de la chaîne) et non pas une opération en temps constant (une opération en O(1)). Traduit en clair, ça veut dire que plus la chaîne est longue, plus la fonction strlen() met du temps.

[Sh4dow49]

ah ok, merci pour l'explication.

Je ne connaissait pas trop le principe d'une chaine de caractère en C car je ne connais absolument rien en C (ce n'est pas moi qui ai choisi le langage).

Sinon j'avais une autre idée, une boucle while, dans laquelle on propose à l'utilisateur de saisir des entiers, et que tant qu'il n'a pas saisi (ou autre chose) on reste dans le while (ce qui lui permet de saisir autant de nombres qu'il le souhaite)
Comme ça il n'y a qu'à incrémenter la variable longueur une fois par tour dans la boucle.

Par contre je ne sais pas comment récupérer une valeur saisie dans la console (je me souviens du cin >> variable; en C++ mais ça ne passe pas en C donc ça doit être autre chose mais je ne trouve pas)

[Médinoc]

En c, pour saisir des valeurs numériques, le plus simple est d'utiliser la fonction scanf(), accompagnée de cette fonction du forum:

Code C :

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

1
2
3
4
5
6
7
8
9
10
/* Note: getchar() retourne EOF en cas d'erreur.
   Cette fonction lit les caractères jusqu'à la fin de la ligne,
   mais s'interrompt et retourne -1 en cas d'erreur. */
int purge(void)
{
	int c;
	while((c=getchar())!=EOF && c!='\n')
	{}
	return (c==EOF ? -1 : 0);
}

Mais pour ce qui est de l'incrémentation de la variable longueur, n'oublie pas que la taille d'un tableau sur la pile est fixe. Si tu veux pouvoir agrandir ton tableau à volonté, tu dois utiliser l'allocation dynamique (malloc(), free() et realloc()).

[Médinoc]

scanf() et purge() s'utilisent comme ça:

Code C :

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
#include <stdio.h>
 
int purge(void)
{
	int c;
	while((c=getchar())!=EOF && c!='\n')
	{}
	return (c==EOF ? -1 : 0);
}
 
int main(void)
{
	int valeur;
	int nScanned;
	print("Entrer la valeur : "), fflush(stdout);
	nScanned = scanf("%d", &valeur);
	purge();
 
	if(nScanned != 1)
		puts("Erreur!");
	else
		printf("Vous avez entre la valeur %d.\n", valeur);
	return 0;
}

[Sh4dow49]

sympa comme fonction, merci

Par contre, autre question : pour déclarer un tableau, est-on obligé de renseigner une taille maximum ou bien peut-on déclarer un tableau de longueur variable ? (si oui comment ! )

car du coup je voudrais permettre a l'utilisateur de saisir autant de valeurs qu'il le souhaite.

J'ai fait ceci :

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
 
while (temp != 0)
	{
		puts ("Veuillez saisir un nombre entier : "), fflush(stdout);
		nScanned = scanf("%d", &temp);
		purge();
 
		if (nScanned != 1)
		{
			puts ("erreur");
		}
		else
		{
			if (temp != 0)
			{
				printf ("\nVous avez saisi : %d\n", temp);
				tableau[longueur] = temp;
				longueur++;
			}
		}
	}

mais seul le tableau empeche la compilation car ma déclaration est simplement :

Code :

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

1
2
 
int tableau[];

S'il n'y a pas de solution tant pis je mettrai un grand nombre ...

Merci d'avance une nouvelle fois

[Médinoc]

On ne peut pas faire de manière simple un tableau de longueur variable.
Cela se fait de manière compliquée, avec l'allocation dynamique. Si tu n'as pas encore vu ce chapitre, je te déconseille de te lancer là-dedans prématurément.

[Sh4dow49]

Je te fais confiance alors ... j'écoute sans broncher les conseils de personnes plus compétentes que moi dans la matière ^^

Du coup je fais un simple "#define MAX_SIZE x" et je déclare mon tableau en mettant ce x entre les crochets et ça marche bien comme ça

[Sh4dow49]

Et donc maintenant que cela fonctionne, comment puis-je implémenter les pthread dans ce programme ?

Je n'ai vraiment aucune idée de comment faire


Merci encore pour vos réponses !

[Médinoc]

Pour bien faire, il faut mettre aussi MAX_SIZE entre les crochets.

Pour la décomposition en plusieurs threads, il faut réfléchir à ce qu'est le tri-fusion:

1. on trie une moitié (généralement aussi par tri fusion)
2. on trie l'autre moitié
3. On fusionne.

Seules les parties 1 et 2 peuvent être faites en parallèle.

Donc, tu peux répartir le tri sur un nombre de threads égal à une puissance de 2.
Exemple sur 2 threads:

• 1 thread A pour trier la première moitié
• 1 thread B pour trier la seconde moitié
• Puis, l'un des 2 threads (on va dire A) fusionne.

Exemple sur 4 threads:

• 1 thread A pour trier le premier quart
• 1 thread B pour trier le second quart
• 1 thread C pour trier le troisième quart
• 1 thread D pour trier le dernier quart
• Puis, l'un des deux threads A et B (on va dire A) fusionne les deux premiers quarts
• l'un des deux threads C et D (on va dire C) fusionne les deux derniers quarts
• Puis, l'un des threads qui fusionnaient (on va dire A) fusionne les deux moitiés