forma compatta di molti cicli for in C ++
Ho un pezzo di codice come segue e il numero di for
cicli è determinato da n
quale è noto in fase di compilazione. Ogni for
ciclo itera sui valori 0 e 1. Attualmente, il mio codice ha un aspetto simile a questo
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);
}
}
// ...
}
}
}
Ora la mia domanda è se è possibile scriverlo in una forma più compatta.
Risposte
I n
bit in_k
possono essere interpretati come la rappresentazione di un numero intero inferiore a 2^n
.
Ciò consente di lavorare facilmente con un array 1-D (vettore) d[.]
.
In pratica, un interger j
corrisponde a
j = in[0] + 2*in[1] + ... + 2^n-1*in[n-1]
Inoltre, un'implementazione diretta è O (NlogN). (N = 2 ^ n)
È possibile una soluzione ricorsiva, ad esempio utilizzando
f(val, n) = updown(val%2) + f(val/2, n-1) and f(val, 0) = 0.
Ciò corrisponderebbe a una complessità O (N), alla condizione di introdurre la memoizzazione, non implementata qui.
Risultato:
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;
}
Come accennato in precedenza, l'approccio ricorsivo consente una complessità O (N), a condizione di implementare la memoizzazione.
Un'altra possibilità è quella di utilizzare un semplice approccio iterativo, al fine di ottenere questa complessità O (N).
(qui N rappresenta il numero totale di dati)
#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;
}
Puoi eseguire il refactoring del codice in questo modo:
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 trasformalo in una funzione ricorsiva ora:
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 il tuo tipo è int d[2][2][2]...[2][2];
o int*****... d;
, puoi anche fermarti quando il tipo non è un array o un puntatore invece di specificare manualmente N
(o cambiare per qualunque sia il tipo di d[0][0][0]...[0][0]
)
Ecco una versione che lo fa con un lambda ricorsivo:
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));
}
Suppongo che sia una matrice multidimensionale. Potrebbe essere necessario risolverlo prima matematicamente e poi scrivere le rispettive equazioni nel programma.