ग्लोबल्स डेटा भंडारण के लिए खजाना-तलवार हैं। विरल सरणियाँ. भाग 3

पिछले भागों में (1, 2) हमने पेड़ों के रूप में ग्लोबल्स के बारे में बात की, इसमें हम ग्लोबल्स को विरल सरणी के रूप में देखेंगे।

विरल सरणी एक प्रकार की सारणी है जिसमें अधिकांश मान समान मान लेते हैं।

व्यवहार में, विरल सरणियाँ अक्सर इतनी बड़ी होती हैं कि समान तत्वों के साथ स्मृति पर कब्जा करने का कोई मतलब नहीं है। इसलिए, विरल सरणियों को इस तरह से लागू करना समझ में आता है कि समान मानों को संग्रहीत करने पर मेमोरी बर्बाद न हो।
कुछ प्रोग्रामिंग भाषाओं में, विरल सरणियाँ भाषा में ही शामिल होती हैं, उदाहरण के लिए जे, MATLAB. अन्य प्रोग्रामिंग भाषाओं में विशेष पुस्तकालय हैं जो आपको उन्हें लागू करने की अनुमति देते हैं। सी++ के लिए - eigen आदि

विरल सरणियों को लागू करने के लिए ग्लोबल अच्छे उम्मीदवार हैं क्योंकि:

1. वे केवल कुछ नोड्स के मूल्यों को संग्रहीत करते हैं और अपरिभाषित नोड्स के मूल्यों को संग्रहीत नहीं करते हैं;
2. किसी नोड के मान तक पहुंचने के लिए इंटरफ़ेस बेहद समान है कि कितनी प्रोग्रामिंग भाषाएं बहुआयामी सरणी तत्व तक पहुंच लागू करती हैं।

   Set ^a(1, 2, 3)=5
   Write ^a(1, 2, 3)

3. ग्लोबल डेटा भंडारण के लिए काफी निम्न-स्तरीय संरचना है, इसलिए इसमें उत्कृष्ट गति विशेषताएँ हैं (हार्डवेयर के आधार पर प्रति सेकंड सैकड़ों हजारों से लेकर लाखों लेनदेन तक, नीचे देखें)। 1)

चूँकि वैश्विक एक सतत संरचना है, इसलिए उन पर विरल सरणियाँ बनाना समझ में आता है जब यह पहले से ज्ञात हो कि RAM की मात्रा पर्याप्त नहीं होगी।

यदि किसी अपरिभाषित सेल तक पहुंच बनाई जाती है तो विरल सरणी कार्यान्वयन के गुणों में से एक कुछ डिफ़ॉल्ट मान वापस करना है।

इसे फ़ंक्शन का उपयोग करके कार्यान्वित किया जा सकता है $प्राप्त करें सीओएस में. यह उदाहरण एक 3-आयामी सरणी पर विचार करता है।

SET a = $GET(^a(x,y,z), defValue)

किन कार्यों के लिए विरल सरणियों की आवश्यकता होती है और ग्लोबल्स कैसे मदद कर सकते हैं?

आसन्नता (कनेक्टिविटी) मैट्रिक्स

ऐसे मैट्रिक्स ग्राफ़ का प्रतिनिधित्व करने के लिए उपयोग किया जाता है:

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

Set ^m(id1, id2) = 1 
Set ^m(id1, id3) = 1 
Set ^m(id1, id4) = 1 
Set ^m(id1) = 3 
Set ^m(id2, id4) = 1 
Set ^m(id2, id5) = 1 
Set ^m(id2) = 2
....

इस उदाहरण में, हम विश्व स्तर पर बचत करते हैं ^m कनेक्टिविटी मैट्रिक्स, साथ ही प्रत्येक नोड पर किनारों की संख्या (कौन किसके साथ मित्र है और मित्रों की संख्या)।

यदि ग्राफ़ में तत्वों की संख्या 29 मिलियन से अधिक नहीं है (यह संख्या 8* के गुणनफल के रूप में ली जाती है) अधिकतम पंक्ति आकार), यानी, ऐसे मैट्रिक्स को स्टोर करने का एक और भी अधिक किफायती तरीका बिट स्ट्रिंग्स है, क्योंकि उनका कार्यान्वयन एक विशेष तरीके से बड़े अंतराल को अनुकूलित करता है।

बिट स्ट्रिंग्स के साथ हेरफेर फ़ंक्शन द्वारा किया जाता है $बिट.

; установка бита
SET $BIT(rowID, positionID) = 1
; получение бита
Write $BIT(rowID, positionID)

राज्य मशीन संक्रमण तालिका

चूँकि एक परिमित ऑटोमेटन का संक्रमण ग्राफ एक साधारण ग्राफ है, तो परिमित ऑटोमेटन की संक्रमण तालिका वही आसन्न मैट्रिक्स है जिसकी ऊपर चर्चा की गई है।

