चक्र के साथ एक ग्राफ की "सामयिक" छँटाई

लेख का पूरा शीर्षक O(|V| + |e| log |e|) में समय के साथ चक्र में ग्राफ के साथ "सतत" सामयिक "छँटनी वाला होना चाहिए था O(|V| + |e| log |e|) यह ओवरकिल क्या है।

डिस्क्लेमर: मैं एक प्रोग्रामर हूं, गणितज्ञ नहीं, इसलिए गलत भाषा उन जगहों पर संभव है, जिनके लिए आपको किक करनी चाहिए।

कार्य का सार

मैं समस्या के सूत्रीकरण का विश्लेषण करूंगा, जिसके समाधान को मैं भागों में साझा करना चाहता हूं।

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

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

पुनरावृत्ति की कमी के साथ , सब कुछ सरल है, ट्यूरिंग मशीन और मेमोरी (और विशेष रूप से स्टैक) सीमित है की तुलना में कंप्यूटर काफी कमजोर है। इसलिए, लागू प्रोग्रामिंग में, पुनरावृत्त एल्गोरिदम आमतौर पर पुनरावर्ती लोगों के लिए बेहतर होते हैं।

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

और अब इस सारे कचरे के साथ हम उतारने की कोशिश करेंगे । पोस्ट की शुरुआत में इंगित समय और मेमोरी प्रतिबंधों के ढांचे के भीतर मैं यह सब करूँगा।

समाधान के लिए खोजें

यदि आप टोपोलॉजिकल सॉर्टिंग ( कहन एल्गोरिथम , गहन खोज ) के लिए मौजूदा एल्गोरिदम को देखते हैं, तो यह पता चलता है कि वे सभी, यदि कोई चक्र है, तो "मैं नहीं कर सकता" और काम करना बंद करो।

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

जबकि प्रत्येक दृढ़ता से जुड़े घटक के भीतर नोड्स के आदेश के बारे में कुछ भी विशेष नहीं है, एल्गोरिथम की एक उपयोगी संपत्ति यह है कि किसी भी उत्तराधिकारी से पहले किसी भी दृढ़ता से जुड़े घटक की पहचान नहीं की जाएगी। इसलिए, जिस क्रम में दृढ़ता से जुड़े घटकों की पहचान की जाती है वह दृढ़ता से जुड़े घटकों द्वारा गठित डीएजी के एक रिवर्स टोपोलॉजिकल प्रकार का गठन करता है ।

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


तो, हमारे पास इनपुट पर कोने की एक सूची है और (पियर्स के लिए धन्यवाद) मजबूत कनेक्टिविटी के घटक का एक निश्चित सूचकांक है जिसके आउटपुट पर यह शीर्ष है। अगला कदम उनके घटक की क्रम संख्या के अनुसार लंबवत क्रमबद्ध करना है। ऐसे कार्य के लिए एक एल्गोरिथ्म है, इसे काउंटिंग सॉर्टिंग कहा जाता है, जो O(n) समय में यह प्रदर्शन करता है।

