व्यापक खोज अनुकूलन: 10 अरब राज्यों के साथ ग्राफ को कैसे संसाधित करें

कुछ महीने पहले, मुझे अंततः यह स्वीकार करना पड़ा कि मैं स्नेपबर्ड पहेली के कुछ स्तरों से गुजरने के लिए पर्याप्त स्मार्ट नहीं था। कुछ आत्मसम्मान हासिल करने का एकमात्र तरीका एक सॉल्वर लिखना था। तो मैं दिखावा कर सकता था कि पहेली को हल करने के लिए एक कार्यक्रम बनाना लगभग इसे स्वयं हल करने के समान है। परिणामी C ++ प्रोग्राम का कोड Github पर उपलब्ध है। लेख में माना गया कोड का मुख्य भाग search.h और compress.h में लागू किया गया है। इस पोस्ट में, मैं मुख्य रूप से चौड़ाई-प्रथम खोज को अनुकूलित करने के बारे में बात करूंगा जिसमें 4 जीबी में फिट होने के लिए 50-100 जीबी मेमोरी की आवश्यकता होगी।

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

किसी न किसी अनुमान से पता चला है कि सबसे बड़ी पहेली में, सभी सममित पदों को समाप्त करने के बाद, लगभग 10 बिलियन राज्य होंगे। अधिकतम घनत्व के साथ राज्य विवरण पैक करने के बाद भी, राज्य का आकार 8-10 बाइट्स था। 100 जीबी मेमोरी के साथ, कार्य तुच्छ होगा, लेकिन 16 जीबी मेमोरी के साथ मेरे होम मशीन के लिए नहीं। और चूंकि क्रोम को उनमें से 12 जीबी की आवश्यकता है, इसलिए मेरी वास्तविक मेमोरी आपूर्ति 4 जीबी के करीब है। इस वॉल्यूम से अधिक होने वाली सभी चीज़ों को डिस्क (पुरानी और जंग लगी हार्ड ड्राइव) में सहेजना होगा।

4 जीबी रैम में 100 जीबी डेटा कैसे फिट करें? या तो ए) राज्यों को उनके मूल के 1/20, पहले से ही अनुकूलित आकार या बी) को निचोड़ने की आवश्यकता होती है, एल्गोरिथ्म को प्रभावी ढंग से राज्यों को डिस्क से या डिस्क से बचाने में सक्षम होना चाहिए, या ग) उपरोक्त दो विधियों का संयोजन, या डी) मुझे और खरीदने की आवश्यकता है रैम या कई दिनों के लिए एक शक्तिशाली वर्चुअल मशीन किराए पर लें। मैंने विकल्प डी पर विचार नहीं किया, क्योंकि यह बहुत उबाऊ है। विकल्प ए और बी को गज़िप का उपयोग करके अवधारणा के प्रमाण के बाद बाहर रखा गया था: 50 एमबी के राज्य विवरण का एक टुकड़ा केवल 35 एमबी तक संकुचित था। यह प्रति राज्य 7 बाइट्स के बारे में है, और मेरी मेमोरी लगभग 0.4 बाइट्स प्रति राज्य है। यही है, विकल्प बी बने रहे, भले ही चौड़ाई पहली खोज माध्यमिक ड्राइव पर भंडारण के लिए असुविधाजनक लग रही थी।

सामग्री

यह काफी लंबा पोस्ट है, इसलिए यहां निम्नलिखित अनुभागों का संक्षिप्त विवरण दिया गया है:

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

विस्तृत खोज "पाठ्यपुस्तक द्वारा"

चौड़ाई-प्रथम खोज क्या दिखती है और आपको इसमें डिस्क का उपयोग क्यों नहीं करना चाहिए? इस छोटी सी परियोजना से पहले, मैंने "पाठ्यपुस्तकों से," उदाहरण के लिए, केवल शब्दों के विकल्प पर विचार किया, जैसे:

def bfs(graph, start, end): visited = {start} todo = [start] while todo: node = todo.pop_first() if node == end: return True for kid in adjacent(node): if kid not in visited: visited.add(kid) todo.push_back(kid) return False 

कार्यक्रम द्वारा नए उम्मीदवार नोड बनाने की प्रक्रिया में, प्रत्येक नोड को पहले से ही देखे गए नोड्स की हैश तालिका के साथ जांचा जाता है। यदि यह पहले से ही हैश तालिका में है, तो नोड को अनदेखा किया जाता है। अन्यथा, इसे कतार और हैश तालिका में जोड़ा जाता है। कभी-कभी कार्यान्वयन में, जानकारी "देखी गई" नोड्स में दर्ज की जाती है, और एक विदेशी तालिका में नहीं; लेकिन यह एक जोखिम भरा अनुकूलन है और यह पूरी तरह से असंभव है यदि ग्राफ़ को स्पष्ट रूप से निर्दिष्ट किया गया है।

हैश टेबल समस्याग्रस्त क्यों है? क्योंकि हैश टेबल पूरी तरह से रैंडम मेमोरी एक्सेस पैटर्न बनाने के लिए हैं। यदि वे नहीं करते हैं, तो यह एक खराब हैश फ़ंक्शन है, और हैश तालिका के टकराव के कारण खराब प्रदर्शन की संभावना होगी। यह रैंडम एक्सेस पैटर्न प्रदर्शन की समस्या पैदा कर सकता है, भले ही डेटा मेमोरी में फिट हो: एक विशाल हैश टेबल तक पहुंचने से कैश मिस और एसोसिएटेड ट्रांसलेशन बफ़र्स (टीएलबी) होने की संभावना है। लेकिन क्या होगा अगर डेटा का एक महत्वपूर्ण हिस्सा डिस्क पर है, और मेमोरी में नहीं? परिणाम भयावह होंगे: प्रति खोज ऑपरेशन 10 एमएस के आदेश के कुछ।

10 बिलियन यूनिक स्टेट्स के साथ, डिस्क I / O का इंतजार करने में केवल हैश टेबल तक पहुंचने में हमें लगभग चार महीने लगेंगे। यह हमें शोभा नहीं देता; कार्य को निश्चित रूप से परिवर्तित करने की आवश्यकता है ताकि कार्यक्रम एक ही पास में बड़े डेटा पैकेट को संसाधित कर सके।

छँटाई और विलय के साथ बीएफएस

यदि हम डेटा एक्सेस ऑपरेशंस को संकुल में अधिक से अधिक एकीकृत करना चाहते हैं, तो अधिकतम प्राप्य सन्निकटन क्या होगा? चूंकि कार्यक्रम को यह नहीं पता है कि कौन सी नोड्स को गहराई N + 1 की प्रक्रिया में संसाधित करना है जब तक कि परत N को पूरी तरह से संसाधित नहीं किया जाता है, यह स्पष्ट लगता है कि कम से कम एक बार गहराई से राज्यों को डुप्लिकेट करना आवश्यक है।

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

