bentuk kompak dari banyak for loop di C ++
Saya memiliki potongan kode sebagai berikut, dan jumlah for
loop ditentukan oleh n
yang diketahui pada waktu kompilasi. Setiap for
loop mengulang nilai 0 dan 1. Saat ini, kode saya terlihat seperti ini
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);
}
}
// ...
}
}
}
Sekarang pertanyaan saya adalah apakah seseorang dapat menulisnya dalam bentuk yang lebih ringkas.
Jawaban
The n
bit in_k
dapat diartikan sebagai representasi dari satu bilangan bulat kurang dari 2^n
.
Ini memungkinkan dengan mudah untuk bekerja dengan larik 1-D (vektor) d[.]
.
Dalam praktiknya, interger j
sesuai dengan
j = in[0] + 2*in[1] + ... + 2^n-1*in[n-1]
Selain itu, implementasi langsungnya adalah O (NlogN). (N = 2 ^ n)
Solusi rekursif dimungkinkan, misalnya menggunakan
f(val, n) = updown(val%2) + f(val/2, n-1) and f(val, 0) = 0.
Ini akan sesuai dengan kompleksitas O (N), pada kondisi untuk memperkenalkan memoization, tidak diterapkan di sini.
Hasil:
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;
}
Seperti disebutkan di atas, pendekatan rekursif memungkinkan kompleksitas O (N), pada kondisi untuk mengimplementasikan memoization.
Kemungkinan lain adalah dengan menggunakan pendekatan iteratif sederhana, untuk mendapatkan kompleksitas O (N) ini.
(di sini N mewakili jumlah total data)
#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;
}
Anda dapat mengubah kode Anda sedikit seperti ini:
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;
}
}
}
}
}
Dan buat ini menjadi fungsi rekursif sekarang:
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;
}
Jika tipe Anda adalah int d[2][2][2]...[2][2];
atau int*****... d;
, Anda juga bisa berhenti ketika tipe bukan larik atau penunjuk alih-alih menentukan secara manual N
(atau mengubah apa pun tipe d[0][0][0]...[0][0]
itu)
Berikut adalah versi yang melakukannya dengan lambda rekursif:
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));
}
Saya berasumsi bahwa ini adalah matriks multi-dimensi. Anda mungkin harus menyelesaikannya secara matematis terlebih dahulu dan kemudian menulis persamaan masing-masing dalam program.