QuickSort parallélisme (Thread et Runnable)

Version imprimable

Bonjour, j'ai besoin de votre aide. J' ai un problème que je n'arrive pas à résoudre par moi même malgré mes recherches sur internet et la doc java.

J'ai créé un classe générique de quickSort() mais je voudrais la faire de deux autres manières: une classe qui implémente l'interface Runnable, et une autre qui extend Thread.

Je vous donne ma classe quickSort qui "extends" mon interface Sortable:

Code:

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
 
___________________________________________________________
package part1e;
 
/*
 * Class QSort without raw types
 */
 
public class QSort extends Sortable  {
 
 
 
	public static <T extends Comparable<? super T>> void quickSort (T[] a, int from, int to) {
		  // Sort a[from√ñto] 
		    if (from < to) {
		      int p = partition(a, from, to);
		      quickSort(a, from, p-1);
		      quickSort(a, p+1, to);
		    }
		  }
 
		 public static <T extends Comparable<? super T>> void quickSort (T[] a) {
		  // Sort a[from√ñto] without indices as parameters
		     int from=0;
		     int to = a.length-1;
		     if (from < to) {
		      int p = partition(a, from, to);
		      quickSort(a, from, p-1);
		      quickSort(a, p+1, to);
		    }
		  }
 
		  private static <T extends Comparable<? super T>> int partition(T[] a,int from, int to) {
		  // Partition a[from√ñto] such that a[from√ñp-1] are all less than
		  // or equal to a[p] and a[p+1√ñto] are all greater than or equal to
		  // a[p].
 
		    T pivot = a[from]; int p = from;
		    for (int r = from+1; r <= to; r++) {
		     int comp = a[r].compareTo(pivot);
		     if (comp < 0) {
		      a[p] = a[r]; a[r] = a[p+1]; a[p+1] = pivot;
		      p++;
		     }
		    }
		    return p;
		  }
 
		  public static <T extends Comparable<? super T>> void test(T[] a,int from, int to){
		  //Test() method to know of the array is sorted
		      boolean b =true;
 
		      while((from<to-1)&&(b==true)){
		          if(a[from].compareTo(a[from+1])>=0){
		              b=false;
		          }
		          from++;
		      }
		      if(b==true)
		          System.out.println("The array is sorted");
		      else
		          System.out.println("The array is not sorted");
		  }
 
 
 
  public static void main(String[] args) {
    Integer[]  aInts = {51, 34, 54, 26, 74, 67, 68, 29, 2, 8, 45};
    test(aInts,0,10);
    QSort.quickSort(aInts,0,10);
    System.out.println("Sorted Integers:");
    for (Integer c : aInts) {
     System.out.print(c + "  ");
   }
   System.out.println();
   test(aInts,0,10);
 
  }
 
}
 
___________________________________________________________
 
package part1f;
 
public interface Sortable {
 
	public  abstract <T extends Comparable<? super T>> void quickSort (T[] a, int from, int to) ;
	public  abstract <T extends Comparable<? super T>> void quickSort (T[] a);
 
}
 
____________________________________________________________

Merci à tous pour vos reponses je l'espere nombreuses.

07/05/2010, 17h51
tchize_

c'est assez dur à paralléliser, mais ca pourrait se faire via un Threadpool executor. Au lieu d'etre récurise, tu transforme tes récursion en des ajout de tâche à la queue. Après reste à déterminer combien de threads tu veux allouer.
07/05/2010, 20h42
Tommy31

Oui, il faut un Thredpoolexecutor pour faire le job et ne pas implémenter un runnable mais un FutureTask, sauf si tu veux te gérer les synchro à la main.

Ce qui fait que tu as un algo à la fois récursif, pour lequel chaque niveau de récursion est alloué à un thread, sauf si le pool executor devient vide auquel cas tu dois séquentialiser.

Mon problème est que j'ai pour consigne de parallléliser avec l'héritage de la classe Thread et/ou l'impléméntation de Runnable.

Code:

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
 
Consigne:
 
 En Java, il existe deux méthodes pour créer des threads. La première étend la classe Thread :
