पॉलीटॉप मॉडल: Difference between revisions

From Vigyanwiki
No edit summary
Line 26: Line 26:
== विस्तृत उदाहरण ==
== विस्तृत उदाहरण ==


[[File:Polytope model unskewed.svg|thumb|right|की निर्भरताएँ <code>src</code>,  लूप   अनुकूलीकरण से पहले कॉमन  लूप  रूपांतरण। लाल बिंदु से मेल खाता है <code>src[1][0]</code>; गुलाबी बिंदु से मेल खाता है <code>src[2][2]</code>.]]निम्नलिखित सी कूट फ़्लॉइड-स्टाइनबर्ग कटौती के समान त्रुटि-वितरण कटौती  के एक रूप को लागू करता है, लेकिन शैक्षणिक कारणों के लिए संशोधित किया गया है। द्वि-आयामी सरणी src में w पिक्सेल की h पंक्तियाँ होती हैं, प्रत्येक पिक्सेल में 0 और 255 के मध्य ग्रेस्केल मान होता है। दिनचर्या समाप्त होने के बाद, आउटपुट त्रुटि dst में मात्र 0 मान या 255 मान वाले पिक्सेल होंगे। गणना के समय, प्रत्येक पिक्सेल की डाइटिंग त्रुटि को वापस src सरणी में जोड़कर एकत्र किया जाता है। ध्यान दें कि गणना के दौरान src और dst दोनों पढ़े और लिखे जाते हैं; src मात्र पढ़ने के लिए नहीं है, और dst मात्र लिखने के लिए नहीं है।
[[File:Polytope model unskewed.svg|thumb|right|लूप तिरछा करने से पहले, src की निर्भरता। लाल बिंदु src[1][0]; गुलाबी बिंदु src[2] से मेल खाता है.]]निम्नलिखित सी कोड फ़्लॉइड-स्टाइनबर्ग डाइथरिंग के समान त्रुटि-वितरण डिथरिंग के एक रूप को अनुबंधित  करता है, परंतु शैक्षणिक कारणों से इन्हे संशोधित किया गया है।  द्वि-आयामी सरणी src में w पिक्सेल की h पंक्तियाँ होती हैं, प्रत्येक पिक्सेल में 0 और 255 के मध्य ग्रेस्केल मान होता है। रूटीन समाप्त होने के उपरांत, निर्गत त्रुटि dst में मात्र 0 मान या 255 मान वाले पिक्सेल उपस्थित होंगे। गणना के समय, प्रत्येक पिक्सेल की डाइटिंग त्रुटि को वापस src सरणी में जोड़कर एकत्र किया जाता है। ध्यान दें कि गणना के समय,  src और dst दोनों पढ़े और लिखे जाते हैं; src मात्र पढ़ने के लिए नहीं है, और dst मात्र लिखने के लिए नहीं है।


आंतरिक लूप   का प्रत्येक पुनरावृत्ति src[i][j] के मानों के आधार पर src[i-1][j], src[i][j-1], और src[i+1] के मानों को संशोधित करता है। जे -1]। (समान निर्भरताएँ dst[i][j] पर लागू होती हैं। लूप    विषमन के प्रयोजनों के लिए, हम src[i][j] और dst[i][j] को एक ही तत्व के रूप में सोच सकते हैं। हम उदाहरण दे सकते हैं src[i][j] रेखांकन की निर्भरता, जैसा कि दाईं ओर आरेख में है
आंतरिक लूप का प्रत्येक पुनरावृत्ति src[i][j] के मानों के आधार पर src[i-1][j], src[i][j-1], और src[i+1] के मानों को संशोधित करता है। [j-1]] वाली समान निर्भरताएँ dst[i][j] पर लागू होती हैं।


<!-- This table nonsense makes the page look slightly better in Firefox on Windows XP. Is there a more portable and self-explanatory way to get the code and images not to overlap with each other? --~~~~ -->
लूप विषमन के प्रयोजनों के लिए, हम src[i][j] और dst[i][j] को एक ही तत्व के रूप में मान सकते हैं। हम उदाहरण दे सकते हैं src[i][j] रेखांकन की निर्भरता, जैसा कि दाईं ओर आरेख में दर्शाया गया है ।
{|
{|
|-
|-
Line 57: Line 57:
|}
|}


