प्रकाश की गति से जापानी रंग वर्ग को हल करना

जापानी क्रॉसवर्ड (नॉनोग्राम) भी तार्किक पहेली हैं जिसमें एक पिक्सेल छवि एन्क्रिप्ट की जाती है। आपको लाइनों के बाईं ओर और स्तंभों के ऊपर स्थित संख्याओं का उपयोग करके क्रॉसवर्ड को हल करना होगा।

वर्ग पहेली का आकार 150x150 तक पहुंच सकता है। खिलाड़ी प्रत्येक सेल के रंग की गणना करने के लिए विशेष तर्क का उपयोग करता है। समाधान शुरुआती पहेली के लिए पहेली पहेली पर कुछ मिनट और जटिल पहेली पर दसियों घंटे ले सकता है।

एक अच्छा एल्गोरिथ्म समस्या को बहुत तेज़ी से हल कर सकता है। पाठ का वर्णन है कि कैसे एक समाधान लिखना है जो सबसे उपयुक्त एल्गोरिदम (जो आमतौर पर समाधान का नेतृत्व करता है) का उपयोग करके लगभग तुरंत काम करता है, साथ ही साथ उनकी अनुकूलन और सी ++ सुविधाओं का उपयोग (जो कई बार दसियों बार रनटाइम को कम करता है)।

होराब के मोबाइल संस्करण में, पाठ में सूत्र नहीं दिखाए जा सकते (सभी मोबाइल ब्राउज़र में नहीं) - यदि आप सूत्रों के साथ समस्याएँ देखते हैं तो पूर्ण संस्करण या किसी अन्य मोबाइल ब्राउज़र का उपयोग करें

खेल के नियम

प्रारंभ में, क्रॉसवर्ड कैनवास सफेद है। वेनिला काले और सफेद वर्ग के लिए, आपको काले कोशिकाओं के स्थान को पुनर्स्थापित करने की आवश्यकता है।

काले और सफेद वर्ग में, प्रत्येक पंक्ति (कैनवास के बाईं ओर) या प्रत्येक स्तंभ (कैनवास के ऊपर) के लिए संख्याओं की संख्या से पता चलता है कि संबंधित पंक्ति या स्तंभ में काली कोशिकाओं के कितने समूह हैं, और संख्याएँ स्वयं बताती हैं कि इनमें से प्रत्येक समूह में कितनी संख्या में सेल हैं। संख्या का सेट $$$[3, 2, 5]$ इसका मतलब है कि एक निश्चित पंक्ति में से तीन लगातार समूह हैं $$$3$ । $$$2$ और $$$5$ एक पंक्ति में काली कोशिकाएँ। समूहों को क्रमिक रूप से एक पंक्ति में व्यवस्थित किया जा सकता है, सापेक्ष क्रम का उल्लंघन किए बिना (संख्या उनकी लंबाई निर्दिष्ट करती है, और स्थिति का अनुमान लगाया जाना चाहिए), लेकिन उन्हें कम से कम एक सफेद सेल द्वारा अलग किया जाना चाहिए।

सही उदाहरण

रंग वर्ग में प्रत्येक समूह का अभी भी अपना रंग है - कोई भी, सफेद को छोड़कर, एक पृष्ठभूमि रंग है। अलग-अलग रंगों के पड़ोसी समूह कंधे से कंधा मिलाकर खड़े हो सकते हैं, लेकिन एक ही रंग के पड़ोसी समूहों के लिए, कम से कम एक सफेद सेल द्वारा अलगाव अभी भी आवश्यक है।

जापानी क्रॉसवर्ड क्या नहीं है

प्रत्येक पिक्सेल छवि को क्रॉसवर्ड पहेली के रूप में एन्क्रिप्ट किया जा सकता है। लेकिन इसे वापस बहाल करना संभव नहीं हो सकता है - परिणामस्वरूप पहेली के पास एक से अधिक समाधान हो सकते हैं, या एक समाधान हो सकता है, लेकिन व्यावहारिक रूप से हल नहीं किया जा सकता है। फिर गेम में शेष कोशिकाओं को क्वांटम कंप्यूटरों का उपयोग करके शॅमिक तकनीक का अनुमान लगाया जाना है ।

इस तरह के वर्ग पहेली नहीं हैं, लेकिन ग्रेफोमेनिया। यह माना जाता है कि सही क्रॉसवर्ड पहेली ऐसी है कि तार्किक तरीके से आप एक अद्वितीय समाधान के लिए आ सकते हैं।

"तार्किक पथ" प्रत्येक सेल को एक-एक करके पुनर्स्थापित करने की क्षमता है, पंक्ति / स्तंभ को अलग से या उनके चौराहे पर विचार करते हुए। यदि यह संभव नहीं है, तो माना जवाब विकल्पों की संख्या बहुत अधिक हो सकती है, एक व्यक्ति की तुलना में बहुत अधिक खुद के लिए गणना कर सकता है।