class MonThread extends Thread {
  public void run() {
     // ici se trouve la description
     // du comportement du thread
  }
  public static void main (String[] args) {
     //on crée une instance de l’objet MonThread :
     MonThread t1 = new MonThread();
     // puis on lance le thread.
     // t1 exécute alors la méthode run() :
     t1.start();
  }
}
 La deuxième méthode implémente l’interface Runnable :
class Tache implements Runnable {
  public void run() {
     // ici se trouve la description
     // du comportement du thread
  }
  public static void main (String[] args) {
      //on crée une tache pour un thread :
     Tache job = new Tache();
     //on crée une instance de Thread avec la tache job
     Thread t1 = new Thread(job); :
     //puis on lance le thread.
     // t1 exécute alors la méthode run() de la tache job :
     t1.start();
  }
}

J'ai essayé d'implémenter ma classe en l'héritant de Thread mais je ne comprend pas comment gérer les 2 threads crées.

Code:

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
 
public class QSort <T extends Comparable<? super T>>  extends Thread {
 
	private int to;
	private int from;
	private T[] a;
 
 
	public QSort (String threadName,T[] a, int from, int to) {
 
		super(threadName); // Initialize thread.
		this.to=to;
		this.from=from;
		this.a=a;
		System.out.println(this);
		start();
	}
 
 
	 public T[] getT() {
	        return a;
	    }
	  public int getFrom() {
	        return from;
	    }
	  public int getTo() {
	        return to;
	    }
 
	public  <T extends Comparable<? super T>> void quickSort (T[] a,int from, int to) {
		  // Sort a[from√ñto] 
		    if (from < to) {
		      int p = partition(a, from, to);
		      quickSort(a, from, p-1);
		      quickSort(a, p+1, to);
		    }
		  }
 
 
	  private synchronized <T extends Comparable<? super T>> int partition(T[] a,int from, int to) {
	  // Partition a[from√ñto] such that a[from√ñp-1] are all less than
	  // or equal to a[p] and a[p+1√ñto] are all greater than or equal to
	  // a[p].
 
	    T pivot = a[from]; int p = from;
	    for (int r = from+1; r <= to; r++) {
	     int comp = a[r].compareTo(pivot);
	     if (comp < 0) {
	      a[p] = a[r]; a[r] = a[p+1]; a[p+1] = pivot;
	      p++;
	     }
	    }
	    return p;
	  }
 
 
	public void run() {
		QSort t2, t3;
		//Display info about this particular thread
		System.out.println(Thread.currentThread().getName());
 
	    if (from < to) {
	    	int p = partition(a, from, to);
 
	    	t2 =new QSort("Le thread 2",a,from,to);
	    	t3 =new QSort("Le thread 3",a,p+1, to);
	    	t2.start();
	    	t3.start();
 
	   }// fin if
	}
 
	    public static void main(String[] args) {
	    	Integer[] tab = {51, 12, 67, 45, 23, 11, 3, 89, 2, 90, 33};
	    	QSort t1 = new QSort("Thread principale",tab,0,10);
	    	t1.start();
		  }
 
}

Les threads qui remplacent la récursion se créent mais tournent en boucle et ne se terminent jamais. J'ai essayé isAlive(), join() mais je ne comprends pas qu'ils ne se terminent jamais et ne donnent pas naissance à de nouveaux thread pour remplacer d'éventuelles récursions. L'erreur se trouve dans la méthode run(), mais je ne sais pas quoi faire.

