Discussion :

[Sh4dow49]

Si j'ai bien compris ce que tu me dis, la création des thread se fera donc dans la fonction tri_fusion_bis (cf commentaires)

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
 
void tri_fusion_bis(int tableau[], int deb, int fin, int count, int longueur)
{
	sleep(3);
 
	printf ("[%d] Itération debut %d fin %d \n", count, deb, fin);
 
	if (deb != fin)
	{
		int milieu = (fin + deb) / 2;
 
		//ici on crée un thread à la place
		tri_fusion_bis (tableau, deb, milieu, count + 1, longueur);
 
		//ici un autre à la place
		tri_fusion_bis(tableau, milieu + 1, fin, count + 1, longueur);
 
		//on attends que les deux aient fini pour fusionner
		fusion(tableau, deb, milieu, fin, longueur);
	}
}

Par contre je ne vois pas comment créer ces thread.

J'avais un exemple basique qui donnait 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
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
 
#include <stdio.h>
#include <pthread.h>
 
static void *task_a (void *p_data)
{
	puts ("hello word A");
 
	(void) p_data;
	NULL;
}
 
static void *task_b (void *p_data)
{
	puts ("Hello word B");
 
	(void) p_data;
	NULL;
}
 
int main (void)
{
	pthread_t ta;
	pthread_t tb;
 
	puts ("maint init");
 
	pthread_create (&ta, NULL, task_a, NULL);
	pthread_join(ta, NULL);
	pthread_create (&tb, NULL, task_b, NULL);
	pthread_join(tb, NULL);
 
	puts ("main end");
 
	return 0;
}

Dans cet exemple, j'ai bien compris comment ca se passe, on crée deux thread qui appellent les fonctions task_a et task_b, mais je n'arrive pas à retranscrire cet exemple dans mon cas...

[Médinoc]

Typiquement, inutile de créer deux nouveaux threads: Il suffit d'utiliser l'existant et de n'en créer qu'un seul nouveau...

Code pseudocode :

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

1
2
3
4
5
6
7
8
9
10
FONCTION TriFusion($liste)
	SI( un certain critère, comme la taille de la liste à traiter,
	    ou un nombre limite de threads )
		$esclave = NouveauThread(TriFusion, SecondeMoitie($liste))
		$premiere_moitie_triee = TriFusion(PremiereMoitie($liste))
		$seconde_moitie_triee = AttendreFin($esclave)
	SINON
		$premiere_moitie_triee = TriFusion(PremiereMoitie($liste))
		$seconde_moitie_triee = TriFusion(SecondeMoitie($liste))
	RETOUR Fusion($premiere_moitie_triee, $seconde_moitie_triee)

[Sh4dow49]

Je vois rapidement ce que tu veux dire mais certains trucs font que je ne vois absolument pas comment traduire :

quand tu mets :

Code :

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

$esclave = NouveauThread(TriFusion, SecondeMoitie($liste))

je traduis par la fonction pthread_create, mais je ne vois pas comment générer le thread car je ne vois pas ce que représente la fonction SecondeMoitie($liste) dans le tri fusion ... (idem pour la focntion PremiereMoitie($liste))

Si je ne me trompe pas, l'autre partie de la création, le "TriFusion" est le rappel de la fonction dans laquelle on se trouve, afin d'effectuer les échanges si besoin ...

Enfin, le ELSE, si j'ai bien compris, tu récupère dans les variables le résultat de la fonction TriFusion qui a en paramètre la fonction PremiereMoitie ou SecondeMoitie (selon la variable).

En fait je ne saisis pas l'enchainement ... Pourrais-tu me faire une trace de ce que tu m'a proposé ? Cela m'aiderai à comprendre je pense

En tout cas merci de m'aider !

[Médinoc]

PremiereMoitie() et SecondeMoitie() doivent être des fonctions permettant d'isoler les deux moitiés d'une liste. Cela peut être des copies complètes des deux moitiés, ou bien simplement des pointeurs sur la liste passée en entrée...

