dạng thu gọn của nhiều vòng lặp for trong C ++

Question

Tôi có một đoạn mã như sau, và số lượng forvòng lặp được xác định bởi số vòng lặp được xác định ntại thời điểm biên dịch. Mỗi forvòng lặp lặp lại các giá trị 0 và 1. Hiện tại, mã của tôi trông giống như thế này

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);
               }
            }
          // ...
        }
    }
}

Bây giờ câu hỏi của tôi là liệu người ta có thể viết nó ở dạng nhỏ gọn hơn không.

Answer 1

Các nbit in_kcó thể được hiểu là biểu diễn của một số nguyên nhỏ hơn 2^n.

Điều này cho phép dễ dàng làm việc với mảng 1-D (vector) d[.].

Trong thực tế, một interger jtương ứng với

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

Hơn nữa, một triển khai trực tiếp là O (NlogN). (N = 2 ^ n)

Một giải pháp đệ quy có thể thực hiện được, chẳng hạn như sử dụng

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

Điều này sẽ tương ứng với độ phức tạp O (N), ở điều kiện để giới thiệu ghi nhớ, không được thực hiện ở đây.

Kết quả:

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;
}

---

Như đã đề cập ở trên, phương pháp đệ quy cho phép độ phức tạp O (N), ở điều kiện để thực hiện ghi nhớ.

Một khả năng khác là sử dụng một cách tiếp cận lặp lại đơn giản, để có được độ phức tạp O (N) này.
(ở đây N đại diện cho tổng số dữ liệu)

#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;
}

Answer 2

Bạn có thể cấu trúc lại mã của mình một chút như sau:

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;
               }
            }
        }
    }
}

Và biến nó thành một hàm đệ quy ngay bây giờ:

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;
}

Nếu kiểu của bạn là int d[2][2][2]...[2][2];hoặc int*****... d;, bạn cũng có thể dừng khi kiểu không phải là mảng hoặc con trỏ thay vì chỉ định thủ công N(hoặc thay đổi cho bất kỳ kiểu nào d[0][0][0]...[0][0]là)

Đây là một phiên bản thực hiện điều đó với lambda đệ quy:

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));
}

Answer 3

Tôi giả định rằng nó là một ma trận đa chiều. Bạn có thể phải giải nó bằng toán học trước và sau đó viết các phương trình tương ứng trong chương trình.