TD4 Java avancé : petits processus

Lamba expressions
vendredi 6 novembre 2020
par  Emmanuel Adam
popularité : 4%

Processus en notation lambda

Il est possible en java de créer rapidement des processus « à la volée » en utilisant le constructeur de la classe Thread sui prend en argument un objet de type Runnable.

L’interface Runnable ne propose qu’une fonction
void run();
_dans laquelle sera effectué le calcul parallèle.

Par exemple, le code suivant recherche le code d’une serrure à molettes à 6 chiffres.

  • Il lance 6 processus qui tentent chacun aléatoirement de trouver le chiffre de leurs molettes.
    — Tant qu’un des processus est encore vivant et cherche, le programme attend, puis il affiche le temps de résolution.
    — Une recherche est également lancée par 1 processus (le main) qui tente seul de trouver les 6 chiffres au hasard.
    — il faudra env. 3 ms aux 6 processus pour trouver la clé en tatonant, et plus d’une demi seconde pour 1 seul processus
  1. public static void testPetitsRunsCombi()
  2. {
  3.  int[] cle = {4,2,1,9,5,8};
  4.  long startTime = System.currentTimeMillis();
  5.  
  6.  Thread process0 = new Thread(()->{while((int)(Math.random()*10) != cle[0])Thread.yield();});
  7.  Thread process1 = new Thread(()->{while((int)(Math.random()*10) != cle[1])Thread.yield();});
  8.  Thread process2 = new Thread(()->{while((int)(Math.random()*10) != cle[2])Thread.yield();});
  9.  Thread process3 = new Thread(()->{while((int)(Math.random()*10) != cle[3])Thread.yield();});
  10.  Thread process4 = new Thread(()->{while((int)(Math.random()*10) != cle[4])Thread.yield();});
  11.  Thread process5 = new Thread(()->{while((int)(Math.random()*10) != cle[5])Thread.yield();});
  12.  process0.start(); process1.start(); process2.start();
  13.  process3.start(); process4.start(); process5.start();
  14.  
  15.  while(process0.isAlive() || process1.isAlive() || process2.isAlive() || process3.isAlive() || process4.isAlive() || process5.isAlive()) Thread.yield();
  16.  long endTime = System.currentTimeMillis();
  17.  
  18.  System.err.printf("Ils ont trouvé en %d ms !!!\n",(endTime-startTime));
  19.  
  20.  int code = 421958 ;
  21.  startTime = System.currentTimeMillis();
  22.  while((int)(Math.random()*1000000) != code)Thread.yield();
  23.  endTime = System.currentTimeMillis();
  24.  System.err.printf("Il a trouvé tout seul en  %d ms !!!\n",(endTime-startTime));
  25. }

Il est possible de ranger les processus dans un groupe pour mieux les gérer :

  • ThreadGroup groupe = new ThreadGroup("mon groupe");
    Il faut ensuite passer en paramètre ce groupe au processus lors de sa création pour qu’il s’inscrive dedans.

A partir d’un groupe, il est possible de lister l’ensemble de ses processus actifs :
Le code ci-dessous reprend le code précédent mais est beaucoup plus compact et adaptable au nombre de molettes.

  • On passe ici à 7 chiffres à trouver. Quelques millisecondes seront nécessaires au processus, plusieurs seconde pour le main seul...
    _
  1. public static void testPetitsRunsCombiGroupes()
  2. {
  3.  int[] cle = {4,2,1,9,5,8,1};
  4.  long startTime = System.currentTimeMillis();
  5.  
  6.  ThreadGroup voleurs = new ThreadGroup("voleurs");
  7.  long startTime = System.currentTimeMillis();
  8.  for(int i = 0; i<6; i++){
  9.   int no = i;
  10.   new Thread(voleurs,()->{while((int)(Math.random()*10) != cle[no])Thread.yield();}).start();
  11.  }
  12.  while(voleurs.activeCount()!=0) Thread.yield();
  13.  long endTime = System.currentTimeMillis();
  14.  
  15.  System.err.printf("Ils ont trouvé en %d ms !!!\n",(endTime-startTime));
  16.  
  17.  int code = 4219581 ;
  18.  int dim = (int)Math.pow(10, cle.length);
  19.  startTime = System.currentTimeMillis();
  20.  while((int)(Math.random()*dim) != code)Thread.yield();
  21.  endTime = System.currentTimeMillis();
  22.  System.err.printf("Il a trouvé tout seul en  %d ms !!!\n",(endTime-startTime));
  23. }

Combinatoire en processus

Pour connaître le nombre de groupes de ’p’ éléments possibles parmi ’n’, on utilise la définition du coefficient binomial :