En fait, si la condition est satisfaite,

• le thread courant lance un nouveau thread qui fait le tri-fusion de la seconde moitié de la liste, et pendant ce temps, le thread courant fait un tri-fusion de la première moitié (oui, c'est un appel récursif).
• Puis quand le thread courant a fini sa part du tri, il prend le résultat du second thread (et l'attend s'il n'a pas encore fini)
• Puis il fait la fusion des deux résultats de tri.

Sinon, le thread courant va simplement trier les deux moitiés de la liste l'une après l'autre et faire la fusion ensuite.

[Sh4dow49]

Donc en fait si je reprends avec mon code (tu m'arretes si je me trompes, car j'ai du mal a l'implémenter, sans connaitre le langage c'est dur ... )

ma fonction tri_fusion :

Code :

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

1
2
3
4
5
6
7
8
 
void tri_fusion(int tableau[], int longueur)
{
	if (longueur > 0)
	{
		tri_fusion_bis(tableau, 0, longueur - 1, -1, longueur);
	}
}

A la place de l'appel de la fonction tri_fusion_bis, je crée un 1er thread qui exécutera la fonction tri_fusion_bis


Ensuite la fonction tri_fusion_bis :

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
 
void tri_fusion_bis(int tableau[], int deb, int fin, int count, int longueur)
{
	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, longueur);
 
		tri_fusion_bis(tableau, milieu + 1, fin, count + 1, longueur);
 
		fusion(tableau, deb, milieu, fin, longueur);
	}
}

dans le IF, à la place des appels fonctions je crée :
- un thread qui va trier la 1ère moitié
- un autre qui va trier la 2e moitié

les deux nouveaux thread réutilisent donc la même fonction tri_fusion_bis, ce qui aura donc pour effet de refaire le test et recréer deux threads pour avoir des tableaux de plus en plus petits.

J'attends la fin de l'exécution des thread à chaque fois pour lancer l'appel de la fonction fusion.

Est-ce que j'ai bon ? (sous entendu est-ce que j'ai compris )

Sur le papier je pense que cela marche, le plus dur reste la création des thread. Je sais que c'est la fonction pthread_create qu'il faut utiliser mais meme en cherchant sur le net je ne comprends pas trop comment l'utiliser.

Je sais par contre que la fonction pthread_join sert à attendre la fin de l'exécution d'un thread et qu'il faut renseigner le nom du thread et la fonction qu'il est en train d'utiliser (si je ne me trompe).

Quel est votre avis ? (pour le cas ou d'autres voudraient intervenir, même si l'aide de Médinoc m'est déjà très utile pour comprendre ! )

[orfix]

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.
<...>

Tu te trompe ...

The sizeof operator
<...>
When applied to an operand that has array type, the result is the total number of bytes in the array
<...>

[Médinoc]

Donc en fait si je reprends avec mon code (tu m'arretes si je me trompes, car j'ai du mal a l'implémenter, sans connaitre le langage c'est dur ... )

ma fonction tri_fusion :

Code :

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

1
2
3
4
5
6
7
8
 
void tri_fusion(int tableau[], int longueur)
{
	if (longueur > 0)
	{
		tri_fusion_bis(tableau, 0, longueur - 1, -1, longueur);
	}
}

A la place de l'appel de la fonction tri_fusion_bis, je crée un 1er thread qui exécutera la fonction tri_fusion_bis


Ensuite la fonction tri_fusion_bis :

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
 
void tri_fusion_bis(int tableau[], int deb, int fin, int count, int longueur)
{
	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, longueur);
 
		tri_fusion_bis(tableau, milieu + 1, fin, count + 1, longueur);
 
		fusion(tableau, deb, milieu, fin, longueur);
	}
}

Cette partie m'a l'air correcte, sauf que:

• je commencerais count à 0 plutôt qu'à -1.
• Pour les variables deb, fin, milieu et longueur, j'utiliserais le type size_t plutôt que int.

