รูปแบบกะทัดรัดของจำนวนมากสำหรับการวนซ้ำใน C ++

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_k2^n

สิ่งนี้ช่วยให้สามารถทำงานกับอาร์เรย์ 1 มิติ (เวกเตอร์) d[.]ได้อย่างง่ายดาย

ในทางปฏิบัติ interger 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) โดยเป็นเงื่อนไขในการใช้การบันทึก

ความเป็นไปได้อีกประการหนึ่งคือการใช้วิธีการวนซ้ำอย่างง่ายเพื่อให้ได้ความซับซ้อน 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

คุณสามารถ refactor โค้ดของคุณได้เล็กน้อยดังนี้:

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

ฉันสมมติว่ามันเป็นเมทริกซ์หลายมิติ คุณอาจต้องแก้ทางคณิตศาสตร์ก่อนจากนั้นจึงเขียนสมการตามลำดับในโปรแกรม