[[File:Polytope model skewed.svg|thumb|right|की निर्भरताएँ <code>src</code>, लूप   तिरछा करने के बाद। सरणी तत्वों को ग्रे, लाल, हरा, नीला, पीला ... क्रम में संसाधित किया जाएगा।]]सजातीय परिवर्तन करना <math>(p,\, t) = (i,\, 2j+i)</math> मूल निर्भरता आरेख पर हमें एक नया आरेख मिलता है, जो अगली छवि में दिखाया गया है। फिर हम कोड को   लूप   ऑन करने के लिए फिर से लिख सकते हैं <code>p</code> और <code>t</code> के अतिरिक्त  <code>i</code> और <code>j</code>, निम्नलिखित तिरछी दिनचर्या प्राप्त करना।
[[File:Polytope model skewed.svg|thumb|right|की निर्भरताएँ <code>src</code>,लूप तिरछा करने के बाद। सरणी तत्वों को ग्रे, लाल, हरा, नीला, पीला क्रम में संसाधित किया जाएगा।]]सजातीय परिवर्तन करना <math>(p,\, t) = (i,\, 2j+i)</math> मूल निर्भरता आरेख पर हमें एक नया आरेख मिलता है, जो अगली छवि में दिखाया गया है। फिर हम कोड को लूप प्रारंभ करने के लिए पुनः लिख सकते हैं <code>p</code> और <code>t</code> के अतिरिक्त  <code>i</code> और <code>j</code>, निम्नलिखित तिरछी रूटीन प्राप्त करते है ।


<!-- Please don't break this code. Test before committing! -->
<!-- Please don't break this code. Test before committing! -->
Line 90: Line 90:
== यह भी देखें ==
== यह भी देखें ==
* बहुफलकीय प्रारूप  का समर्थन करने वाले ढांचे
* बहुफलकीय प्रारूप  का समर्थन करने वाले ढांचे
* लूप   नीड   अनुकूलीकरण
* लूप नीड अनुकूलीकरण
*  [[लूप   अनुकूलन]]
*  [[लूप अनुकूलन]]
*  [[लूप   अनोलिंग]]
*  [[लूप अनोलिंग]]
* लूप   टाइलिंग
* लूप टाइलिंग


== बाहरी लिंक और संदर्भ ==
== बाहरी लिंक और संदर्भ ==

Revision as of 20:34, 22 March 2023

बहुफलकीय प्रारूप, किसी प्रोग्राम में बड़ी संख्याओ वाली संक्रियाओ के लिए  एक गणितीय ढांचा है जिन्हे  स्पष्ट रूप से गणना करने के लिए बहुत बड़े सघन प्रतिनिधित्व की आवश्यकता होती है। नेस्टेड लूप प्रोग्राम विशिष्ट प्रयोगों के लिए उपयोगी हैं परंतु इसके लिए ये एकमात्र उदाहरण नहीं है और इस  प्रारूप का सबसे सरल उपयोग प्रोग्राम अनुकूलन में लूप नेस्ट अनुकूलन के लिए है। बहुफलकीय विधि नेस्टेड लूप के भीतर प्रत्येक लूप पुनरावृत्ति को बहुकोणीय आकृति नामक गणितीय वस्तुओं के अंदर नेस्टेड बिंदुओं के रूप में मानती है, और सजातीय रूपान्तरण या अधिक सामान्य गैर- सजातीय रूपान्तरण करती है। जैसे कि बहुतलों पर टाइलिंग, और फिर रूपांतरित बहुतलों को समतुल्य बहुफलनों में परिवर्तित करती है, परंतु  अनुकूलित, बहुफलकीय प्रारूप स्कैनिंग के माध्यम से लूप नेस्ट करता है।

सरल उदाहरण

C प्रोग्रामिंग भाषा में लिखे गए निम्नलिखित उदाहरण पर विचार करें:

 const int n = 100;
int i, j, a[n][n];