सेट के साथ दो संचालन को जोड़ा जा सकता है ताकि वे दोनों थ्रेड्स के साथ एक पास में काम करें। वास्तव में, हम दोनों धाराओं को देखते हैं, छोटे तत्व को संसाधित करते हैं, और फिर उस धारा के साथ आगे बढ़ते हैं, जिसमें से तत्व लिया गया था (या शुरुआत में दोनों तत्व समान हैं)। दोनों ही मामलों में, हम आइटम को नए विज़िट किए गए सेट में जोड़ते हैं। फिर हम नए राज्यों की धारा के साथ आगे बढ़ते हैं, और नए टूडू सेट में एक तत्व भी जोड़ते हैं:

 def bfs(graph, start, end): visited = Stream() todo = Stream() visited.add(start) todo.add(start) while True: new = [] for node in todo: if node == end: return True for kid in adjacent(node): new.push_back(kid) new_stream = Stream() for node in new.sorted().uniq(): new_stream.add(node) todo, visited = merge_sorted_streams(new_stream, visited) return False # Merges sorted streams new and visited. Return a sorted stream of # elements that were just present in new, and another sorted # stream containing the elements that were present in either or # both of new and visited. def merge_sorted_streams(new, visited): out_todo, out_visited = Stream(), Stream() while visited or new: if visited and new: if visited.peek() == new.peek(): out_visited.add(visited.pop()) new.pop() elif visited.peek() < new.peek(): out_visited.add(visited.pop()) elif visited.peek() > new.peek(): out_todo.add(new.peek()) out_visited.add(new.pop()) elif visited: out_visited.add(visited.pop()) elif new: out_todo.add(new.peek()) out_visited.add(new.pop()) return out_todo, out_visited 

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

सैद्धांतिक प्रदर्शन 100 गहराई स्तर पर डेटा के सरलीकृत वितरण के साथ कैसा दिखेगा, जिसमें से प्रत्येक में 100 मिलियन राज्य हैं? औसत अवस्था 50 बार पढ़ी और लिखी जाएगी। यह 10 बाइट्स / स्टेट * 5 बिलियन स्टेट्स * 50 = 2.5 टीबी देता है। मेरी हार्ड ड्राइव 100 एमबी / एस की औसत गति से कथित रूप से पढ़ और लिख सकती है, अर्थात, औसतन I / O लगेगा (2 * 2.5 टीबी) / (100 एमबी / एस) = ~ 50k / s = ~ 13 घंटे । यह पिछले परिणाम (चार महीने) की तुलना में कुछ कम ऑर्डर है!

यह भी ध्यान देने योग्य है कि यह सरलीकृत मॉडल नए उत्पन्न राज्यों के आकार को ध्यान में नहीं रखता है। मर्ज चरण से पहले, उन्हें सॉर्टिंग + डुप्लीकेशन के लिए मेमोरी में संग्रहीत किया जाना चाहिए। हम इसे नीचे दिए गए अनुभागों में शामिल करेंगे।

दबाव

परिचय में, मैंने कहा कि शुरुआती प्रयोगों में, राज्य संपीड़न में आशाजनक नहीं था, और संपीड़न अनुपात केवल 30% था। लेकिन एल्गोरिथ्म में परिवर्तन करने के बाद, राज्य सुव्यवस्थित हो गए। उन्हें संपीड़ित करने के लिए बहुत आसान होना चाहिए।

इस सिद्धांत का परीक्षण करने के लिए, मैंने 14.6 मिलियन राज्यों की पहेली के साथ zstd का उपयोग किया, जिनमें से प्रत्येक का आकार 8 बाइट्स था। छंटाई के बाद, उन्हें प्रति राज्य औसतन 1.4 बाइट्स पर संकुचित किया गया था। यह एक गंभीर कदम की तरह लगता है। यह पूरे कार्यक्रम को स्मृति में चलाने के लिए पर्याप्त नहीं है, लेकिन यह डिस्क I / O समय को कुछ घंटों तक कम कर सकता है।

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

क्या यह सिद्धांत बीएफएस राज्य रिकॉर्ड पर लागू किया जा सकता है? ऐसा लगता है कि यह संभव होना चाहिए। पीएनजी के साथ के रूप में, हमारे पास एक निरंतर रेखा आकार है, और हम आसन्न लाइनों के समान होने की उम्मीद कर सकते हैं। घटाव / जोड़ फिल्टर के साथ पहले नमूने, zstd के बाद, संपीड़न दर में एक और 40% की वृद्धि के कारण: प्रति राज्य 0.87 बाइट्स। फ़िल्टरिंग ऑपरेशन तुच्छ हैं, इसलिए, सीपीयू की खपत के दृष्टिकोण से, वे व्यावहारिक रूप से "मुक्त" हैं।

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

