🥇Globals डेटा साठवण्यासाठी खजिना-तलवार आहेत. विरळ अॅरे. भाग 3

मागील भागांमध्ये (1, 2) आपण ग्लोबल्स बद्दल झाडं म्हणून बोललो, यामध्ये आपण ग्लोबल्सकडे विरळ अॅरे म्हणून पाहू.

विरळ ॲरे अॅरेचा एक प्रकार आहे ज्यामध्ये बहुतेक मूल्ये समान मूल्य घेतात.

व्यवहारात, विरळ अॅरे अनेकदा इतके मोठे असतात की एकसारख्या घटकांसह मेमरी व्यापण्यात काही अर्थ नाही. त्यामुळे, समान मूल्ये साठवण्यात मेमरी वाया जाणार नाही अशा प्रकारे विरळ अॅरे लागू करण्यात अर्थ आहे.
काही प्रोग्रामिंग भाषांमध्ये, विरळ अॅरे भाषेमध्येच समाविष्ट केले जातात, उदाहरणार्थ जे, MATLAB. इतर प्रोग्रामिंग भाषांमध्ये विशेष लायब्ररी आहेत जी तुम्हाला त्यांची अंमलबजावणी करण्याची परवानगी देतात. C++ साठी - आयगेन आणि इतर.

विरळ अॅरे लागू करण्यासाठी ग्लोबल हे चांगले उमेदवार आहेत कारण:

ते केवळ विशिष्ट नोड्सची मूल्ये संग्रहित करतात आणि अपरिभाषित मूल्ये संचयित करत नाहीत;
नोडच्या व्हॅल्यूमध्ये प्रवेश करण्यासाठी इंटरफेस बहुआयामी अॅरे घटकामध्ये किती प्रोग्रामिंग भाषा प्रवेश लागू करतात यासारखेच आहे.
```
Set ^a(1, 2, 3)=5
Write ^a(1, 2, 3)
```
डेटा संचयित करण्यासाठी ग्लोबल ही बर्‍यापैकी निम्न-स्तरीय रचना आहे, म्हणून त्यात उत्कृष्ट गती वैशिष्ट्ये आहेत (हार्डवेअरवर अवलंबून प्रति सेकंद शेकडो ते लाखो व्यवहार, खाली पहा). 1)

ग्लोबल ही एक पर्सिस्टंट स्ट्रक्चर असल्याने, RAM ची रक्कम पुरेशी नसेल हे आधीच माहीत असताना त्यावर विरळ अॅरे तयार करण्यात अर्थ आहे.

अपरिभाषित सेलमध्ये प्रवेश केल्यास काही डीफॉल्ट मूल्य परत करणे हे स्पार्स अॅरे अंमलबजावणीच्या गुणधर्मांपैकी एक आहे.

हे फंक्शन वापरून लागू केले जाऊ शकते $GET COS मध्ये. हे उदाहरण 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 * चे गुणाकार म्हणून घेतली जाते. कमाल ओळ आकार), म्हणजे, अशा मॅट्रिक्स संचयित करण्याचा आणखी किफायतशीर मार्ग म्हणजे बिट स्ट्रिंग, कारण त्यांची अंमलबजावणी मोठ्या अंतरांना एका विशेष मार्गाने अनुकूल करते.

बिट स्ट्रिंगसह मॅनिपुलेशन फंक्शनद्वारे केले जातात $BIT.

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

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

मर्यादित ऑटोमॅटनचा संक्रमण आलेख हा एक सामान्य आलेख असल्याने, मर्यादित ऑटोमॅटॉनचे संक्रमण सारणी वर चर्चा केलेल्या समान संलग्नता मॅट्रिक्स आहे.

सेल्युलर ऑटोमेटा

सर्वात प्रसिद्ध सेल्युलर ऑटोमॅटन आहे खेळ "जीवन", जे, त्याच्या नियमांमुळे (जेव्हा सेलमध्ये अनेक शेजारी असतात, तेव्हा ते मरतात) एक विरळ अॅरे आहे.

स्टीफन वोल्फ्रामचा असा विश्वास आहे की सेल्युलर ऑटोमेटा आहेत विज्ञानाचे नवीन क्षेत्र. 2002 मध्ये, त्यांनी 1280 पानांचे एक पुस्तक प्रकाशित केले, अ न्यू काइंड ऑफ सायन्स, ज्यामध्ये त्यांनी व्यापकपणे असा युक्तिवाद केला की सेल्युलर ऑटोमॅटामधील प्रगती वेगळी नाही, परंतु टिकणारी आहे आणि विज्ञानाच्या सर्व क्षेत्रांवर त्याचे चांगले परिणाम आहेत.

हे सिद्ध झाले आहे की संगणकावर कार्यान्वित करण्यायोग्य कोणतेही अल्गोरिदम सेल्युलर ऑटोमॅटन वापरून लागू केले जाऊ शकते. सेल्युलर ऑटोमेटाचा वापर डायनॅमिक वातावरण आणि प्रणालींचे मॉडेल करण्यासाठी, अल्गोरिदमिक समस्या सोडवण्यासाठी आणि इतर हेतूंसाठी केला जातो.

जर आमच्याकडे खूप मोठे फील्ड असेल आणि आम्हाला सेल्युलर ऑटोमॅटनच्या सर्व इंटरमीडिएट स्टेटस रेकॉर्ड करण्याची आवश्यकता असेल, तर ग्लोबल वापरण्यात अर्थ आहे.

कार्टोग्राफी

