C ++の多くのforループのコンパクトな形式
Jan 12 2021
私は次のようなコードを持っています、そしてforループの数はnコンパイル時にどれが知られているかによって決定されます。各forループは値0と1を繰り返します。現在、私のコードは次のようになっています。
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);
}
}
// ...
}
}
}
さて、私の質問は、もっとコンパクトな形で書くことができるかどうかです。
回答
2 Damien Jan 12 2021 at 21:23
nビットは、in_k整数1未満の表現として解釈することができます2^n。
これにより、1-D配列（ベクトル）を簡単に操作できますd[.]。
実際には、整数はにj対応します
j = in[0] + 2*in[1] + ... + 2^n-1*in[n-1]
さらに、直接実装はO（NlogN）です。（N = 2 ^ n）
再帰的な解決策が可能です。たとえば、
f(val, n) = updown(val%2) + f(val/2, n-1) and f(val, 0) = 0.
これは、メモ化を導入する条件でのO（N）の複雑さに対応しますが、ここでは実装されていません。
結果：
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;
}
上記のように、再帰的アプローチでは、メモ化を実装する条件で、O（N）の複雑さが可能になります。
もう1つの可能性は、このO（N）の複雑さを得るために、単純な反復アプローチを使用することです。
（ここで、Nはデータの総数を表します）
#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
次のようにコードを少しリファクタリングできます。
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;
}
}
}
}
}
そして、これを再帰関数にします。
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;
}
あなたのタイプがある場合int d[2][2][2]...[2][2];やint*****... d;タイプが配列またはポインタの代わりに、手動で指定していない場合、あなたはまた、停止することができますN（何のためか、変更の種類がd[0][0][0]...[0][0]あります）
再帰的なラムダでそれを行うバージョンは次のとおりです。
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
多次元行列だと思います。最初に数学的に解いてから、プログラムにそれぞれの方程式を書く必要があるかもしれません。