dans le IF, à la place des appels fonctions je crée :
- un thread qui va trier la 1ère moitié
- un autre qui va trier la 2e moitié

Non. Relis ce que j'ai dit plus haut.
Si le thread de départ en crée deux autres et les attend, on se retrouve avec trois threads dont l'un ne fait rien d'autre qu'attendre.
Au lieu de ça, si le thread de départ crée UN autre thread et fait une moitié du travail lui-même, il n'y aura pas de gachis...

les deux nouveaux thread réutilisent donc la même fonction tri_fusion_bis, ce qui aura donc pour effet de refaire le test et recréer deux threads pour avoir des tableaux de plus en plus petits.

En intégrant la correction que j'avais faite, ça y ressemble, mais n'oublie pas qu'il faut limiter cela, car au bout d'un moment on perd plus de temps à créer les threads qu'à calculer.

J'attends la fin de l'exécution des thread à chaque fois pour lancer l'appel de la fonction fusion.

Oui.

Sur le papier je pense que cela marche, le plus dur reste la création des thread. Je sais que c'est la fonction pthread_create qu'il faut utiliser mais meme en cherchant sur le net je ne comprends pas trop comment l'utiliser.

Je sais par contre que la fonction pthread_join sert à attendre la fin de l'exécution d'un thread et qu'il faut renseigner le nom du thread et la fonction qu'il est en train d'utiliser (si je ne me trompe).

On complètera ça quand tu auras parfaitement compris l'algorithme.
De plus, comment comptes-tu faire ta fusion exactement ? N'oublie pas que faire la fusion en in-place est assez peu efficace...

[Sh4dow49]

Ben en fait, je te remets le code qu'on m'a donné et sur lequel je suis parti (légèrement modifié):

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
94
95
96
97
 
#include <stdio.h>
#include <pthread.h>
 
#define MAX_SIZE 20
 
void fusion(int tableau[], int deb1, int fin1, int fin2, int longueur);
void tri_fusion_bis(int tableau[], int deb, int fin, int count, int longueur);
void tri_fusion(int tableau[], int longueur);
 
void affiche_tab(int *tab, int longueur)
{
	int i;
	for (i = 0; i < longueur; i++)
	{
		printf (" %d ", tab[i]);
	}
}
 
void fusion(int tableau[], int deb1, int fin1, int fin2, int longueur)
{
	int *table1;
	int deb2 = fin1 + 1;
	int compt1 = deb1;
	int compt2 = deb2;
	int i;
 
	printf (" [deb fusion] --> ");
	affiche_tab(tableau, longueur);
	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, longueur);
	printf (" \n");
}
 
void tri_fusion_bis(int tableau[], int deb, int fin, int count, int longueur)
{
 
	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, longueur);
 
		tri_fusion_bis(tableau, milieu + 1, fin, count + 1, longueur);
 
		fusion(tableau, deb, milieu, fin, longueur);
	}
}
 
void tri_fusion(int tableau[], int longueur)
{
	if (longueur > 0)
	{
		tri_fusion_bis(tableau, 0, longueur - 1, -1, longueur);
	}
}

Pour réaliser la fusion, j'utilise donc la fonction du même nom qui se charge en même temps de trier (on trouve les mêmes codes sur internet, j'ai juste ajouté une fonction main permettant d'utiliser le code)


Pour reprendre sur la fonction tri_fusion_bis :

Au lieu de ça, si le thread de départ crée UN autre thread et fait une moitié du travail lui-même, il n'y aura pas de gachis...

Je ne crée donc qu'un seul thread et pour l'autre moitié je laisse l'appel fonction d'elle même, en gros un truc du genre :

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
 
void tri_fusion_bis(int tableau[], int deb, int fin, int count, int longueur)
{
	pthread_t tri1;
	pthread_t tri2;
 
	sleep(3);
 
	printf ("[%d] Itération debut %d fin %d \n", count, deb, fin);
 
	if (deb != fin)
	{
		int milieu = (fin + deb) / 2;
 
		pthread_create(&tri1, NULL, tri_fusion_bis, NULL);
 
		tri_fusion_bis(tableau, milieu + 1, fin, count + 1, longueur);
 
		pthread_join(tri1, NULL);
		fusion(tableau, deb, milieu, fin, longueur);
	}
}