गलत नॉनोग्राम एकमात्र समाधान है, लेकिन सामान्य रूप से हल करना असंभव है। ऑरेंज ने "असंगत" कोशिकाओं को लेबल किया। विकिपीडिया से लिया गया।

इस प्रतिबंध को निम्नानुसार समझाया गया है - सबसे सामान्य मामले में, जापानी क्रॉसवर्ड पहेली एक एनपी-पूर्ण समस्या है। हालांकि, अनुमान लगाना एनपी-पूर्ण कार्य नहीं बन जाता है, अगर कोई एल्गोरिथ्म है जो प्रत्येक समय में स्पष्ट रूप से इंगित करता है कि आगे कौन से सेल खुलने हैं। मनुष्यों द्वारा उपयोग की जाने वाली सभी क्रॉसवर्ड पहेलियाँ (विधि को छोड़कर) मोंटे कार्लो परीक्षण और त्रुटि) इस पर आधारित हैं।

अधिकांश रूढ़िवादी क्रॉसवर्ड पहेलियाँ 5 चौड़ाई और ऊंचाइयों से विभाजित होती हैं, ऐसी कोई पंक्तियाँ नहीं होती हैं, जिन्हें तुरंत गिना जा सकता है (वे जहां रंगीन कोशिकाएं सभी स्थानों को रोक देती हैं, या वे सभी जगह मौजूद नहीं होती हैं), और पूरक रंगों की संख्या सीमित है। इन आवश्यकताओं की आवश्यकता नहीं है।

सबसे सरल गलत क्रॉसवर्ड पहेली:

|1 1| --+---+ 1| | 1| | --+---+ 

अक्सर, एन्कोडेड पिक्सेल आर्ट, जो एक ग्रेडिएंट का अनुकरण करने के लिए "चेकबोर्ड" पैटर्न का उपयोग करता है, पीछे की तरफ हल नहीं होता है। यह समझने में बेहतर है कि यदि आप खोज में "पिक्सेलआर्ट ग्रेडिएंट" टाइप करते हैं। ग्रेडिएंट इस 2x2 फेयेल क्रॉसवर्ड की तरह ही है।

संभव समाधान

हमारे पास क्रॉसवर्ड पहेली का आकार, रंगों और सभी पंक्तियों और स्तंभों का विवरण है। मैं इस से एक चित्र कैसे इकट्ठा कर सकता हूं:

पूर्ण खोज

प्रत्येक सेल के लिए, हम सभी संभव राज्यों के माध्यम से सॉर्ट करते हैं और संतोषजनक की जांच करते हैं। एक काले और सफेद क्रॉसवर्ड के लिए इस तरह के समाधान की जटिलता $$$O (N * M * {2} ^ {N * M})$ , रंग के लिए $$$O (N * M * {color} ^ {N * M})$ । जोकर सॉर्टिंग के साथ सादृश्य द्वारा , इस समाधान को जोकर भी कहा जा सकता है। यह आकार 5x5 के लिए उपयुक्त है।

बैक ट्रैकिंग

कोशिकाओं के क्षैतिज समूहों की व्यवस्था के सभी संभावित तरीकों को हल किया जाता है। हम एक पंक्ति में कोशिकाओं का एक समूह रखते हैं, यह जांचें कि यह कॉलम समूहों के विवरण को नहीं तोड़ता है। यदि यह टूट जाता है, तो हम 1 सेल पर आगे रखते हैं, हम फिर से जांच करते हैं। सेट करें - अगले समूह पर जाएं। यदि आप किसी भी तरह से एक समूह नहीं रख सकते हैं, तो हम दो समूहों को वापस लाते हैं, पिछले समूह को फिर से व्यवस्थित करते हैं, और जब तक कि हम अंतिम समूह को सफलतापूर्वक नहीं डालते हैं।

प्रत्येक पंक्ति के लिए अलग से

यह निर्णय बहुत बेहतर है और यह वास्तव में सही है। हम प्रत्येक पंक्ति और प्रत्येक कॉलम का व्यक्तिगत रूप से विश्लेषण कर सकते हैं। प्रत्येक पंक्ति अधिकतम जानकारी प्रकट करने का प्रयास करेगी।

पंक्ति में प्रत्येक सेल के लिए एल्गोरिथ्म अधिक जानकारी सीखता है - यह पता चला सकता है कि सेल को कुछ रंग में रंगना असंभव है, समूह अभिसरण नहीं करेंगे। आप पूरी तरह से पंक्ति का विस्तार नहीं कर सकते, लेकिन प्राप्त जानकारी कई कॉलमों के लिए बेहतर तरीके से "मदद" करेगी, और जब हम उनका विश्लेषण करना शुरू करेंगे, तो वे फिर से पंक्तियों को "मदद" करेंगे, और कई पुनरावृत्तियों के लिए, जब तक कि सभी कोशिकाओं में एक संभव रंग न हो।