$C_n^p = \dfrac{n !}{(p ! \times (n-p) !}$

  • Avec cette méthode, on calcule qu’il y a 6 possibilités de créer des groupes de 3 éléments parmi 5 :
    • 123, 124, 125,134, 135, 145,
    • 234, 235, 245,
    • 345
  • on calcule aussi qu’il y a 13983816 de possibilités de tirer 6 boules d’un groupe de 49 ..

Créer une méthode static long fact(int n)

  • qui retourne n ! dans un entier long.
  • placer le code Thread.yield(); dans la boucle

remarque, le plus long en entier en java a pour valeur
$2^{64}-1 = 9223372036854775807$
Donc, il n’est pas possible d’aller plus loin que
$21 ! = 2432902008176640000$

On décide de ne pas optimiser et de lancer séparément les calculs de p !, (n-p) ! et n !
(idéalement deux calculs suffiraient, retournant d’abord, si p<(n-p), p !, puis (n-p+1)x(n-p+2)x...x n, mais pour l’exercice on fera long)

Créer une méthode static void cnp( int n,  int p)

  • qui définit un tableau de 3 long
    • long[] resultats = {1,1,1};
  • qui lance rapidement (cf. onglet précédents) 3 processus :
    • un processus processN qui lance le calcul de n ! et range le résultat dans resultats[0]
    • un processus processP qui lance le calcul de p ! et range le résultat dans resultats[1]
    • un processus processNP qui lance le calcul de (n-p) ! et range le résultat dans resultats[2]
  • qui attend la fin de tous les processus avant de calculer n !/ (p ! * (n-p) !)

Remarque : il n’est pas possible de modifier la valeur d’une variable à partir d’une classe interne à une fonction.

  • Ici, pour ranger leurs résultats, les processus les classent dans une case du tableau.
  • La valeur du tableau (son adresse) n’est pas modifiée...seuls les contenus de ses cases le sont.

solution au calcul de cnp (...)

solution au calcul de cnp avec entiers long

  1. static long fact(int n) {
  2.   long f = 1;
  3.   for(long i=1;i<=n; i++) {
  4.     f *=i;
  5.     Thread.yield();
  6.   }
  7.   return f;
  8. }
  9.  
  10. public static void cnp( int n,  int p)
  11. {
  12.   ThreadGroup groupe = new ThreadGroup("groupe factorielle");
  13.   long[] fact = {1,1,1};
  14.   process1 = new Thread(groupe, ()->fact[0] = fact(n)).start();
  15.   process2 = new Thread(groupe, ()->fact[1] = fact(p)).start();
  16.   process3 = new Thread(groupe, ()->fact[2] = fact(n-p)).start();
  17.  
  18.   while(groupe.activeCount()!=0 ) Thread.yield();
  19.  
  20.   long combinatoire =  fact[0]/(fact[1] * fact[2]);
  21.   System.out.println("combinaison de " + p + " éléments parmi " + n + " = " + combinatoire);
  22. }

Grands entiers

Le plus grand entier long en Java a comme valeur Long.MAX_VALUE=9223372036854775807,
ce qui limite le calcul de factorielle à 21 ! = 2432902008176640000

Le calcul de fact(22) retourne -4249290049419214848
car l’entier long suivant Long.MAX_VALUE est Long.MIN_VALUE = -9223372036854775808

Se limiter à 21 ! est très court. Pour aller plus loin, il faut utiliser la classe BigInteger.
Le plus grand BigInteger a la valeur de $2^{2147483647}$

  • BigInteger bigI = BigInteger.valueOf(10); initialise le grand entier bigI à 10
  • bigI = bigI.add(BigInteger.ONE); ajoute 1 à bigI
  • bigC = bigA.multiply(bigB); multiplie les deux grands entiers bigA et bigB et affecte le résultat à bigC
  • bigC = bigA.divide(bigB); divise le grand entier bigA par bigB et affecte le résultat à bigC

Créer la fonction static BigInteger factBig(int start, int end) qui calcule start \times (start+1) \times \dots \times end et retourne le résultat sous forme de grands entiers.
Ne pas oublier d’introduire dans la boucle la ligne Thread.yield()

Créer une méthode static void cnpBig( int n,  int p)

  • qui définit un tableau de 3 BigInteger
    • BigInteger[] resultat = {BigInteger.ONE, BigInteger.ONE, BigInteger.ONE};
  • qui lance rapidement les 3 processus pour calculer n !, (n-p) ! et p !
  • et qui affiche le résultat de n !/ (p ! * (n-p) !)

Optimiser le calcul et créez une méthode static void cnpBigQuick( int n,  int p)

  • qui définit un tableau de 2 BigInteger
    • BigInteger[] resultat = {BigInteger.ONE, BigInteger.ONE};
  • définir petit = min(n, n-p)
  • définir grand = max(n, n-p)
  • qui lance rapidement les 2 processus pour calculer $dessous=1 \times 2 \times \dots \times petit$
    et $dessus =(grand+1) \times (grand+2) \times \dots \times n$
  • et qui affiche le résultat de dessus/dessous

Vérifier que

  • $C_{49}^6 = 13983816$
  • $C_{50}^{25} = 126410606437752$
  • $C_{10000}^{3} = 166616670000$

Afficher le temps pris par les deux approches (cnpBigQuick & cnpBig)