c - डायनामिक ग्राफ में "हीप पॉइंटर स्पेगेटी" से कैसे बचें?




algorithm data-structures (3)

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

सामान्य समस्या

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

मैंने क्या कोशिश की

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

ठोस उदाहरण

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


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


यदि आप वास्तव में स्मृति के लेआउट के बारे में चिंतित हैं, तो इसे स्वयं प्रबंधित करने के लिए उपयुक्त हो सकता है।

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

संरेखण करने के लिए आपको एक चीज सावधान रहना होगा। दोबारा, यदि आप हमेशा एक ही संरचना के आकार के गुणकों में स्मृति आवंटित करेंगे, जो चीजों को आसान बनाता है, अन्यथा यह सुनिश्चित करना एक अच्छा विचार है कि सभी आवंटन 4 बाइट सीमा से शुरू होते हैं, यानी आपके पते के बीच का अंतर आवंटित करें और malloc से प्राप्त प्रारंभ पता 4 का एक बहु है।

ब्लॉक को रखा जाना चाहिए, जैसे एक या अधिक पास के नोड्स के पते के बारे में संकेत देने के लिए आप अपने कस्टम आवंटन कार्यों में अतिरिक्त पैरामीटर पास कर सकते हैं।





cpu-cache