मान लीजिए हमारे पास आसन्न पंक्तियाँ हैं R1 = [1, 2, 3, 4] और R2 = [1, 2, 6, 4]। R2 आउटपुट करते समय, हम प्रत्येक बाइट की तुलना पिछली पंक्ति के समान बाइट से करते हैं, और 0 एक मैच का संकेत देगा, और 1 एक बेमेल का संकेत देगा: diff = [0, 0, 1, 0]। फिर हम इस बिटमैप को पास करते हैं, जिसे VarInt के रूप में एन्कोड किया गया है, इसके बाद केवल बाइट्स हैं जो पिछली पंक्ति से मेल नहीं खाते हैं। इस उदाहरण में, हमें दो बाइट्स मिलते हैं 0b00000100 6. अपने आप में, यह फ़िल्टर संदर्भ डेटा को 2.2 बाइट्स / स्थिति में संपीड़ित करता है। लेकिन + zstd फ़िल्टर के संयोजन से, हमने डेटा आकार को 0.42 बाइट्स / स्थिति में घटा दिया। या, इसे दूसरे तरीके से कहें, तो यह मात्रा 3.36 बिट्स प्रति राज्य है, जो हमारे अनुमानित गणना किए गए संकेतकों की तुलना में थोड़ा अधिक है, यह सुनिश्चित करने के लिए कि सभी डेटा रैम में फिट होते हैं।

व्यवहार में, संपीड़न अनुपात में सुधार होता है क्योंकि सॉर्ट किए गए सेट सघन हो जाते हैं। जब खोज उस बिंदु तक पहुंचती है जहां स्मृति समस्याओं का कारण बनने लगती है, तो संपीड़न दर बहुत बेहतर हो सकती है। सबसे बड़ी समस्या यह है कि अंत में हमें 4.6 बिलियन विज़िट किए गए राज्य मिलते हैं। छांटने के बाद, ये राज्य 405 एमबी पर कब्जा कर लेते हैं और ऊपर प्रस्तुत योजना के अनुसार संकुचित होते हैं। यह हमें प्रति राज्य 0.7 बिट्स देता है। अंत में, संपीड़न और अपघटन कार्यक्रम के CPU समय का लगभग 25% लेता है, लेकिन यह स्मृति खपत को सौ गुना कम करने के लिए एक उत्कृष्ट समझौता है।

उपरोक्त फ़िल्टर प्रत्येक पंक्ति पर VarInt हेडर के कारण थोड़ा महंगा लगता है। ऐसा लगता है कि कम सीपीयू लागत या जटिलता में मामूली वृद्धि की लागत पर इसे अपग्रेड करना आसान है। मैंने कई अलग-अलग विकल्पों की कोशिश की, स्तंभों द्वारा डेटा ट्रांसपोज़ करना, या बड़े ब्लॉक में बिट मास्क लिखना, आदि। ये विकल्प अकेले बहुत अधिक संपीड़न अनुपात उत्पन्न करते हैं, लेकिन जब zstd द्वारा फ़िल्टर आउटपुट को संपीड़ित किया गया था, तब भी प्रदर्शन नहीं किया था। और यह किसी प्रकार की zstd त्रुटि नहीं थी, gzip और bzip2 के परिणाम समान थे। मेरे पास इस बारे में कोई विशेष रूप से सरल सिद्धांत नहीं हैं कि क्यों इस विशेष प्रकार की कोडिंग अन्य विकल्पों की तुलना में संपीड़न में बहुत बेहतर निकली।

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

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

ओह-ओह, मैंने धोखा दिया!

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