सेल्यूलर आटोमेटा

सबसे प्रसिद्ध सेलुलर ऑटोमेटन है खेल "जीवन", जो, अपने नियमों के कारण (जब किसी कोशिका के कई पड़ोसी होते हैं, तो वह मर जाती है) एक विरल सरणी है।

स्टीफन वोल्फ्राम का मानना ​​है कि सेलुलर ऑटोमेटा हैं विज्ञान का नया क्षेत्र. 2002 में, उन्होंने 1280 पन्नों की एक पुस्तक, ए न्यू काइंड ऑफ साइंस प्रकाशित की, जिसमें उन्होंने मोटे तौर पर तर्क दिया कि सेलुलर ऑटोमेटा में प्रगति अलग-थलग नहीं है, बल्कि स्थायी है और विज्ञान के सभी क्षेत्रों के लिए इसका बहुत बड़ा प्रभाव है।

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

यदि हमारे पास एक विशाल क्षेत्र है और हमें सेलुलर ऑटोमेटन के सभी मध्यवर्ती राज्यों को रिकॉर्ड करने की आवश्यकता है, तो ग्लोबल्स का उपयोग करना समझ में आता है।

नक्शानवीसी

जब विरल सरणियों का उपयोग करने की बात आती है तो पहली बात जो मेरे दिमाग में आती है वह है मैपिंग कार्य।

एक नियम के रूप में, मानचित्रों पर बहुत सारी खाली जगह होती है। यदि मानचित्र को बड़े पिक्सेल के रूप में दर्शाया जाए, तो पृथ्वी के 71% पिक्सेल पर महासागर का कब्जा होगा। विरल सरणी. और यदि आप केवल मानव हाथों के कार्यों को लागू करते हैं, तो रिक्त स्थान 95% से अधिक होगा।

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

सबसे महत्वाकांक्षी मानचित्रण मिशनों में से एक हमारी आकाशगंगा का मानचित्रण करने वाला गैया टेलीस्कोप मिशन है। लाक्षणिक रूप से कहें तो, हमारी आकाशगंगा, संपूर्ण ब्रह्मांड की तरह, एक सतत विरल सरणी है: शून्यता के विशाल स्थान जिनमें दुर्लभ छोटे बिंदु - तारे हैं। रिक्त स्थान 99,999999…….% है। हमारी आकाशगंगा के मानचित्र को संग्रहीत करने के लिए, एक वैश्विक डेटाबेस चुना गया - कैचे।

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

Set ^galaxy(b, l, d) = 1; Номер звезды по каталогу, если есть
Set ^galaxy(b, l, d, "name") = "Sun"
Set ^galaxy(b, l, d, "type") = "normal" ; варианты blackhole, quazar, red_dwarf и т.д.
Set ^galaxy(b, l, d, "weight") = 14E50
Set ^galaxy(b, l, d, "planetes") = 7
Set ^galaxy(b, l, d, "planetes", 1) = "Mercury"
Set ^galaxy(b, l, d, "planetes", 1, weight) = 1E20
...

जहाँ b, l, d हैं गैलेक्टिक अक्षांश, देशांतर का समन्वय करता है और सूर्य से दूरी.

ग्लोबल्स की लचीली संरचना आपको सितारों और ग्रहों की किसी भी आवश्यक विशेषता को सहेजने की अनुमति देती है, क्योंकि ग्लोबल्स पर आधार योजना-रहित होते हैं।

हमारे ब्रह्मांड के मानचित्र को संग्रहीत करने के लिए, कैचे को न केवल इसके लचीलेपन के लिए चुना गया था, बल्कि डेटा की एक धारा को बहुत तेज़ी से संग्रहीत करने की क्षमता के लिए भी चुना गया था, साथ ही साथ तेज़ खोजों के लिए इंडेक्स ग्लोबल्स भी बनाया गया था।

यदि हम पृथ्वी पर लौटते हैं, तो ग्लोबल्स पर कार्टोग्राफिक प्रोजेक्ट बनाए गए थे ओपनस्ट्रीटमैप XAPI और OpenStreetMap का एक कांटा - FOSM.

हाल ही में हैकथॉन कैचे भू-स्थानिक सूचकांक लागू किए गए भू-स्थानिक. हम कार्यान्वयन विवरण के साथ लेखकों के एक लेख की प्रतीक्षा कर रहे हैं।

OpenStreetMap XAPI में वैश्विक स्तर पर स्थानिक अनुक्रमणिका का कार्यान्वयन

से ली गई तस्वीरें यह प्रस्तुति.

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

किसी भी क्षण, हम लगभग तुरंत वांछित वर्ग का अनुरोध कर सकते हैं या उसे साफ़ कर सकते हैं, और सभी उप-वर्ग भी वापस कर दिए जाएंगे या साफ़ कर दिए जाएंगे।