सच में सही फैसला

एक पंक्ति, दो रंग

ब्लैक-एंड-व्हाइट "सिंगल-लाइन" का प्रभावी अनुमान, जिसके लिए कुछ सेल पहले ही अनुमान लगा चुके हैं, एक बहुत ही कठिन काम है। वह इस तरह के स्थानों में मिले:

• ACM ICPC 2006 का क्वार्टर फाइनल - आप समस्या को स्वयं हल करने का प्रयास कर सकते हैं । समय सीमा 1 सेकंड है, समूहों की संख्या पर सीमा 400 है, और श्रृंखला की लंबाई भी 400 है। इसमें अन्य कार्यों की तुलना में जटिलता का स्तर बहुत अधिक है।
• इंटरनेशनल ओलंपियाड इनफॉर्मेटिक्स 2016 - कार्य को पारित करने की शर्त । समय सीमा 2 सेकंड है, समूहों की संख्या की सीमा 100 है, पंक्ति की लंबाई 200'000 है। इस तरह की सीमाएं ओवरकिल हैं, लेकिन एसीएम प्रतिबंधों के साथ एक समस्या को हल करना इस समस्या में 80/100 अंक हासिल करता है। यहां भी, स्तर ने निराश नहीं किया, दुनिया भर के स्कूली बच्चों ने एक क्रूर बुद्धि स्तर के साथ विभिन्न चालों को हल करने के लिए कई वर्षों से प्रशिक्षण लिया है, फिर वे इस ओलंपियाड में जाते हैं (देश से केवल 4 लोगों को पास होना चाहिए), वे 5 घंटे के 2 दौर तय करते हैं और महाकाव्य जीत के मामले में (600 में से 138-240 अंक के लिए अलग-अलग वर्षों में कांस्य), ऑक्सफ़ोर्ड में प्रवेश, फिर स्पष्ट कंपनियों से खोज विभाग को प्रदान करता है, एक लंबा और सुखी जीवन dakimakura के साथ गले लगा लिया।

मोनोक्रोम सिंगल-लाइन को विभिन्न तरीकों से भी हल किया जा सकता है, और इसके लिए $$$O (N * 2 ^ N)$ (सभी विकल्पों की गणना, शुद्धता के लिए जाँच, सभी विकल्पों में समान रंग वाली कोशिकाओं का चयन करना), और किसी तरह कम बेवकूफ होना।

मुख्य विचार बैकट्रैकिंग के एनालॉग का उपयोग करना है, लेकिन अनावश्यक गणना के बिना। यदि हम किसी तरह कई समूह स्थापित करते हैं और अब किसी तरह के सेल में हैं, तो हमें यह पता लगाना होगा कि क्या वर्तमान सेल से शुरू होकर शेष समूह को रखना संभव है।

 def EpicWin(group, cell): if cell >= last_cell: #   return group == group_size win = False #        if group < group_size #    and CanInsertBlack(cell, len[group]) #    and CanInsertWhite(cell + len[group], 1) #    and EpicWin(group + 1, cell + len[group] + 1): #    win = True can_place_black[cell .. (cell + len[group] - 1)] = True can_place_white[cell + len[group]] = True; #         if CanInsertWhite(cell, 1) and EpicWin(group, cell + 1): win = True can_place_white[cell] = True return win EpicWin(0, 0) 

इस दृष्टिकोण को डायनेमिक प्रोग्रामिंग कहा जाता है । छद्म कोड को सरलीकृत किया गया है, और यहां तक ​​कि गणना किए गए मान भी संग्रहीत नहीं हैं।

CanInsertBlack/CanInsertWhite को यह जांचने की आवश्यकता है कि क्या सही जगह पर सही आकार के समूह को रखना सैद्धांतिक रूप से संभव है। उन सभी को यह सत्यापित करने की आवश्यकता है कि संकेतित सेल श्रेणी में कोई "100% सफेद" सेल नहीं है (पहले फ़ंक्शन के लिए) या "100% काला" (दूसरे के लिए)। इसलिए वे काम कर सकते हैं $$$O (1)$ , यह आंशिक मात्रा का उपयोग करके किया जा सकता है:

 white_counter = [ 0, 0, ..., 0 ] #   n def PrecalcWhite(): for i in range(0, (n-1)): if is_anyway_white[i]: # 1,  i-  100%  white_counter[i]++ if i > 0: white_counter[i] += white_counter[i - 1] def CanInsertBlack(cell, len): #     [cell, cell + len - 1] ans = white_counter[cell + len - 1] if cell > 0: ans -= white_counter[cell - 1] #  ans -     cell  (cell + len - 1) return ans == 0 

