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_kपूर्णांक से कम एक का प्रतिनिधित्व के रूप में व्याख्या की जा सकती 2^n

यह आसानी से 1-डी सरणी (वेक्टर) के साथ काम करने की अनुमति देता है d[.]

व्यवहार में, एक अंतराल से jमेल खाती है

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

इसके अलावा, एक सीधा कार्यान्वयन हे (NlogN) है। (एन = 2 ^ एन)

उदाहरण के लिए, एक पुनरावर्ती समाधान संभव है

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) जटिलता को प्राप्त करने के लिए, एक सरल पुनरावृत्त दृष्टिकोण का उपयोग किया जाए।
(यहां एन कुल आंकड़ों की संख्या का प्रतिनिधित्व करता है)

#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

मैं यह मान रहा हूं कि यह एक बहुआयामी मैट्रिक्स है। आपको इसे पहले गणितीय रूप से हल करना पड़ सकता है और फिर कार्यक्रम में संबंधित समीकरण लिख सकते हैं।