वैश्विक स्तर पर एक समान योजना को कई तरीकों से लागू किया जा सकता है।

विकल्प 1:

Set ^m(a, b, a, c, d, a, b,c, d, a, b, a, c, d, a, b,c, d, a, 1) = idПервойТочки
Set ^m(a, b, a, c, d, a, b,c, d, a, b, a, c, d, a, b,c, d, a, 2) = idВторойТочки
...

विकल्प 2:

Set ^m('abacdabcdabacdabcda', 1) = idПервойТочки
Set ^m('abacdabcdabacdabcda', 2) = idВторойТочки
...

दोनों ही मामलों में, किसी भी स्तर के वर्ग में स्थित बिंदुओं का अनुरोध करने के लिए COS/M का उपयोग करना मुश्किल नहीं है। पहले विकल्प में किसी भी स्तर पर जगह के चौकोर टुकड़ों को साफ करना कुछ हद तक आसान होगा, लेकिन यह शायद ही कभी आवश्यक हो।

निचले स्तर के वर्गों में से एक का उदाहरण:

और यहाँ XAPI प्रोजेक्ट से कई ग्लोबल्स हैं: ग्लोबल्स पर एक सूचकांक का प्रतिनिधित्व:

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

ग्लोबल्स पर विरल सरणियों के उपयोग का मोटा वर्गीकरण।

1. हम कुछ वस्तुओं और उनकी स्थितियों के निर्देशांक संग्रहीत करते हैं (मैपिंग, सेलुलर ऑटोमेटा)
2. हम विरल मैट्रिक्स संग्रहीत करते हैं।

मामले 2 के लिए) एक विशिष्ट समन्वय का अनुरोध करते समय जहां तत्व को कोई मान निर्दिष्ट नहीं किया गया है, हमें डिफ़ॉल्ट विरल सरणी तत्व का मान प्राप्त करना होगा।

बोनस जो हमें ग्लोबल्स में बहुआयामी मैट्रिक्स संग्रहीत करते समय प्राप्त होता है

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

टीम हत्या हम या तो एक तत्व या एक पंक्ति, या यहां तक ​​कि एक संपूर्ण विमान को हटा सकते हैं। ग्लोबल्स के गुणों के लिए धन्यवाद, यह बहुत तेजी से होता है - तत्व-दर-तत्व हटाने की तुलना में हजारों गुना तेजी से।

यह चित्र वैश्विक में त्रि-आयामी सरणी दिखाता है ^a और विभिन्न प्रकार के विलोपन.

ज्ञात अनुक्रमणिका का उपयोग करके स्थान के टुकड़ों का चयन करने के लिए, आप कमांड का उपयोग कर सकते हैं मर्ज.

कॉलम वेरिएबल में मैट्रिक्स कॉलम का चयन करना:

; Зададим трёхмерный разреженный массив 3x3x3
Set ^a(0,0,0)=1,^a(2,2,0)=1,^a(2,0,1)=1,^a(0,2,1)=1,^a(2,2,2)=1,^a(2,1,2)=1
Merge Column = ^a(2,2)
; Выведем переменную Column
Zwrite Column

निष्कर्ष:

Column(0)=1
Column(2)=1

कॉलम वैरिएबल के बारे में दिलचस्प बात यह है कि हमारे पास एक विरल सरणी भी है, जिसे इसके माध्यम से भी एक्सेस किया जाना चाहिए $प्राप्त करें, चूँकि इसमें डिफ़ॉल्ट मान संग्रहीत नहीं होते हैं।

फ़ंक्शन का उपयोग करके अंतरिक्ष के टुकड़ों का चयन एक छोटे प्रोग्राम के माध्यम से भी किया जा सकता है $आदेश. यह उन स्थानों पर विशेष रूप से सुविधाजनक है जिनके सूचकांक परिमाणित (मानचित्रण) नहीं हैं।

निष्कर्ष

वर्तमान समय नये महत्वाकांक्षी कार्य प्रस्तुत करता है। ग्राफ़ अरबों शीर्षों से बने हो सकते हैं, मानचित्र अरबों बिंदुओं से बने हो सकते हैं, और कुछ लोग अपने स्वयं के ब्रह्मांड को सेलुलर ऑटोमेटा पर चलाना भी चाह सकते हैं (1, 2).

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

आपके ध्यान देने के लिए धन्यवाद! हम टिप्पणियों में आपके प्रश्नों और शुभकामनाओं का इंतजार कर रहे हैं।

Disclaimer: यह लेख और इस पर मेरी टिप्पणियाँ मेरी राय हैं और इसका इंटरसिस्टम्स कॉर्पोरेशन की आधिकारिक स्थिति से कोई संबंध नहीं है।

स्रोत: www.habr.com