विरळ अॅरे वापरताना माझ्या मनात येणारी पहिली गोष्ट म्हणजे मॅपिंग कार्ये.

नियमानुसार, नकाशांवर बरीच रिकामी जागा आहे. जर नकाशा मोठ्या पिक्सेल म्हणून दर्शविला असेल, तर पृथ्वीच्या पिक्सेलपैकी 71% समुद्राने व्यापलेला असेल. विरळ अॅरे. आणि जर आपण फक्त मानवी हातांची कामे लागू केली तर रिक्त जागा 95% पेक्षा जास्त असेल.

अर्थात, रास्टर अॅरेच्या स्वरूपात कोणीही नकाशे संग्रहित करत नाही; वेक्टर प्रतिनिधित्व वापरले जाते.
पण वेक्टर नकाशे काय आहेत? हा एक प्रकारचा फ्रेम आणि पॉलीलाइन्स आणि पॉइंट्स असलेले पॉलीगॉन्स आहे.
मूलत: बिंदू आणि त्यांच्यामधील कनेक्शनचा डेटाबेस.

सर्वात महत्वाकांक्षी मॅपिंग मोहिमांपैकी एक म्हणजे आपल्या आकाशगंगेचा नकाशा बनवण्याचे गैया टेलिस्कोप मिशन. लाक्षणिकदृष्ट्या सांगायचे तर, आपली आकाशगंगा, संपूर्ण विश्वाप्रमाणेच, एक सतत विरळ अॅरे आहे: रिकामपणाची प्रचंड जागा ज्यामध्ये दुर्मिळ लहान बिंदू आहेत - तारे. रिकामी जागा ९९.९९९९९९…….% आहे. आमच्या आकाशगंगेचा नकाशा संग्रहित करण्यासाठी, एक जागतिक डेटाबेस निवडला गेला - कॅशे.

मला या प्रकल्पातील ग्लोबल्सची नेमकी रचना माहित नाही, मी असे गृहीत धरू शकतो की ते यासारखे काहीतरी आहे:

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 आहेत गॅलेक्टिक समन्वय अक्षांश, रेखांश आणि सूर्याचे अंतर.

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

आपल्या विश्वाचा नकाशा संचयित करण्यासाठी, कॅशेची निवड केवळ त्याच्या लवचिकतेसाठीच नाही, तर जलद शोधांसाठी एकाच वेळी जागतिक निर्देशांक तयार करताना, डेटाचा प्रवाह अतिशय जलद संचयित करण्याच्या क्षमतेसाठी देखील निवडली गेली.

जर आपण पृथ्वीवर परतलो, तर जागतिक स्तरावर कार्टोग्राफिक प्रकल्प तयार केले गेले OpenStreetMap 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 प्रकल्पातील अनेक जागतिक आहेत: जागतिक स्तरावरील निर्देशांकाचे प्रतिनिधित्व:

जागतिक ^मार्ग गुण साठवण्यासाठी वापरले जाते पॉलीलाइन (रस्ते, लहान नद्या इ.) आणि बहुभुज (बंद क्षेत्र: इमारती, जंगले इ.).

ग्लोबल्सवर विरळ अॅरेच्या वापराचे उग्र वर्गीकरण.

आम्ही विशिष्ट वस्तूंचे निर्देशांक आणि त्यांची स्थिती संग्रहित करतो (मॅपिंग, सेल्युलर ऑटोमेटा)
आम्ही विरळ मॅट्रिक्स साठवतो.

केस 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

कॉलम व्हेरिएबलबद्दल मनोरंजक गोष्ट म्हणजे आमच्याकडे एक विरळ अॅरे देखील आहे, ज्यामध्ये देखील प्रवेश करणे आवश्यक आहे $GET, कारण त्यात डीफॉल्ट मूल्ये साठवली जात नाहीत.

फंक्शन वापरून छोट्या प्रोग्रामद्वारे जागेचे तुकडे निवडणे देखील शक्य आहे $ऑर्डर. हे विशेषत: अशा जागांसाठी सोयीस्कर आहे ज्यांचे निर्देशांक परिमाणित नाहीत (कार्टोग्राफी).

निष्कर्ष

सध्याचा काळ नवीन महत्वाकांक्षी कार्ये उभी करतो. आलेख कोट्यवधी शिरोबिंदूंनी बनलेले असू शकतात, अब्जावधी बिंदूंनी बनलेले नकाशे आणि काहींना त्यांचे स्वतःचे विश्व सेल्युलर ऑटोमेटावर चालवायचे असेल (1, 2).

जेव्हा विरळ अ‍ॅरेमधील डेटाची मात्रा यापुढे रॅममध्ये बसू शकत नाही, परंतु आपल्याला त्यांच्यासह कार्य करण्याची आवश्यकता असेल, तेव्हा ग्लोबल आणि सीओएसवर समान प्रकल्प लागू करण्याची शक्यता विचारात घेणे योग्य आहे.

आपण लक्ष दिल्याबद्दल धन्यवाद! आम्ही टिप्पण्यांमध्ये तुमच्या प्रश्नांची आणि शुभेच्छांची वाट पाहत आहोत.

जबाबदारी नाकारणे: हा लेख आणि त्यावरच्या माझ्या टिप्पण्या माझे मत आहेत आणि त्यांचा इंटरसिस्टम कॉर्पोरेशनच्या अधिकृत पदाशी कोणताही संबंध नाही.

स्त्रोत: www.habr.com

ग्लोबल हे डेटा साठवण्यासाठी खजिना-तलवार आहेत. विरळ अॅरे. भाग 3