आसन्नता सूची

Question

के लिए स्मृति आवश्यकताओं को कम करने के लिए मैं adjacency_list < vecS, vecS, bidirectionalS का उपयोग कर रहा हूं ...> बड़े पैमाने पर। मेरे पास एक बार में इतने सारे ग्राफ लोड किए गए हैं कि स्मृति कोई समस्या बन जाती है। मैं स्थैतिक प्रोग्राम विश्लेषण कर रहा हूं और बूस्ट ग्राफ़ में अलग-अलग बाइनरी के कॉलग्राफ और फ़्लोग्राफ स्टोर करता हूं। इस प्रकार मेरे पास कई दस हजार फ़ंक्शन == फ़्लोग्राफ और एक विशाल कॉलग्राफ हो सकते हैं। मैं अभी भी बीजीएल का उपयोग करते हुए अपने ग्राफ के लिए मेमोरी उपयोग को कम करना चाहता हूं।

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

अधिक प्रश्न:
1) वर्टेक्स और एज गुणों का उपयोग करने की स्मृति ओवरहेड क्या है? मैं उनमें से कुछ हैं।
2) क्या बीजीएल को idiom फिट करने के लिए संकीर्णता का उपयोग करने के लिए मनाने के लिए संभव है? जैसा कि मैं समझता हूं कि आसन्नता सूचियां किनारों को जोड़ने के लिए push_back का उपयोग करती हैं। क्या को स्वैप करके मेमोरी उपयोग को कम करना संभव है जिसके परिणामस्वरूप वेक्टर स्वयं की एक प्रति है? शायद पूरे ग्राफ की प्रतिलिपि बनाकर?
3) क्या बीजीएल के साथ बूस्ट पूल आवंटकों का उपयोग करना संभव है? अब तक जैसा कि मैं बता सकता हूं कि बीजीएल वर्तमान में बहुत से छोटे आवंटन करता है - मैं वास्तव में अंतरिक्ष और रनटाइम दक्षता कारणों से बचाना चाहता हूं।

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

सादर,

Sören 

Answer 1

बीजीएल में "संपीड़ित स्पैस पंक्ति" ग्राफ नामक एक छोटा ज्ञात ग्राफ प्रकार है। यह काफी नया प्रतीत होता है और सूचकांक पृष्ठों से जुड़ा हुआ नहीं है। हालांकि ग्राफ जितना संभव हो सके उतना छोटा ग्राफ प्राप्त करने के लिए यह एक सुंदर छोटी सी चाल को नियोजित करता है। http://www.boost.org/doc/libs/1_40_0/libs/graph/doc/compressed_sparse_row.html

हमारे कुछ ग्राफों के लिए इसका उपयोग करना मैं पहले से ही कुल स्मृति उपयोग को 20% तक कम करने में सक्षम हूं - इसलिए यह वास्तव में एक बहुत ही अनुकूल अनुकूलन है।

यह वैक्टरों में कशेरुक/किनारे के गुणों को भी संग्रहीत करता है, इस प्रकार उन लोगों के लिए सबसे छोटा संभव ओवरहेड भी प्रदान करता है।

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

Answer 2

बीजीएल के बाद से interoperate with legacy or custom graphs लिए बनाया गया है, तो आप शायद अपने खुद के ग्राफ लेखन को सबसे अच्छा कर रहे हैं।

Answer 3

1. ओवरहेड निर्भर करता है कि आप किस संस्करण का उपयोग कर रहे हैं और क्या आप "बंडल" गुणों के लिए गए हैं या नहीं। मैंने केवल बंडल गुणों का उपयोग किया है और कोड पढ़ रहा हूं, मुझे उम्मीद है कि प्रत्येक प्रॉपर्टी बंडल आपको 2 पॉइंटर्स + आपके द्वारा उपयोग किए जा रहे बंडल प्रकार का आकार + प्रत्येक संलग्न गुणों का आकार देगा। बाइनरी afaik में कोई भी अवधारणा जांच सामान छोड़ दिया गया है। चूंकि आपके पास कोड है, फिर भी लागत का आकलन क्यों न करें? यदि आपके पास ज्ञात आकार के बफर में ज्ञात आकारों के ग्राफ उत्पन्न करने में सहायता करने के लिए कोई टूलिंग नहीं है। आखिरकार कुछ असफल हो जाएगा और उस बिंदु पर आपको मायने रखता था।

2. क्या आपने adjacency_list<blah>.swap(adjacency_list& x) पर कॉल करने का प्रयास किया है? मुझे उम्मीद है कि कंटेनरों को उचित रूप से कम कर देगा।

3. ???

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

Answer 4

के जवाब के रूप में:

3) यह बीजीएल साथ बढ़ावा पूल allocators उपयोग करने के लिए संभव है? जहां तक ​​मैं बता सकता हूं कि बीजीएल वर्तमान में बहुत से छोटे आवंटन करता है - मैं वास्तव में अंतरिक्ष और रनटाइम दक्षता कारणों से बचना चाहता हूं।

कोड here से नकल:

template <class Allocator> 
    struct list_with_allocatorS { }; 

    namespace boost { 
    template <class Alloc, class ValueType> 
    struct container_gen<list_with_allocatorS<Alloc>, ValueType> 
    { 
     typedef typename Alloc::template rebind<ValueType>::other Allocator; 
     typedef std::list<ValueType, Allocator> type; 
    }; 
    } 

    // now you can define a graph using std::list 
    // and a specific allocator 
    typedef adjacency_list< list_with_allocatorS< std::allocator<int> >, vecS, directedS> MyGraph;