आंशिक रकम के साथ एक ही टोना फार्म की एक पंक्ति का इंतजार कर रहा है

 can_place_black[cell .. (cell + len[group] - 1)] = True 

यहाँ हम १ के बजाय संख्या को बढ़ा सकते हैं। १ / या यदि हमें किसी सेगमेंट में बहुत सी जोड़ियाँ बनानी हैं $$$सरणी$ , और इसके अलावा हम अलग-अलग परिवर्धन से पहले इस सरणी का उपयोग नहीं करते हैं (वे इस बारे में कहते हैं कि यह कार्य "ऑफ़लाइन हल किया गया है"), फिर लूप के बजाय:

 #     for i in range(L, R + 1): array[i]++ 

आप यह कर सकते हैं:

 #     array[L]++ array[R + 1]-- #    for i in range(1, n): array[i] += array[i - 1] 

इस प्रकार, पूरा एल्गोरिथ्म काम करता है $$$O (k * n)$ जहाँ $$$k$ - काली कोशिकाओं के समूहों की संख्या, $$$एन$ स्ट्रिंग की लंबाई है। और हम ACM ICPC के सेमीफाइनल में जाते हैं या इंटर्नशिप का कांस्य प्राप्त करते हैं। ACM समाधान (जावा) । IOI समाधान (C ++) ।

एक लाइन, कई रंग

जब हम बहु-रंग नॉनोग्राम पर स्विच करते हैं, जो अभी भी स्पष्ट नहीं हैं कि कैसे हल किया जाए, तो हम एक भयानक सच्चाई सीखते हैं - यह पता चलता है कि हर कॉलम जादुई रूप से सभी कॉलमों से प्रभावित होता है! यह एक उदाहरण के माध्यम से स्पष्ट है:

स्रोत - जापानी वर्ग पहेली को हल करने के तरीके

जबकि सामान्य रूप से दो-रंग के गैर -ोग्राम ने इसके बिना किया, उन्हें ऑर्थोगोनल दोस्तों को वापस देखने की आवश्यकता नहीं थी।
चित्र दिखाता है कि बाएं उदाहरण में, तीन चरम दाएं कोशिकाएं खाली हैं, क्योंकि यदि आप इन कोशिकाओं को रंग देते हैं तो कॉन्फ़िगरेशन टूट जाता है वे रंग जिनमें खुद को रंगना है गैर-सफेद रंग।

लेकिन यह मजाक गणितीय रूप से निर्णायक है - प्रत्येक सेल को एक नंबर दिया जाना चाहिए, जहां $$$मैं$ ith बिट का मतलब होगा कि क्या यह सेल दिया जा सकता है $$$मैं$ ध रंग। प्रारंभ में, सभी कोशिकाओं का एक मूल्य होता है $$$2 ^ {रंग} - 1$ । गतिकी का निर्णय बहुत अधिक नहीं बदलेगा।

आप निम्न प्रभाव का निरीक्षण कर सकते हैं: समान बाएं उदाहरण में, पंक्तियों के संस्करण के अनुसार, सबसे दाईं ओर की सेल में नीले या सफेद रंग हो सकते हैं।
कॉलम के संस्करण के अनुसार, इस सेल में या तो हरा या सफेद रंग है।
सामान्य ज्ञान संस्करण के अनुसार, इस सेल में केवल सफेद रंग होगा। और फिर हम उत्तर की गणना करना जारी रखते हैं।

यदि हम शून्य बिट "व्हाइट", पहला "ब्लू", दूसरा "ग्रीन" मानते हैं, तो लाइन ने अंतिम सेल के लिए राज्य की गणना की $$$011$ , और कॉलम $$$101$ । इसका मतलब है कि इस सेल की स्थिति वास्तविक है $$$011 \ & 101 = 001$

 source = [...] #   result = [0, 0, ..., 0] #   len = [...] #    clrs = [...] #    def CanInsertColor(color, cell, len): for i in range(cell, cell + len): if (source[i] & (1 << color)) == 0: #     color    return False; return True def PlaceColor(color, cell, len): for i in range(cell, cell + len): result[i] |= (1 << color) #   color  OR def EpicWinExtended(group, cell): if cell >= last_cell: #   return group == group_size win = False #        if group < group_size #    and CanInsertColor(clrs[group], cell, len[group]) #    and SequenceCheck() #       ,  #         and EpicWin(group + 1, cell + len[group]): #    win = True PlaceColor(clrs[group], cell, len[group]) PlaceColor(0, cell + len[group], 1) #   -    #         #   -  0 if CanInsertWhite(0, cell, 1) and EpicWinExtended(group, cell + 1): win = True PlaceColor(0, cell, 1) return win 