एल्गोरिथ्म को ढेर में इकट्ठा करने की प्रक्रिया में, यह पता चला कि यह तथ्य यह है कि यह विपरीत टोपोलॉजिकल सॉर्टिंग देना स्वाभाविक है, वास्तव में टैरियन से बाहर आ रहा है - फिर ग्राफ की पड़ोसी शाखाएं (उनके बीच एक ऑर्डर संबंध नहीं होने पर पीछे की ओर संख्या होगी, फिर ग्राफ के टुकड़े नहीं होंगे आपस में कोई संबंध रखने के लिए, उल्टे क्रम में होना चाहिए ...

जवाब है

तो अंतिम समाधान:

1. हम मूल सूची के कोने की संख्या। O(|V|)
2. हम प्रत्येक शीर्ष के किनारों को सॉर्ट की संख्या के अनुसार क्रमबद्ध करते हैं, जिस पर किनारे जाता है। O(|e| log |e|)
3. पियर्स एल्गोरिथ्म का उपयोग करते हुए, हम मजबूत कनेक्शन के घटकों को ढूंढते हैं और उन्हें संख्या देते हैं। O(|V|)
4. गिनती करके छंटाई का उपयोग करके, हम दृढ़ता से जुड़े घटकों की संख्या के आधार पर कोने को सॉर्ट करते हैं जो उन्हें प्राप्त हुए थे। O(|V|)

GitHub कोड, जावा, सार्वजनिक डोमेन । यह ध्यान दिया जा सकता है कि छंटाई की स्थिरता सुनिश्चित करने के लिए, पियर्स एल्गोरिथ्म को थोड़ा संशोधित किया गया है और रिवर्स ऑर्डर में कोने को बायपास किया गया है।

लेकिन क्यों ???

और अब पृष्ठभूमि, यह सब क्यों आवश्यक था। गतिशील पुस्तकालयों (.so) को लोड / अनलोड करते समय, glibc को यह निर्णय लेने की आवश्यकता होती है कि किस क्रम में स्थिर वैरिएबल को आरम्भ करना है। चर एक दूसरे पर निर्भर करते हैं, विभिन्न कार्यों पर निर्भर करते हैं, आदि। सामान्य तौर पर, यह सब बहुत ग्राफ बनाता है जिसमें चक्र होते हैं और जिन्हें क्रमबद्ध किया जाना चाहिए।

एक बार, O(n^2) लिए कार्य करने वाले एक बल्कि उप-अपनाने वाला कोड इस कार्य में लगा हुआ था। और सामान्य तौर पर, यह वास्तव में किसी को परेशान नहीं करता है, 2012 तक यह पता चला था कि कोड सही तरीके से काम नहीं कर रहा था और कुछ मामलों में गलत था।

रेडहैट के कठोर लोगों ने सोचा, सोचा और ऊपर से कुछ और चक्रों को खराब कर दिया। समस्या के मामलों की मरम्मत की गई, लेकिन एल्गोरिथ्म O(n^3) लिए काम करना शुरू कर दिया, और यह पहले से ही ध्यान देने योग्य हो गया और कुछ अनुप्रयोगों पर कई दसियों सेकंड लगने लगे, जो 2013 में एक बग था। साथ ही, बग के लेखक ने ऐसे मामलों की खोज की जिसमें एल्गोरिथ्म O(n^3) भी गलत O(n^3) । उन्होंने टेरियन एल्गोरिथ्म का उपयोग करने का सुझाव दिया, हालांकि सुधार के साथ पैच को कभी भी डिज़ाइन नहीं किया गया है।

और समय बीत गया, glibc निर्दयता से धीमा हो गया और 2015 में एल्गोरिथ्म को ठीक करने का एक और प्रयास हुआ । दुर्भाग्य से, असफल, एल्गोरिथ्म को O(n^2) चुना गया था, इसके अलावा ग्राफ की शाखाओं को भ्रमित करने के लिए, जिसके बीच क्रम को परिभाषित नहीं किया गया है।

आज 2019 है, ग्लिब अभी भी धीमा है। समस्या को ठीक करने में मुझे कितना समय लगा, यह देखते हुए कि मैं इसे अंत तक लाऊंगा, 100% से काफी कम है। यह इस तथ्य से और अधिक बढ़ गया है कि GNU कोडिंग स्टाइल कोड, क्रेज़ी टेस्ट रनर ("यदि आप फिर से परीक्षण चलाना चाहते हैं, तो संबंधित .out फ़ाइल को हटाएं"), IDE समर्थन के बिना, C में चीजें हो रही हैं। और अपने पैच पर एक नज़र डालने के लिए ग्लिबक के लिए, आपको कॉपीराइट असाइनमेंट प्रक्रिया से गुजरना होगा, ठीक से पैच जारी करना होगा और शैतान जानता है कि और क्या है। इसलिए, समस्या को हल करने वाले एल्गोरिथ्म का आविष्कार करने के मुद्दे को कम से कम हटाने के लिए, इस पोस्ट को लिखा गया था।