पहले तो ऐसा लगता है कि इस समस्या को हल करना आसान है। राज्यों के सेट को इकट्ठा करने के बजाय, आपको मूल राज्यों के साथ राज्य संबंधों को इकट्ठा करने की आवश्यकता है। फिर, समाधान खोजने के बाद, आप बस अंत से शुरुआत तक माता-पिता के समाधान की सूची से वापस जा सकते हैं। हैश टेबल आधारित समाधान के लिए, यह कुछ इस तरह दिखेगा:

 def bfs(graph, start, end): visited = {start: None} todo = [start] while todo: node = todo.pop_first() if node == end: return trace_solution(node, visited) for kid in adjacent(node): if kid not in visited: visited[kid] = node todo.push_back(kid) return None def trace_solution(state, visited): if state is None: return [] return trace_solution(start, visited[state]) + [state] 

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

एकाधिक आउटपुट के साथ सॉर्ट + मर्ज करें

बहुत अंत में, समाधान पर वापस लौटते समय, कार्यक्रम को केवल राज्यों / मूल राज्यों के बंडलों की आवश्यकता होगी। इसलिए, हम समानांतर में दो डेटा संरचनाओं को संग्रहीत कर सकते हैं। दौरा के दौरान पहले से पुनर्गठित के रूप में दौरा किया राज्यों के सेट का दौरा जारी रहेगा। माता-पिता कम से कम राज्य / मूल राज्य जोड़े की एक छँटाई सूची है जो ओवरराइट नहीं किए गए हैं। प्रत्येक मर्ज ऑपरेशन के बाद, "स्टेट + पैरेंट स्टेट" जोड़ी को माता-पिता में जोड़ा जाता है।

 def bfs(graph, start, end): parents = Stream() visited = Stream() todo = Stream() parents.add((start, None)) visited.add(start) todo.add(start) while True: new = [] for node in todo: if node == end: return trace_solution(node, parents) for kid in adjacent(node): new.push_back(kid) new_stream = Stream() for node in new.sorted().uniq(): new_stream.add(node) todo, visited = merge_sorted_streams(new_stream, visited, parents) return None # Merges sorted streams new and visited. New contains pairs of # key + value (just the keys are compared), visited contains just # keys. # # Returns a sorted stream of keys that were just present in new, # another sorted stream containing the keys that were present in either or # both of new and visited. Also adds the keys + values to the parents # stream for keys that were only present in new. def merge_sorted_streams(new, visited, parents): out_todo, out_visited = Stream(), Stream() while visited or new: if visited and new: visited_head = visited.peek() new_head = new.peek()[0] if visited_head == new_head: out_visited.add(visited.pop()) new.pop() elif visited_head < new_head: out_visited.add(visited.pop()) elif visited_head > new_head: out_todo.add(new_head) out_visited.add(new_head) out_parents.add(new.pop()) elif visited: out_visited.add(visited.pop()) elif new: out_todo.add(new.peek()[0]) out_visited.add(new.peek()[0]) out_parents.add(new.pop()) return out_todo, out_visited 

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

अदला-बदली

छद्म कोड में एक और विवरण को अनदेखा किया गया है: डिस्क I / O के लिए कोई स्पष्ट कोड नहीं है, लेकिन केवल सार स्ट्रीम इंटरफ़ेस। स्ट्रीम एक फ़ाइल स्ट्रीम या मेमोरी के अंदर एक सरणी हो सकती है, लेकिन हमने इस कार्यान्वयन विवरण को अनदेखा कर दिया। इसके बजाय, छद्म कोड एक मेमोरी एक्सेस पैटर्न बना रहा है जो डिस्क के इष्टतम उपयोग की अनुमति देता है। एक आदर्श दुनिया में, यह पर्याप्त होगा, और बाकी को ओएस वर्चुअल मेमोरी सबसिस्टम द्वारा लिया जा सकता है।