कई लाइनें, कई रंग

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

पहला परिणाम

मान लीजिए कि हमने कठफोड़वा की तरह कोड नहीं लिखा है, यानी हम संदर्भ से गुजरने के बजाय गलती से कहीं भी वस्तुओं को कॉपी नहीं करते हैं, हम कहीं भी साइकिल का आविष्कार नहीं करते हैं, हम साइकिल का आविष्कार नहीं करते हैं, बिट संचालन के लिए हम __builtin_popcount और __builtin_ctz ( gcc फीचर्स ) का उपयोग करते हैं, सब कुछ साफ है।

आइए कार्यक्रम के समय को देखें, जो फ़ाइल से पहेली को पढ़ता है और इसे पूरी तरह से हल करता है। यह उस मशीन के फायदों का मूल्यांकन करने के लायक है जिस पर यह सब लिखा और परीक्षण किया गया था:

 RAM - 4GB  - AMD E1-2500,  1400MHz  L1 - 128KiB, 1GHz  L2 - 1MiB, 1GHz  - 2,  - 2   « SoC   »   2013    28  

यह स्पष्ट है कि इस तरह के एक सुपर कंप्यूटर को चुना गया था क्योंकि इस पर अनुकूलन एक उड़ान शैतान मशीन की तुलना में अधिक प्रभाव डालते हैं।

इसलिए, सबसे जटिल क्रॉसवर्ड पहेली (नॉनोग्राम्स 12 के अनुसार) पर हमारे एल्गोरिथ्म को चलाने के बाद, हमें बहुत अच्छा परिणाम नहीं मिलता है - 47 से 60 सेकंड (इसमें फ़ाइल और समाधान से पढ़ना शामिल है)। यह ध्यान दिया जाना चाहिए कि साइट पर "जटिलता" अच्छी तरह से गणना की गई थी - कार्यक्रम के सभी संस्करणों में एक ही क्रॉसवर्ड पहेली भी सबसे कठिन थी, संग्रह की राय में अन्य सबसे जटिल वर्ग पहेली शीर्ष समय में रखी गई थीं।

रंग क्रॉसवर्ड नंबर 9596, सबसे बड़ी कठिनाई

त्वरित परीक्षण के लिए, बेंचमार्क के लिए कार्यक्षमता बनाई गई थी। उसके लिए डेटा प्राप्त करने के लिए, मैं 4683 रंगीन क्रॉसवर्ड ( 10906 से ) और 1406 ब्लैक एंड व्हाइट ( 8293 से ) को nonograms.ru (इंटरनेट पर यह सबसे बड़ा नॉनोग्राम अभिलेखागार में से एक) का उपयोग करके एक विशेष स्क्रिप्ट का उपयोग करता हूं और उन्हें एक प्रारूप में सहेजता हूं, जिसे प्रोग्राम समझता है। हम मान सकते हैं कि ये क्रॉसवर्ड एक यादृच्छिक नमूना हैं, इसलिए बेंचमार्क पर्याप्त औसत मान दिखाएगा। इसके अलावा, सबसे "जटिल" वर्ग पहेली के दर्जनों के एक जोड़े की संख्या (आकार में सबसे बड़ी और रंगों की संख्या भी) एक स्क्रिप्ट में कलमों के साथ लोड करने के लिए दर्ज की गई थी।

अनुकूलन

यहां आप संभावित अनुकूलन तकनीकों को देख सकते हैं जो पूरे एल्गोरिथ्म के लेखन के दौरान (1) बनाई गई थीं, (2) काम के समय को आधा मिनट से दूसरे के एक अंश तक कम करने के लिए, (3) उन अनुकूलन जो आगे उपयोगी हो सकते हैं।

एल्गोरिथ्म लिखने के समय

• बिट संचालन के लिए विशेष कार्य, हमारे मामले में __builtin_popcount एक संख्या के द्विआधारी संकेतन में इकाइयों की गिनती के लिए, और __builtin_ctz पहले सबसे छोटी इकाई से पहले शून्य की संख्या के लिए। इस तरह के कार्य कुछ संकलक में नहीं दिखाई दे सकते हैं। विंडोज के लिए, ऐसे एनालॉग उपयुक्त हैं:

 #ifdef _MSC_VER # include <intrin.h> # define __builtin_popcount __popcnt #endif 

• एरे संगठन - एक छोटा आकार पहले आता है। उदाहरण के लिए, सरणी का उपयोग करना बेहतर है [2] [३] [५००] [१०२०] की तुलना में [१०२०] [५००] [३] [२]।
• सबसे महत्वपूर्ण बात यह है कि कोड की सामान्य पर्याप्तता और गणना के लिए अनावश्यक चिंताओं से बचा जाता है।

