Oui désolé je n'avais pas fait attention que tu cherchais à limiter le nombre de threads. J'ai compléter ma réponse depuis. A noter que je ma réponse ne concerne pas le crible d’Ératosthène mais juste comment répartir un tableau en n tableaux traités chacun par un thread (parmi x threads, x égal n ou pas).
Si tu es capable d'écrire un algorithme qui traite ton problème sur un tableau de n éléments quelconques, tu sais le faire dans un thread. Le problème c'est juste de savoir comment reconstituer un résultat unique qui rassemble le résultat de chaque thread et ça, c'est juste de la "concaténation". Donc de la création et de la copie de tableau (à défaut de passer par une ArrayList qui fait ça justement), et de la synchronisation de processus parallèle. Pour faire ça proprement, je ferais personnellement un buffer de type producteur/consomateur (ça fait un thread de plus pour consommer le contenu du buffer, mais ce thread peut être le thread principal).
Oui désolé je n'avais pas fait attention que tu cherchais à limiter le nombre de threads. J'ai compléter ma réponse depuis.
Mmm, sans faire les calculs et une démonstration, je dirais intuitivement que ça doit être vrai pour les premiers nombres premiers, mais que ça devient de moins en moins vrai... supposons qu'on soit en train d'évaluer 2 entiers N et M tels que M-N = 10
6. Il te faut au moins un tableau de 10
6+1 booléens (de taille donc (10
6)* 1 +12 octets pour les stocker (avec 2 valeurs à true et le reste à false) ou un tableau de 2 int, soit un taille de 4*2 + 12 octets. Me semble quand même que le tableau de int est plus petit que le tableau de booléen.
Avec une solution parallélisée, on a deux cas :
- créer un nouveau tableau à chaque fois qu'on parcourt un interval de int pour déterminer lesquels sont premiers. Avec des tableaux de booléens on va en créer beaucoup plus que de tableaux de int. Donc une charge beaucoup plus importante pour le GC.
- réutiliser les mêmes tableaux. dans le cas de booléen, on va produire beaucoup plus de tableaux à parcourir qui ne contiendront que des false, alors qu'avec des tableaux de int, tout parcours sera utile (parce qu'on aura que des nombres premiers dans le tableau). Si la charge en mémoire est moindre, elle se déplace simplement vers le cpu. Au lieu de consommer beaucoup d'espace pour des trucs inutiles, on va juste passer beaucoup de temps à faire des choses inutiles.
Reste à détermine à partir de quel N il est plus intéressant d'utiliser des int[] que des boolean[]...
Partager