08/05/2010, 09h41
Tommy31
Bon quelques tuyaux pour t'aider à faire fonctionner ton programme :
1. Vire le start() dans le constructeur (puisque tu l'appelle à la main dans le main et dans la méthode run).
2. Ejecte ces synchronize qui servent à rien ici (les données sont compartimentés par de risque d'accès concurentiel)
3. Met des join, à a après les start de t1 et t2, et surtout après le start dans le main, sinon tu n'obtiendra jamais le résultat.
Là ca marchera.

J'ai corrigé mes erreurs synchronized et start();
Par contre j'ai toujours cette erreur de threads qui ne se terminent pas avec les join() à la fin de t2 et t3 et à la fin de t1 dans le main.

J'ai une erreur qui apparait pour les 2 threads que j'ai pu retrouver sur internet mais je ne sais pas vraiment quoi faire :

Thread[Le thread2,5,main]
Thread[Le thread3,5,main]
Thread[Le thread3,5,main]
Exception in thread "Le thread3" java.lang.OutOfMemoryError: unable to create new native thread
at java.lang.Thread.start0(Native Method)

Code:

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
public class QSort <T extends Comparable<? super T>>  extends Thread {
 
	int countPair =2,countImpair =3;
 
	private int to;
	private int from;
	private T[] a;
 
	 public T[] getT() {
	        return a;
	    }
	  public int getFrom() {
	        return from;
	    }
	  public int getTo() {
	        return to;
	    }
 
 
	public QSort (String threadName,T[] a, int from, int to) {
		super(threadName); // Initialize thread.
		this.to=to;
		this.from=from;
		this.a=a;
		System.out.println(this);
	}
 
 
 
	private  <T extends Comparable<? super T>> int partition(T[] a,int from, int to) {
		  // Partition a[from√ñto] such that a[from√ñp-1] are all less than
		  // or equal to a[p] and a[p+1√ñto] are all greater than or equal to
		  // a[p].
 
		    T pivot = a[from]; int p = from;
		    for (int r = from+1; r <= to; r++) {
		     int comp = a[r].compareTo(pivot);
		     if (comp < 0) {
		      a[p] = a[r]; a[r] = a[p+1]; a[p+1] = pivot;
		      p++;
		     }
		    }
		    return p;
		  }
 
 
	public void run() {
		QSort t2, t3;		
		//Display info about this particular thread
		System.out.println(Thread.currentThread().getName());
		 // Sort a[from√ñto] 
	    if (from < to) {
	    	int p = partition(a, from, to);
 
	    	 t2 = new QSort("Le thread" + countPair, a, from, to);
             t3 = new QSort("Le thread" + countImpair, a, p + 1, to);
             countPair++;
             countImpair++;
 
	    	 t2.start();
	    	 t3.start();
 
	    		try {
	    		t2.join();
	    		System.out.println("t2.join()");
	    		} 
	    		catch (InterruptedException e) 
	    		{ 
	    			System.out.println("t2.join() non réalisé");
	    		}
 
	    		try {
		    	t3.join();
		    	System.out.println("t3.join()");
		    	} 
		    	catch (InterruptedException e) 
		    	{ 
		   		System.out.println("t3.join() non réalisé");
		    	}
 
	   }// fin if
} // fin run
 
	    public static void main(String[] args) {
	    	//Sortable  s =new QSort();
	    	Integer[] tab = {12, 77, 67, 44, 21, 9, 99, 67, 2, 45, 37};
	    	QSort t1 = new QSort("Thread 1",tab,0,10);
	    	t1.start();
		try {
				t1.join();
			} catch (InterruptedException e) {
				// TODO Auto-generated catch block
				e.printStackTrace();
			}
		  }
 
}

08/05/2010, 13h10
tchize_

tu ne peux pas créer des threads à l'infini (d'où la suggestion d'utiliser un Threadpool executor). Par défaut, sous linux, on est limité à 1024 threads. Vu ton algorithme, ca représente seulement 10 niveau de récursions! (chaque Thread créant 2 threads, au niveau 10 on a donc 2^1024 threads). Il faut que tu détermine une limite au nombre de threads (2 ou 4 suivant le nombre de core dont dispose ta machine, pas plus)

T'as encore un bug. Dans la création de t2, les bornes du pivot sont incorrectes :
Code:

1 2 3 t2 = new QSort("Le thread" + countPair, a, from, p-1 ); t3 = new QSort("Le thread" + countImpair, a, p + 1, to);

09/05/2010, 13h51
jijoUK

Effectivement, il y avait cette erreur stupide qui causait la création de thread illimité. Maintenant cela marche parfaitement.

Merci à tous pour vos réponses.