forma compacta de muitos loop for em C ++
Eu tenho um trecho de código como segue, e o número de for
loops é determinado pelo n
que é conhecido em tempo de compilação. Cada for
loop itera sobre os valores 0 e 1. Atualmente, meu código é parecido com este
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);
}
}
// ...
}
}
}
Agora, minha pergunta é se podemos escrevê-lo de uma forma mais compacta.
Respostas
Os n
bits in_k
podem ser interpretados como a representação de um inteiro menor que 2^n
.
Isso permite trabalhar facilmente com uma matriz 1-D (vetor) d[.]
.
Na prática, um interger j
corresponde a
j = in[0] + 2*in[1] + ... + 2^n-1*in[n-1]
Além disso, uma implementação direta é O (NlogN). (N = 2 ^ n)
Uma solução recursiva é possível, por exemplo, usando
f(val, n) = updown(val%2) + f(val/2, n-1) and f(val, 0) = 0.
Isso corresponderia a uma complexidade O (N), na condição de introduzir memoização, não implementada aqui.
Resultado:
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;
}
Conforme mencionado acima, a abordagem recursiva permite uma complexidade O (N), na condição de implementar a memoização.
Outra possibilidade é usar uma abordagem iterativa simples, a fim de obter essa complexidade O (N).
(aqui N representa o número total de dados)
#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;
}
Você pode refatorar seu código um pouco assim:
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;
}
}
}
}
}
E transforme isso em uma função recursiva agora:
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;
}
Se o seu tipo for int d[2][2][2]...[2][2];
ou int*****... d;
, você também pode parar quando o tipo não for uma matriz ou ponteiro em vez de especificar manualmente N
(ou alterar o tipo de d[0][0][0]...[0][0]
)
Esta é uma versão que faz isso com um lambda recursivo:
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));
}
Estou assumindo que é uma matriz multidimensional. Você pode ter que resolver matematicamente primeiro e depois escrever as respectivas equações no programa.