for (i = 1; i < n; i++) {
  for (j = 1; j < (i + 2) && j < n; j++) {
    a[i][j] = a[i - 1][j] + a[i][j - 1];
 

इस कोड के साथ आवश्यक समस्या यह है कि [i] [j] पर आंतरिक लूप के प्रत्येक पुनरावृत्ति के लिए आवश्यक है कि पिछले पुनरावृत्ति का परिणाम, [i] [j - 1], पहले से ही उपलब्ध हो। इसलिए, इस कोड को समानांतर या पाइपलाइन नहीं किया जा सकता जैसा कि वर्तमान में लिखा गया है।

सजातीय परिवर्तन के साथ बहुतलीय प्रारूप का एक अनुप्रयोग और सीमाओं में उपयुक्त परिवर्तन, ऊपर नेस्टेड लूप को रूपांतरित कर देगा

a[i - j][j] = a[i - j - 1][j] + a[i - j][j - 1];

इस स्थिति में, आंतरिक लूप का कोई पुनरावृत्ति पिछले पुनरावृत्ति के परिणामों पर निर्भर नहीं करता है; पूरे आंतरिक लूप को समानांतर में निष्पादित किया जा सकता है, यद्यपि बाहरी लूप का प्रत्येक पुनरावृत्ति पिछले पुनरावृत्तियों पर निर्भर करता है

विस्तृत उदाहरण

लूप तिरछा करने से पहले, src की निर्भरता। लाल बिंदु src[1][0]; गुलाबी बिंदु src[2] से मेल खाता है.

निम्नलिखित सी कोड फ़्लॉइड-स्टाइनबर्ग डाइथरिंग के समान त्रुटि-वितरण डिथरिंग के एक रूप को अनुबंधित  करता है, परंतु शैक्षणिक कारणों से इन्हे संशोधित किया गया है।  द्वि-आयामी सरणी src में w पिक्सेल की h पंक्तियाँ होती हैं, प्रत्येक पिक्सेल में 0 और 255 के मध्य ग्रेस्केल मान होता है। रूटीन समाप्त होने के उपरांत, निर्गत त्रुटि dst में मात्र 0 मान या 255 मान वाले पिक्सेल उपस्थित होंगे। गणना के समय, प्रत्येक पिक्सेल की डाइटिंग त्रुटि को वापस src सरणी में जोड़कर एकत्र किया जाता है। ध्यान दें कि गणना के समय,  src और dst दोनों पढ़े और लिखे जाते हैं; src मात्र पढ़ने के लिए नहीं है, और dst मात्र लिखने के लिए नहीं है।

आंतरिक लूप का प्रत्येक पुनरावृत्ति src[i][j] के मानों के आधार पर src[i-1][j], src[i][j-1], और src[i+1] के मानों को संशोधित करता है। [j-1]] वाली समान निर्भरताएँ dst[i][j] पर लागू होती हैं।

लूप विषमन के प्रयोजनों के लिए, हम src[i][j] और dst[i][j] को एक ही तत्व के रूप में मान सकते हैं। हम उदाहरण दे सकते हैं src[i][j] रेखांकन की निर्भरता, जैसा कि दाईं ओर आरेख में दर्शाया गया है ।

#define ERR(x, y) (dst[x][y] - src[x][y])

void dither(unsigned char** src, unsigned char** dst, int w, int h)
{
    int i, j;
    for (j = 0; j < h; ++j) {
        for (i = 0; i < w; ++i) {
            int v = src[i][j];
            if (i > 0)
                v -= ERR(i - 1, j) / 2;
            if (j > 0) {
                v -= ERR(i, j - 1) / 4;
                if (i < w - 1)
                    v -= ERR(i + 1, j - 1) / 4;
            }
            dst[i][j] = (v < 128) ? 0 : 255;
            src[i][j] = (v < 0) ? 0 : (v < 255) ? v : 255;
        }
    }
}
की निर्भरताएँ src,लूप तिरछा करने के बाद। सरणी तत्वों को ग्रे, लाल, हरा, नीला, पीला क्रम में संसाधित किया जाएगा।

सजातीय परिवर्तन करना मूल निर्भरता आरेख पर हमें एक नया आरेख मिलता है, जो अगली छवि में दिखाया गया है। फिर हम कोड को लूप प्रारंभ करने के लिए पुनः लिख सकते हैं p और t के अतिरिक्त i और j, निम्नलिखित तिरछी रूटीन प्राप्त करते है ।

 void dither_skewed(unsigned char **src, unsigned char **dst, int w, int h)  
 {
     int t, p;
     for (t = 0; t < (w + (2 * h)); ++t) {
         int pmin = max(t % 2, t - (2 * h) + 2);
         int pmax = min(t, w - 1);
         for (p = pmin; p <= pmax; p += 2) {
             int i = p;
             int j = (t - p) / 2;
             int v = src[i][j];
             if (i > 0)
               v -= ERR(i - 1, j) / 2;
             if (j > 0)
               v -= ERR(i, j - 1) / 4;
             if (j > 0 && i < w - 1)
               v -= ERR(i + 1, j - 1) / 4;
             dst[i][j] = (v < 128) ? 0 : 255;
             src[i][j] = (v < 0) ? 0 : (v < 255) ? v : 255;
         }
     }
 }


यह भी देखें

बाहरी लिंक और संदर्भ

श्रेणी:संकलक अनुकूलन श्रेणी:सूडोकोड के उदाहरण वाले लेख श्रेणी:उदाहरण सी कोड वाले लेख