क्या काम का समय कम करता है

• संकलन करते समय -O2 ध्वज।
• एल्गोरिथ्म में पूरी तरह से हल की गई पंक्ति / कॉलम को फिर से नहीं फेंकने के लिए, आप प्रत्येक पंक्ति के लिए झंडे को एक अलग std :: वेक्टर / सरणी में सेट कर सकते हैं, उन्हें एक पूर्ण समाधान के साथ चिह्नित कर सकते हैं, और न जाने दें यदि हल करने के लिए अधिक कुछ नहीं है।
• एक गतिशील समस्या के बहु-पुनरावृत्ति समाधान की बारीकियों से पता चलता है कि एक विशेष सरणी जिसमें पहले से ही "गणना की गई" टुकड़ों को चिह्नित करने वाले झंडे होते हैं, हर बार एक नया समाधान किए जाने पर रीसेट किया जाना चाहिए। हमारे मामले में, यह एक दो-आयामी सरणी / वेक्टर है, जहां पहला आयाम समूहों की संख्या है, दूसरा वर्तमान सेल है (ऊपर एपिकविन स्यूडोकोड देखें, जहां यह सरणी नहीं है, लेकिन विचार स्पष्ट है)। शून्य करने के बजाय, आप ऐसा कर सकते हैं - हमारे पास "टाइमर" वैरिएबल है, और सरणी में अंतिम "समय" दिखाने वाले नंबर शामिल हैं, जब इस टुकड़े को आखिरी बार देखा गया था। एक नया कार्य शुरू करते समय, "टाइमर" 1 से बढ़ जाता है। बूलियन ध्वज की जांच करने के बजाय, आपको सरणी तत्व और "टाइमर" की समानता की जांच करनी चाहिए। यह उन मामलों में विशेष रूप से प्रभावी है, जहां सभी संभव राज्यों से एल्गोरिदम द्वारा कवर किया गया है (जिसका अर्थ है कि सरणी को शून्य करना "क्या हमने पहले ही इस पर विचार किया था" समय का एक स्वस्थ हिस्सा लेता है)।
• एसटीएल या अधिक पर्याप्त चीजों में एनालॉग्स के साथ एक ही प्रकार (असाइनमेंट, आदि के साथ छोरों) के सरल संचालन की जगह। कभी-कभी यह साइकिल से भी तेज काम करता है।
• std::vector<bool> C ++ में सभी बूलियन मानों को अलग-अलग बिट्स में संख्याओं में संपीड़ित करता है, जो कि थोड़ा धीमी पहुंच पर काम करता है अगर यह पते पर एक नियमित मूल्य था। यदि कोई प्रोग्राम ऐसे मानों का उपयोग करता है, तो बहुत बार, पूर्णांक प्रकार के साथ बूल की जगह प्रदर्शन पर अच्छा प्रभाव डाल सकती है।
• अन्य कमजोरियों को प्रोफाइलर्स के माध्यम से खोजा जा सकता है और उन्हें संपादित किया जा सकता है। मैं खुद Valgrind का उपयोग करता हूं, इसका प्रदर्शन विश्लेषण kCachegrind के माध्यम से देखने के लिए सुविधाजनक है। प्रोफाइलर कई आईडीई में निर्मित होते हैं।