लेकिन ऐसा नहीं होता है, कम से कम लिनक्स पर। कुछ बिंदु पर (डेटा के कामकाजी सेट को मेमोरी के आकार के लिए संपीड़ित किया जा सकता है), मुझे लगभग 11 घंटे चलने का कार्यक्रम मिला और डेटा मुख्य रूप से डिस्क पर सहेजा गया। फिर मैंने प्रोग्राम को फ़ाइलों में संग्रहीत करने के बजाय अनाम पृष्ठों का उपयोग किया, और एक ही ड्राइव पर पर्याप्त आकार की एक स्वैप फ़ाइल का चयन किया। हालांकि, तीन दिन बाद, कार्यक्रम केवल एक चौथाई तरीके से चला गया, और फिर भी, समय के साथ, यह धीमा हो गया। मेरे आशावादी अनुमानों के अनुसार, उसे 20 दिनों में काम पूरा करना था।

मैं स्पष्ट कर दूंगा - यह एक ही कोड और बिल्कुल एक ही एक्सेस पैटर्न था । केवल एक चीज जो बदल गई है वह यह है कि मेमोरी को एक स्पष्ट डिस्क फ़ाइल के रूप में नहीं, बल्कि स्वैप के रूप में सहेजा गया था। लगभग किसी भी सबूत की ज़रूरत नहीं है कि स्वैपिंग पूरी तरह से लिनक्स प्रदर्शन को नष्ट कर देती है, जबकि नियमित फ़ाइल I / O नहीं करता है। मैंने हमेशा यह माना कि यह इस तथ्य के कारण है कि कार्यक्रम रैम को यादृच्छिक अभिगम स्मृति के रूप में मानते हैं। लेकिन ऐसा नहीं है।

यह पता चलता है कि फाइल सेविंग पेज और अनाम पेज वर्चुअल मशीन सबसिस्टम द्वारा अलग-अलग तरीके से हैंडल किए जाते हैं। वे अलग-अलग समाप्ति नीतियों के साथ अलग-अलग LRU कैश में संग्रहीत होते हैं; इसके अलावा, ऐसा लगता है कि उनके पास अलग-अलग रीड / लोड रीड-फॉरवर्ड गुण हैं।

अब मुझे पता है: लिनक्स पर स्वैपिंग की संभावना सबसे अनुकूल परिस्थितियों में भी अच्छी तरह से काम नहीं करेगी। यदि पता स्थान के कुछ हिस्सों को डिस्क पर कुछ समय के लिए अनलोड किए जाने की संभावना है, तो स्वैप पर भरोसा करने की तुलना में उन्हें फ़ाइलों में मैन्युअल रूप से सहेजना बेहतर है। मैंने अपने स्वयं के वैक्टरों को लागू करके इसे पूरा किया, जो शुरू में केवल स्मृति में काम करता है, और एक निश्चित आकार सीमा से अधिक होने के बाद, यह एक अस्थायी अलग फ़ाइल में mmap पर स्विच करता है।

विलय से पहले नए राज्यों का संपीड़न

एक सरलीकृत प्रदर्शन मॉडल में, हमने यह मान लिया कि प्रत्येक गहराई पर 100 मिलियन नई स्थितियां होंगी। यह पता चला कि यह वास्तविकता से बहुत दूर नहीं है (सबसे जटिल पहेली में, गहराई की एक परत पर अधिकतम 150 मिलियन से अधिक अद्वितीय नए राज्य)। लेकिन यह मापा नहीं जाना है; विलय से पहले काम करने वाला सेट न केवल अद्वितीय राज्यों के साथ जुड़ा हुआ है, बल्कि इस पुनरावृत्ति के लिए सभी राज्यों के साथ जुड़ा हुआ है। यह आंकड़ा प्रति परत गहराई में 880 मिलियन उत्पादन राज्यों तक पहुंचता है। इन 880 मिलियन राज्यों) को छँटाई के लिए यादृच्छिक अभिगम पैटर्न के साथ संसाधित करने की आवश्यकता है, ख) छँटाई की कमी के कारण प्रभावी ढंग से संकुचित नहीं हो सकते हैं, ग) को मूल राज्य के साथ संग्रहीत किया जाना चाहिए। यह वर्किंग सेट लगभग 16 जीबी का है।

