Générer tous les nuplets avec C – meilleur moyen que les boucles nestedes?

J’ai un tableau double x[] de longueur 11 et une fonction f(double x[]) . Je veux trouver le minimum de la fonction f() par discrétisation. Donc pour des valeurs données val1, val2, ..., valn j’ai besoin d’une boucle passant par tous les tuples de x dans {val_1, …, val_n} ^ 11. Je pourrais facilement utiliser 11 boucles nestedes, mais est-ce vraiment le plus efficace que je puisse faire?

Edit: Pour clarifier les choses: la fonction f () est définie sur un ensemble de 11 dimensions. Je veux évaluer la fonction sur les sumts d’une grid de 11 dimensions. Pour une taille de grid h , les valeurs possibles pour les entrées du tableau x[] pourraient être 0 , h , 2*h , …, n*h = val_1, val_2, …, val_n. Ainsi, au début, f(val_1, val_1, ..., val_1) doit être évalué, puis f(val_1, val_1, ...,val_1, val_2) , … et dans les et f(val_n, val_n, ..., val_n) . Je me fiche de l’ordre en fait, mais je tiens à la vitesse, car il existe de nombreux n-uplets. Pour être précis, il n’existe pas 11 modèles de ce type. Donc pour n = 10, f() doit évaluer 10 ^ 11 fois. Mon ordinateur peut évaluer f() environ 5 * 10 ^ 6 fois par seconde. Ainsi, pour n = 10, l’évaluation de f() prend 5 heures. C’est pourquoi je cherche le moyen le plus efficace de le mettre en œuvre.

Voici un pseudocode (pas forcément syntaxiquement correct de code C) pour une approche non récursive permettant d’itérer sur tous les tuples possibles:

 const int vals[] = { val1, val2, val3, ... }; int x[NUM_DIMS] = { vals[0], vals[0], ... }; // The current tuple int i[NUM_DIMS] = { 0 }; // Index of each element in x[] while (1) { f(x); // Whatever // Update x (we increment i[] treated as a base-N number) int j; for (j = 0; j < NUM_DIMS; j++) { i[j]++; // Increment the current digit x[j] = vals[i[j]]; // Update (via mapping) if (i[j] < NUM_VALS) { break; } // Has this digit wrapped? // We've caused a carry to the next digit position i[j] = 0; // Wrap x[j] = vals[0]; // Update (via mapping) } if (j == NUM_DIMS) { break; } // All digits wrapped, therefore game over } 

Utilisez la récursivité lorsque le nombre de boucles dont vous avez besoin est trop élevé ou si vous ne le connaissez pas au moment de la compilation.

 void check(double *x, int count) { // Check the tuple } void process(double *x, double *tuple, int count, int pos) { if (pos == count) { check(tuple, count); } else { for (int i = 0 ; i != count ; i++) { tuple[pos] = x[i]; process(x, tuple, count, pos+1); } } } int main() { double x[11] = {1,2,3...}, tuple[11]; process(x, tuple, 11, 0); return 0; } 

Vous voudrez peut-être réduire la pression sur le cache du processeur. Ainsi, si N dans val_N est petit et que vous le représentez par N au lieu de N*h comme le suggère @OliCharlesworth, vous pourrez peut-être utiliser un type plus petit (par exemple, un caractère unsigned char ).

En outre, la boucle pourrait être réduite à:

 static inline int incx(uint8_t *x, unsigned int len) { ++*x; // compute any overflow unsigned int i = 0; while (x[i] >= len && i < len) { x[i++] -= len; ++x[i]; } // if the last value overflows, we're done return (i < len); } uint8_t x[LEN]; memset(x, 0, sizeof(x)); while (incx(x, sizeof(x))) f(x);