बेंचमार्क पर इस तरह के डेटा प्राप्त करने के लिए ये संपादन पर्याप्त थे:

 izaron@izaron:~/nonograms/build$ ./nonograms_solver -x ../../nonogram/source2/ -e [2018-08-04 22:57:40.432] [Nonograms] [info] Starting a benchmark... [2018-08-04 22:58:03.820] [Nonograms] [info] Average time: 0.00497556, Median time: 0.00302781, Max time: 0.215925 [2018-08-04 22:58:03.820] [Nonograms] [info] Top 10 heaviest nonograms: [2018-08-04 22:58:03.820] [Nonograms] [info] 0.215925 seconds, file 9596 [2018-08-04 22:58:03.820] [Nonograms] [info] 0.164579 seconds, file 4462 [2018-08-04 22:58:03.820] [Nonograms] [info] 0.105828 seconds, file 15831 [2018-08-04 22:58:03.820] [Nonograms] [info] 0.08827 seconds, file 18353 [2018-08-04 22:58:03.820] [Nonograms] [info] 0.0874717 seconds, file 10590 [2018-08-04 22:58:03.820] [Nonograms] [info] 0.0831248 seconds, file 4649 [2018-08-04 22:58:03.820] [Nonograms] [info] 0.0782811 seconds, file 11922 [2018-08-04 22:58:03.820] [Nonograms] [info] 0.0734325 seconds, file 4655 [2018-08-04 22:58:03.820] [Nonograms] [info] 0.071352 seconds, file 10828 [2018-08-04 22:58:03.820] [Nonograms] [info] 0.0708263 seconds, file 11824 

 izaron@izaron:~/nonograms/build$ ./nonograms_solver -x ../../nonogram/source/ -e -b [2018-08-04 22:59:56.308] [Nonograms] [info] Starting a benchmark... [2018-08-04 23:00:09.781] [Nonograms] [info] Average time: 0.0095679, Median time: 0.00239274, Max time: 0.607341 [2018-08-04 23:00:09.781] [Nonograms] [info] Top 10 heaviest nonograms: [2018-08-04 23:00:09.781] [Nonograms] [info] 0.607341 seconds, file 5126 [2018-08-04 23:00:09.781] [Nonograms] [info] 0.458932 seconds, file 19510 [2018-08-04 23:00:09.781] [Nonograms] [info] 0.452245 seconds, file 5114 [2018-08-04 23:00:09.781] [Nonograms] [info] 0.19975 seconds, file 18627 [2018-08-04 23:00:09.781] [Nonograms] [info] 0.163028 seconds, file 5876 [2018-08-04 23:00:09.781] [Nonograms] [info] 0.161675 seconds, file 17403 [2018-08-04 23:00:09.781] [Nonograms] [info] 0.153693 seconds, file 12771 [2018-08-04 23:00:09.781] [Nonograms] [info] 0.146731 seconds, file 5178 [2018-08-04 23:00:09.781] [Nonograms] [info] 0.142732 seconds, file 18244 [2018-08-04 23:00:09.781] [Nonograms] [info] 0.136131 seconds, file 19385 

आप देख सकते हैं कि औसत काले और सफेद रंग के क्रॉसवर्ड रंग की तुलना में "कठिन" हैं। यह खेल प्रेमियों की टिप्पणियों की पुष्टि करता है, जो यह भी मानते हैं कि "रंग" औसत आसान पर हल किया गया है।

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

आगे अनुकूलन

निम्नलिखित तरीकों से कार्यक्रम के प्रदर्शन में काफी सुधार हो सकता है। उनमें से कुछ सभी मामलों में काम नहीं करते हैं, लेकिन कुछ शर्तों के तहत।

• सी-स्टाइल और अन्य 1972 में रीराइटिंग कोड। हम एनालॉग प्रतिपक्ष के साथ ifstream को प्रतिस्थापित करते हैं, सरणियों के साथ वैक्टर, सभी संकलक विकल्प सीखते हैं और प्रत्येक प्रोसेसर घड़ी चक्र के लिए लड़ते हैं।
• साथ में चलाना। उदाहरण के लिए, कोड में एक टुकड़ा होता है जहां पंक्तियों को क्रमिक रूप से अपडेट किया जाता है, फिर कॉलम:

  ... if (!UpdateGroupsState(solver, dead_rows, row_groups, row_masks)) { return false; } if (!UpdateGroupsState(solver, dead_cols, col_groups, col_masks)) { return false; } return true; 

ये फ़ंक्शंस एक-दूसरे से स्वतंत्र होते हैं और उनके पास चर सॉलेवर (टाइप वनलाइनसोलर) को छोड़कर, साझा मेमोरी नहीं होती है, इसलिए आप दो सॉल्वर ऑब्जेक्ट्स बना सकते हैं (यहाँ, जाहिर है, केवल एक सॉल्वर है) और एक ही फ़ंक्शन में दो थ्रेड शुरू करें। इसका प्रभाव यह है: रंग वर्ग में, "सबसे कठिन" को दो बार तेजी से हल किया जाता है, काले और सफेद में एक तिहाई तेजी से होता है, और थ्रेड बनाने की अपेक्षाकृत उच्च लागत के कारण औसत समय में वृद्धि हुई है।

लेकिन सामान्य तौर पर, मैं इसे वर्तमान कार्यक्रम में सही तरीके से करने की सलाह नहीं दूंगा और शांति से इसका उपयोग करूंगा - सबसे पहले, थ्रेड बनाना एक महंगा ऑपरेशन है, आपको लगातार माइक्रोसेकंड कार्यों के लिए थ्रेड्स नहीं बनाने चाहिए, और दूसरी बात, प्रोग्राम के फैसलों के कुछ संयोजन के साथ, थ्रेड्स को संदर्भित कर सकते हैं जिसमें से बाहरी मेमोरी, उदाहरण के लिए, जब एक समाधान के चित्र बनाते हैं - इसे ध्यान में रखा जाना चाहिए और सुरक्षित किया जाना चाहिए।