स्पष्ट समाधान: किसी प्रकार की बाहरी छँटाई का उपयोग करें। बस सभी राज्यों को डिस्क पर लिखें, बाहरी सॉर्टिंग, डुप्लिकेट करें और फिर हमेशा की तरह मर्ज करें। सबसे पहले मैंने इस समाधान का उपयोग किया, और यद्यपि यह सबसे अधिक समाप्त समस्या ए में था, मैं बी और सी के साथ सामना नहीं कर सका।

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

बेशक, 100 मिलियन राज्यों के इन रनों की संपीड़न दरें सभी विज़िट किए गए राज्यों के सेट के संपीड़न के रूप में अच्छी नहीं हैं। लेकिन ऐसे संकेतकों के साथ भी, यह काम करने वाले सेट और डिस्क I / O की आवश्यकताओं दोनों की मात्रा को काफी कम कर देता है। थ्रेड्स की प्राथमिकता कतार को संसाधित करने के लिए आपको कुछ अधिक CPU संसाधनों की आवश्यकता होती है, लेकिन यह अभी भी एक महान समझौता है।

जनक राज्यों पर अंतरिक्ष की बचत

इस स्तर पर, कार्यक्रम के कब्जे वाले अधिकांश हिस्से को मूल राज्यों को संग्रहीत करने पर खर्च किया जाता है, ताकि समाधान खोजने के बाद हम इसकी प्रक्रिया को फिर से बना सकें। सबसे अधिक संभावना है, उन्हें शायद ही अच्छी तरह से निचोड़ा जा सकता है, लेकिन शायद सीपीयू और मेमोरी के बीच किसी तरह का समझौता हो?

S' D+1 S D. S', , - D visited. ( visited, / ). , ; S S'. , .

यदि हम केवल राज्यों के बीच संक्रमण पैदा कर सकते हैं, लेकिन पिछड़े नहीं हैं, तो फिर ऐसा क्यों नहीं? आइए, सभी राज्यों के बारे में गहराई से डी पर जाएँ और देखें कि उन्हें किस तरह के आउटपुट मिलते हैं। यदि आउटपुट पर कुछ राज्य S 'देता है, तो हमें एक उपयुक्त एस मिला। इस योजना के साथ समस्या यह है कि यह कार्यक्रम की कुल सीपीयू खपत को 50% बढ़ा देता है। (100% नहीं, क्योंकि औसतन हम आधे राज्यों को डी की गहराई पर देखकर एस पाएंगे)।

, , , /. - ? (S', S), (S', H(S)), H — 8- -. S S', D. - , . H(S), , , . , 1/256 , , 8-10 1 .

पिछले खंडों में, हमने उच्च-स्तरीय अनुकूलन के अनुक्रम को देखा जो काम करते थे। मैंने उन अन्य चीजों की कोशिश की जो काम नहीं करती थीं, या जो मुझे साहित्य में मिली थीं, लेकिन मैंने तय किया कि इस विशेष मामले में वे काम नहीं करेंगे। यहाँ एक आंशिक सूची है।

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

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

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

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

हालांकि बेंचमार्क हैंयह दिखाते हुए कि हैश-आधारित दृष्टिकोण छँटाई + विलय की तुलना में लगभग 30% तेज है, लेकिन ऐसा लगता है कि वे खाते संपीड़न में नहीं लेते हैं। मैंने अभी यह नहीं देखा कि संपीड़न के लाभों की अस्वीकृति कैसे खुद को सही ठहरा सकती है, इसलिए मैंने ऐसे दृष्टिकोणों के साथ भी प्रयोग नहीं किया।

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

निष्कर्ष

, , . 50-100 500 , . , 50% , - , .

Snakebird Steam , Google Play App Store . , , .