forme compacte de plusieurs boucles for en C++

Jan 12 2021

J'ai un morceau de code comme suit, et le nombre de forboucles est déterminé par celui nqui est connu au moment de la compilation. Chaque forboucle itère sur les valeurs 0 et 1. Actuellement, mon code ressemble à ceci

for(int in=0;in<2;in++){
    for(int in_1=0;in_1<2;in_1++){
        for(int in_2=0;in_2<2;in_2++){
          // ... n times
            for(int i2=0;i2<2;i2++){
               for(int i1=0;i1<2;i1++){
                   d[in][in_1][in_2]...[i2][i1] =updown(in)+updown(in_1)+...+updown(i1);
               }
            }
          // ...
        }
    }
}

Maintenant ma question est de savoir si on peut l'écrire sous une forme plus compacte.

Réponses

2 Damien Jan 12 2021 at 21:23

Les nbits in_kpeuvent être interprétés comme la représentation d'un entier inférieur à 2^n.

Cela permet de travailler facilement avec un tableau 1-D (vecteur) d[.].

En pratique, un entier jcorrespond à

j = in[0] + 2*in[1] + ... + 2^n-1*in[n-1]

De plus, une implémentation directe est O(NlogN). (N = 2^n)

Une solution récursive est possible, par exemple en utilisant

f(val, n) = updown(val%2) + f(val/2, n-1) and f(val, 0) = 0.

Ceci correspondrait à une complexité O(N), à condition d'introduire la mémoisation, non implémentée ici.

Résultat:

0 : 0
1 : 1
2 : 1
3 : 2
4 : 1
5 : 2
6 : 2
7 : 3
8 : 1
9 : 2
10 : 2
11 : 3
12 : 2
13 : 3
14 : 3
15 : 4

#include <iostream>
#include <vector>

int up_down (int b) {
    if (b) return 1;
    return 0;
}

int f(int val, int n) {
    if (n < 0) return 0;
    return up_down (val%2) + f(val/2, n-1);
}

int main() {
    const int n = 4;
    int size = 1;
    for (int i = 0; i < n; ++i) size *= 2;
    std::vector<int> d(size, 0);
    
    for (int i = 0; i  < size; ++i) {
        d[i] = f(i, n);
    }
    for (int i = 0; i < size; ++i) {
        std::cout << i << " : " << d[i] << '\n';
    }
    return 0;
}

Comme mentionné ci-dessus, l'approche récursive permet une complexité O(N), à condition de mettre en œuvre la mémorisation.

Une autre possibilité est d'utiliser une approche itérative simple, afin d'obtenir cette complexité O(N).
(ici N représente le nombre total de données)

#include <iostream>
#include <vector>

int up_down (int b) {
    if (b) return 1;
    return 0;
}
int main() {
    const int n = 4;
    int size = 1;
    for (int i = 0; i < n; ++i) size *= 2;
    std::vector<int> d(size, 0);
    
    int size_block = 1;
    for (int i = 0; i  < n; ++i) {
        for (int j = size_block-1; j >= 0; --j) {
            d[2*j+1] = d[j] + up_down(1);
            d[2*j] = d[j] + up_down(0);
        }
        size_block *= 2;
    }
    for (int i = 0; i < size; ++i) {
        std::cout << i << " : " << d[i] << '\n';
    }
    return 0;
}
2 Artyer Jan 12 2021 at 20:48

Vous pouvez refactoriser votre code légèrement comme ceci:

for(int in=0;in<2;in++) {
    auto& dn = d[in];
    auto updown_n = updown(in);
    for(int in_1=0;in_1<2;in_1++) {
        // dn_1 == d[in][in_1]
        auto& dn_1 = dn[in_1];
        // updown_n_1 == updown(in)+updown(in_1)
        auto updown_n_1 = updown_n + updown(in_1);
        for(int in_2=0;in_2<2;in_2++) {
            // dn_2 == d[in][in_1][in_2]
            auto& dn_2 = dn_1[in_2];
            // updown_n_2 == updown(in)+updown(in_1)+updown(in_2)
            auto updown_n_2 = updown_n_1 + updown(in_2);
                     .
                     .
                     .
            for(int i2=0;i2<2;i1++) {
               // d2 == d[in][in_1][in_2]...[i2]
               auto& d2 = d3[i2];
               // updown_2 = updown(in)+updown(in_1)+updown(in_2)+...+updown(i2)
               auto updown_2 = updown_3 + updown(i2);
               for(int i1=0;i1<2;i1++) {
                   // d1 == d[in][in_1][in_2]...[i2][i1]
                   auto& d1 = d2[i1];
                   // updown_1 = updown(in)+updown(in_1)+updown(in_2)+...+updown(i2)+updown(i1)
                   auto updown_1 = updown_2 + updown(i1);

                   // d[in][in_1][in_2]...[i2][i1] = updown(in)+updown(in_1)+...+updown(i1);
                   d1 = updown_1;
               }
            }
        }
    }
}

Et faites-en une fonction récursive maintenant :

template<std::size_t N, typename T>
void loop(T& d) {
    for (int i = 0; i < 2; ++i) {
        loop<N-1>(d[i], updown(i));
    }
}

template<std::size_t N, typename T, typename U>
typename std::enable_if<N != 0>::type loop(T& d, U updown_result) {
    for (int i = 0; i < 2; ++i) {
        loop<N-1>(d[i], updown_result + updown(i));
    }
}

template<std::size_t N, typename T, typename U>
typename std::enable_if<N == 0>::type loop(T& d, U updown_result) {
    d = updown_result;
}

Si votre type est int d[2][2][2]...[2][2];ou int*****... d;, vous pouvez également vous arrêter lorsque le type n'est pas un tableau ou un pointeur au lieu de spécifier manuellement N(ou de changer pour quel que soit le type de d[0][0][0]...[0][0])

Voici une version qui fait cela avec un lambda récursif :

auto loop = [](auto& self, auto& d, auto updown_result) -> void {
    using d_t = typename std::remove_cv<typename std::remove_reference<decltype(d)>::type>::type;
    if constexpr (!std::is_array<d_t>::value && !std::is_pointer<d_t>::value) {
        // Last level of nesting
        d = updown_result;
    } else {
        for (int i = 0; i < 2; ++i) {
            self(self, d[i], updown_result + updown(i));
        }
    }
};
for (int i = 0; i < 2; ++i) {
    loop(loop, d[i], updown(i));
}
girdhar Jan 12 2021 at 21:32

Je suppose que c'est une matrice multidimensionnelle. Vous devrez peut-être d'abord le résoudre mathématiquement, puis écrire les équations respectives dans le programme.