Une technique courante en parallélisation consiste à fusionner des boucles nestedes comme celle-ci.
for(int i=0; i<n; i++) { for(int j=0; j<n; j++) {
à
for(int x=0; x<n*n; x++) { int i = x/n; int j = x%n;
Je me demande comment je peux faire cela pour fondre une boucle en sortingangle comme celle-ci
for(int i=0; i<n; i++) { for(int j=0; j<i+1; j++) {
Cela a n*(n+1)/2
itérations. Appelons l’itération fusionnée x
. En utilisant la formule quadratique, j’ai trouvé ceci:
for(int x=0; x<(n*(n+1)/2); x++) { int i = (-1 + sqrt(1.0+8.0*x))/2; int j = x - i*(i+1)/2;
Contrairement à la fusion de la boucle carrée, cela nécessite l’utilisation de la fonction sqrt
et des conversions d’intol en float et de float en int.
Je me demande s’il existe un moyen plus simple ou plus efficace de procéder. Par exemple, une solution ne nécessitant pas la fonction sqrt
ou les conversions de int en float ou de float en int.
Edit: Je ne veux pas de solution qui dépend des itérations précédentes ou suivantes. Je veux seulement des solutions comme int i = funci(x) and int j = funcj(x,i)
Voici un code montrant que cela fonctionne:
#include #include int main() { int n = 5; int cnt = 0; for(int i=0; i<n; i++) { for(int j=0; j<i+1; j++) { printf("%d: %d %d\n", cnt++, i,j); } } printf("\n"); int nmax = n*(n+1)/2; for(int x=0; x<nmax; x++) { int i = (-1 + sqrt(1.0+8.0*x))/2; int j = x - i*(i+1)/2; printf("%d: %d %d\n", x,i,j); } }
Étant donné que vous essayez de fusionner un sortingangle dans le but de paralléliser, la solution non évidente consiste à choisir un mappage non sortingvial de x vers (i, j):
j |\ i -> | \ ____ | | \ => |\\ | V |___\ |_\\__|
Après tout, vous ne les traitez pas dans un ordre spécial, le mappage exact est donc sans importance.
Calculez donc x->i,j
comme vous le feriez pour un rectangle, mais si i > j
alors { i=Ni, j = Nj }
(axe Y du miroir, puis axe X du miroir).
____ |\\ | |\ |\ |_\\__| ==> |_\ __ => | \ / | | \ /__| |___\
La forme la plus saine est bien sûr la première forme.
Cela dit, la forme fusionnée est mieux faite avec les conditionnels:
int i = 0; int j = 0; for(int x=0; x<(n*(n+1)/2); x++) { // ... ++j; if (j>i) { j = 0; ++i; } }
Je me demande s’il existe un moyen plus simple ou plus efficace de procéder.
Oui, le code par lequel vous deviez commencer. Veuillez garder ceci à l’esprit:
Ainsi, votre deuxième exemple est quasiment garanti d’être beaucoup plus lent que le premier exemple, quel que soit le processeur utilisé dans le monde. En outre, il est également complètement illisible.