कुशल (समय और स्थान जटिलता) डेटा घने और विरल मैट्रिक्स

Question

के लिए संरचना मैं, जिसमें कारों के साथ एक मैट्रिक्स (1 = BlueCar, 2 = रेडकार, 0 = खाली) संग्रहीत किया जाता है एक फ़ाइल को पढ़ने के लिए।

मैं करने की जरूरत है कि रास्ते में मैट्रिक्स की कारों स्थानांतरित करने के लिए एक एल्गोरिथ्म लिखें:

• नीले ले जाने नीचे;
• लाल वालों को दाएं पर ले जाएं;
• एक बारी जिसमें सभी नीले ले जाएँ और सभी लाल लोगों को स्थानांतरित करने के लिए एक बारी है।

से पहले फ़ाइल पढ़ा है मैं मैट्रिक्स आकार को जानते हैं और अगर यह घने या विरल है नहीं है, इसलिए मैं दो डाटा संरचनाओं (घना के लिए और एक विरल के लिए) और दो एल्गोरिथम को लागू करना है।

मैं सबसे अच्छा समय और स्थान जटिलता संभव तक पहुँचने के लिए की जरूरत है।

अज्ञात मैट्रिक्स आकार के कारण, मुझे लगता है कि ढेर पर डेटा स्टोर करना है।

मैट्रिक्स घने है, तो मैं की तरह कुछ का उपयोग करने के बारे में सोच: इस संरचना के साथ

short int** M = new short int*[m]; 
short int* M_data = new short int[m*n]; 

for(int i=0; i< m; ++i) 
{ 
    M[i] = M_data + i * n; 
} 

मैं स्मृति का एक सन्निहित अंतरिक्ष आवंटित कर सकते हैं और यह भी M[i][j] के साथ पहुँचा जा करने के लिए सरल है।

अब समस्या संरचना विरल मामले के लिए चयन करने के लिए है, और मैं यह भी विचार करने के लिए कैसे मैं सबसे आसान तरीका में एल्गोरिथ्म के माध्यम से कारों स्थानांतरित कर सकते हैं है: उदाहरण के लिए जब मैं एक कार का मूल्यांकन, मैं करने की जरूरत है अगर अगली स्थिति (नीचे या दाएं) में आसानी से मिल जाए तो एक और कार है या यदि यह खाली है।

शुरू में मैं BlueCar और रेडकार वस्तुओं है कि आम कार वस्तु से विरासत को परिभाषित करने के बारे में सोचा। इस वस्तुओं में मैं मैट्रिक्स निर्देशांक बचा सकता है और फिर उन्हें में डाल दिया:

vector< tuple< row, column, value >> sparseMatrix 

लेकिन खोजने क्या में अगले स्थिति अभी भी बना हुआ है की समस्या:

std::vector<BluCar> sparseBlu; 
std::vector<RedCar> sparseRed; 

अन्यथा मैं की तरह कुछ कर सकते हैं।

शायद यह यह करने के लिए सबसे अच्छा तरीका नहीं है, इसलिए मैं एक कुशल तरीके से विरल मामला कैसे लागू कर सकते हैं? (यह भी विरल के लिए एक अनूठा संरचना का उपयोग)

Answer 1

क्यों बस फ़ाइल पर सीधे एक memory mapping नहीं बना? (मानते हुए कि आपका डेटा 0,1,2 फ़ाइल में संगत बाइट्स (या बिट्स) में संग्रहीत है, और उन बाइट्स की स्थिति भी कारों के निर्देशांक का प्रतिनिधित्व करती है)

इस तरह आपको अतिरिक्त आवंटित करने की आवश्यकता नहीं है स्मृति और सभी डेटा में पढ़ें, और डेटा M[i][j] के साथ आसानी से और कुशलता से पहुंचा जा सकता है।

पंक्तियों पर जा रहे हैं एल 1-कैश अनुकूल होगा।

बहुत स्पैस डेटा के मामले में, आप एक बार डेटा को स्कैन कर सकते हैं और रिक्त क्षेत्रों/ब्लॉक में स्मृति (केवल स्टार्टोज़ और आकार को स्टोर करने की आवश्यकता है) की सूची रख सकते हैं, जिसे आप छोड़ सकते हैं (और जहां आवश्यक हो समायोजित करें)) आगे रनों में।

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

एक और लाभ यह है कि आप ओएस डिस्क कैश सीधे एक्सेस कर रहे है। इस प्रकार कर्नेल स्पेस और उपयोगकर्ता स्पेस के बीच डेटा कॉपी करने और स्थानांतरित करने की आवश्यकता नहीं है।

आगे अंतरिक्ष और स्मृति के उपयोग का अनुकूलन करने के लिए, कारों फ़ाइल में 2 बिट्स में संग्रहित किया जा सकता है।

अद्यतन:

मैं OpenMP के साथ कारों स्थानांतरित करने के लिए होगा और एमपीआई ... विल स्मृति मानचित्रण समवर्ती धागे के साथ भी काम करता है?

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

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

तुम भी विरल क्षेत्रों की सूची को एडजस्ट करने के लिए एक ताला तंत्र की आवश्यकता होगी। मुझे लगता है कि अलग-अलग धागे लॉन्च करना सबसे अच्छा तरीका होगा (पाठ्यक्रम के डेटा के आकार के आधार पर)।

Answer 2

में कुछ ऐसी ही काम में, मैं बस Compressed Row Storage का इस्तेमाल किया।

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

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

There's already an existing C++ implementation available online as well.