TD4 Java avancé : petits processus
par
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 fonctionvoid 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
- public static void testPetitsRunsCombi()
- {
- int[] cle = {4,2,1,9,5,8};
- process0.start(); process1.start(); process2.start();
- process3.start(); process4.start(); process5.start();
- while(process0.isAlive() || process1.isAlive() || process2.isAlive() || process3.isAlive() || process4.isAlive() || process5.isAlive()) Thread.yield();
- int code = 421958 ;
- }
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...
_
- public static void testPetitsRunsCombiGroupes()
- {
- int[] cle = {4,2,1,9,5,8,1};
- for(int i = 0; i<6; i++){
- int no = i;
- }
- int code = 4219581 ;
- }
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.
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 à bigIbigC = bigA.multiply(bigB);
multiplie les deux grands entiers bigA et bigB et affecte le résultat à bigCbigC = 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)