यदि कार्य गंभीर था और मेरे पास बहुत सारी डेटा और मल्टी-कोर मशीनें होंगी, तो मैं और भी आगे बढ़ूंगा - आप कई निरंतर थ्रेड्स बना सकते हैं, प्रत्येक की अपनी OneLineSolver ऑब्जेक्ट होगी, और एक अन्य थ्रेड-सुरक्षित संरचना जो काम के वितरण और मांग पर नियंत्रण रखती है। यह समाधान के लिए अगली पंक्ति / स्तंभ का संदर्भ देता है। एक और समस्या को हल करने के बाद थ्रेड्स संरचना को फिर से कुछ और हल करने के लिए मुड़ते हैं। सिद्धांत रूप में, पिछले एक को पूरा किए बिना एक नॉनोग्राम समस्या शुरू की जा सकती है, उदाहरण के लिए, जब यह संरचना पारस्परिक और सभी कोशिकाओं में लगी होती है, और फिर कुछ प्रवाह मुक्त होते हैं और कुछ भी नहीं करते हैं। CUDA के माध्यम से GPU पर अधिक समानांतरकरण किया जा सकता है - कई विकल्प हैं।

• क्लासिक डेटा संरचनाओं का उपयोग करना। कृपया ध्यान दें - जब मैंने रंग नॉनोग्राम के समाधान का छद्म कोड दिखाया, तो CanInsertColor और PlaceColor फ़ंक्शंस बिल्कुल भी काम नहीं करते हैं $$$O (1)$ , काले और सफेद nonograms के विपरीत। यह एक कार्यक्रम में इस तरह दिखता है:

 bool OneLineSolver::CanPlaceColor(const vector<int>& cells, int color, int lbound, int rbound) { // Went out of the border if (rbound >= cells.size()) { return false; } // We can paint a block of cells with a certain color if and only if it is // possible for all cells to have this color (that means, if every cell // from the block has color-th bit set to 1) int mask = 1 << color; for (int i = lbound; i <= rbound; ++i) { if (!(cells[i] & mask)) { return false; } } return true; } void OneLineSolver::SetPlaceColor(int color, int lbound, int rbound) { // Every cell from the block now can have this color for (int i = lbound; i <= rbound; ++i) { result_cells_[i] |= (1 << color); } } 

यही है, यह लाइन के लिए, के लिए काम करता है $$$O (N)$ (बाद में बस ऐसे कोड के अर्थ का स्पष्टीकरण होगा)।

आइए देखें कि आप सबसे अच्छी जटिलता कैसे प्राप्त कर सकते हैं। CanPlaceColor लें। यह फ़ंक्शन यह जांचता है कि खंड में वेक्टर की सभी संख्याओं के बीच $$$[लिबर, रबड]$ बिट संख्या $$$रंग$ 1. इस के बराबर, आप ले सकते हैं $$$और$ इस सेगमेंट के सभी नंबर और बिट नंबर की जांच करें $$$रंग$ । इस तथ्य का उपयोग करते हुए कि ऑपरेशन $$$और$ कम्यूटेटिव , साथ ही योग, न्यूनतम / अधिकतम, उत्पाद, या ऑपरेशन $$$Xor$ , त्वरित गिनती के लिए $$$और$ , . :

1. SQRT-. $$$O(\sqrt{N})$ , $$$O(\sqrt{N})$ । .
2. . $$$O(N\log{N})$ , $$$O(\log{N})$ । .
3. (Sparse Table). $$$O(N\log{N})$ , $$$O(1)$ । .

, - ( $$$O(N)$ , $$$O(1)$ ) , , , $$$\ varphi$ , $$$\varphi(\alpha, \beta) \in \{\alpha, \beta\}$ , — (, ...)

SetPlaceColor . . SQRT- ( " "). - .

- — .

, — , ? :

1. . $$$\log$ , , — ( magic number , ). , $$$N=10^{5}$ , $$$O(N^2)$ 10 , $$$O(N\log{N})$ 0.150 , $$$एन$ , . , ( ): $$$O(N\sqrt{N})$ versus $$$O(N\log^2{N})$ । $$$एन$ ( ) — 15-30.
2. , .

— , - — $$$एन$ , . , ~25% ~11% , . - , , , .

— , . .

• . , , - . : , , "" ? , , ! . , .
• (, 1337 1000x1000) . std::bitset , — , .

, . "" . , C++ ( rope , ), hashtable , 3-6 / 4-10 /, unordered_map. , boost.

ROFL Omitting Format Language

, , , -.

ROFL — , "GNU's Not Unix". , , , , , . Omitting — (, , : — ).

, Matroska — 4 [52][4F][46][4C], , , , 3 , — , .

, MIT, — , .

GitHub . , , (, ). Magick++ args .

, ( ). nonograms.ru , , .

nonograms.ru .. KyberPrizrak , , , ! nonograms.ru, .

.