Bon par contre la création du thread n'est pas correcte (j'ai laissé ce que j'avais testé pour illustrer)

Je crée donc un thread qui trie une moitié, je rappelle la fonction a l'intérieur d'elle même, ce qui va tout échelonner et créer un thread par appel (et non 2 comme je proposais) et on attends que le thread ait finit pour effectuer les fusions.

Par contre dans la fonction tri_fusion :

Code :

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

1
2
3
4
5
6
7
8
 
void tri_fusion(int tableau[], int longueur)
{
	if (longueur > 0)
	{
		tri_fusion_bis(tableau, 0, longueur - 1, -1, longueur);
	}
}

Plutôt qu'un appel fonction, ne devrais-je pas plutôt créer un thread ici aussi ? Ou bien l'appel fonction suffit-il ?

Egalement, quelle est la différence entre le type int et le type size_t ?

[Sh4dow49]

Sinon je suis en train de tester un truc (j'ai mis quelques commentaires pour se repérer), ca vient donc compléter la fonction tri_fusion_bis sur laquelle on plance depuis cet après midi (je la remet pour voir les modif) :

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
 
//structure pour permettre le passage de paramètres dans le thread qui appelle la fonction tri_fusion_bis
struct MyArgs
{
	int tableau[MAX_SIZE];
	int deb;
	int fin;
	int count;
	int longueur;
 
};
 
//fonction temporaire permettant de rappeler la fonction tri_fusion_bis
void *temp (void *p)
{
	struct MyArgs *args = p
	tri_fusion_bis(args.tableau, args.deb, args.fin, args.count, args.longueur);
}
 
void tri_fusion_bis(int tableau[], int deb, int fin, int count, int longueur)
{
	pthread_t tri;
 
	struct MyArgs args;
	int i;
 
	sleep(3);
 
	printf ("[%d] Itération debut %d fin %d \n", count, deb, fin);
 
	if (deb != fin)
	{
		int milieu = (fin + deb) / 2;
 
		//on récupère les valeurs à passer en paramètre dans la structure
		for (i = 0; i < longueur; i++)
		{
			args.tableau[i] = tableau[i];
		}
		args.deb = deb;
		args.fin = milieu;
		args.count = count + 1;
		args.longueur = longueur;
		//fin de la récupération
 
		//on crée un thread appelant la fonction temporaire
		pthread_create(&tri, NULL, temp, &args);
 
		//on fait l'appel fonction pour la deuxième moitié du tableau
		tri_fusion_bis(tableau, milieu + 1, fin, count + 1, longueur);
 
		//on attends la fin de l'exécution du thread
		pthread_join(tri, NULL);
 
		//on appelle la fonction fusion
		fusion(tableau, deb, milieu, fin, longueur);
	}
}

En gros je passe par une fonction temporaire pour créer mon thread, ne prenant qu'un seul argument (la structure, dans laquelle je stocke les valeurs à passer en paramètre à tri_fusion_bis). La fonction temp se charge donc d'appeler tri_fusion_bis en mettant les paramètres récupérés via la structure.

J'ai juste une erreur que je ne sais pas comment corriger :

tri_fusion.c: In function 'temp':
tri_fusion.c:86: error: parse error before "tri_fusion_bis"

Quelqu'un aurait-il une idée pour m'aider ?

En tout cas grand merci à ceux qui m'ont aidé jusque là, notamment Médinoc, mais les autres aussi et ceux qui vont peut-être m'aider, car j'ai vraiment avancé et je comprends vraiment ce que je fais surtout grâce à vous

[Sh4dow49]

Bon en fait l'erreur vient du fait que j'avais oublié un point virgule lors de la récupération des paramètres dans la fonction temp (ligne ci-dessous) ;

Code :

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

struct MyArgs *args = p;

J'ai corrigé ce point et l'erreur maintenant est (un seul exemple, valable pour chaque paramètre passé à la fonction tri_fusion_bis quand je l'appelle depuis la fonction temp) :

error: request for member 'deb' in something not a structure or union

Je change donc les paramètres, au lieu de mettre args.deb (pour l'exemple) je met args->deb, et la ça compile !

Ça compile, mais ça ne trie pas comme il faut ...
Et la je ne vois pas ce qu'il faut faire par contre ... j'ai beau chercher je ne vois pas ...

Merci d'avance pour vos réponses (qui ne viendront qu'a partir de demain je pense pour maintenant ^^)

[Sh4dow49]

It is okay !

Voici ce que j'ai ajouté après la création du thread (dans la fonction tri_fusion_bis donc) (j'ai remis la création du thread pour situer exactement, ce n'est en aucun cas la création d'un second thread) :

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
 
//on crée un thread appelant la fonction temporaire
		pthread_create(&tri, NULL, temp, &args);
 
		//on attends la fin de l'exécution du thread
		pthread_join(tri, NULL);
 
for (i = 0; i < longueur; i++)
		{
			tableau[i] = args.tableau[i];
		}
		deb = args.deb;
		milieu = args.fin;
		count = args.count;
		longueur = args.longueur;

En clair, c'est l'inverse de ce que j'ai fai pour récupérer les valeurs dans la structure (rappel : la structure me permet de rassembler tous les paramètres à passer à la fonction tri_fusion_bis dans le thread créé).

Il s'agit tout simplement de redonner aux variables les valeurs modifiées à la fin de l'exécution du thread, dans le but d'avoir les bonnes valeurs lorsque, à la fin de l'exécution du thread, la fonction tri_fusion_bis se ré-appelle elle-même.

Je pense que c'est ce qu'on cherchait à faire avec Médinoc (si quelqu'un à une suggestion à faire ou juste une amélioration, ne pas hésiter)

Dans tous les cas un grand merci à tous ceux qui m'ont aidé aujourd'hui, particulièrement Médinoc. J'ai bien avancé (voir même fini si ce que j'ai fait est ce que cherchait à me faire comprendre Médinoc).

[Médinoc]

Salut,
J'ai du mal à voir exactement ce que tu fais car ce n'est pas exactement ma façon de faire, mais ça ne m'a pas l'air trop mal sur le principe...

[Luffy49]

Il me semble que ce tp est a faire tous seul ...

1) Ta la solution il te reste plus qua la faire marcher
2) c le meilleur moyen de te faire griller et d'avoir 0 ( si je suis tomber dessus c pas par hasard ... google est ton amis et celui du prof aussi )
3) Sa t'apprend rien de demander directe la solution
4) t un boulet xD

sur ce bonne chance

Luffy

[Emmanuel Delahaye]

je ne connais absolument rien en C

Alors arrête tout tout de suite avant que tu ne fasses exploser une centrale nucléaire ou dévier un astéroïde vers la Terre... (oui, le C, c'est puissant !)

Le langage C n'est pas un langage jouet qu'on apprend en 5 minutes en bidouillant au hasard. C'est un vrai langage de programmation professionnel très puissant (bas niveau) mais bourré de pièges et de subtilités. Si tu as besoin du C il faut passer du temps (6 mois à un an) à l'apprendre correctement. Sinon, utilise un autre langage que le C.

[Nikita0511]

Il me semble que ce tp est a faire tous seul ...

1) Ta la solution il te reste plus qua la faire marcher
2) c le meilleur moyen de te faire griller et d'avoir 0 ( si je suis tomber dessus c pas par hasard ... google est ton amis et celui du prof aussi )
3) Sa t'apprend rien de demander directe la solution
4) t un boulet xD

sur ce bonne chance

Luffy

la 4 !!!!

Spotted shadow