ગ્લોબલ એ ડેટા સ્ટોર કરવા માટેનો ખજાનો-તલવાર છે. છૂટાછવાયા એરે. ભાગ 3

અગાઉના ભાગોમાં (1, 2) આપણે ગ્લોબલ વિશે વૃક્ષો તરીકે વાત કરી, આમાં આપણે વૈશ્વિકને સ્પાર્સ એરે તરીકે જોઈશું.

સ્પાર્સ એરે એરેનો એક પ્રકાર છે જેમાં મોટાભાગના મૂલ્યો સમાન મૂલ્ય લે છે.

વ્યવહારમાં, છૂટાછવાયા એરે ઘણીવાર એટલા વિશાળ હોય છે કે સમાન તત્વો સાથે મેમરીને કબજે કરવાનો કોઈ અર્થ નથી. તેથી, સ્પાર્સ એરેને એવી રીતે અમલમાં મૂકવાનો અર્થ થાય છે કે સમાન મૂલ્યોને સંગ્રહિત કરવામાં મેમરીનો વ્યય ન થાય.
કેટલીક પ્રોગ્રામિંગ ભાષાઓમાં, છૂટાછવાયા એરેનો ભાષામાં જ સમાવેશ થાય છે, ઉદાહરણ તરીકે જે, મેટલેબ Language. અન્ય પ્રોગ્રામિંગ ભાષાઓમાં વિશેષ પુસ્તકાલયો છે જે તમને તેનો અમલ કરવાની મંજૂરી આપે છે. C++ માટે - આઈજેન અને અન્ય

છૂટાછવાયા એરેનો અમલ કરવા માટે વૈશ્વિક લોકો સારા ઉમેદવારો છે કારણ કે:

1. તેઓ માત્ર અમુક ગાંઠોના મૂલ્યોને સંગ્રહિત કરે છે અને અવ્યાખ્યાયિત મૂલ્યોને સંગ્રહિત કરતા નથી;
2. નોડના મૂલ્યને ઍક્સેસ કરવા માટેનું ઇન્ટરફેસ બહુપરીમાણીય એરે તત્વની ઍક્સેસને કેટલી પ્રોગ્રામિંગ ભાષાઓ અમલમાં મૂકે છે તેના જેવું જ છે.

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

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% થી વધુ હશે.

અલબત્ત, રાસ્ટર એરેના રૂપમાં કોઈ નકશા સંગ્રહિત કરતું નથી; વેક્ટર રજૂઆતનો ઉપયોગ થાય છે.
પરંતુ વેક્ટર નકશા શું છે? આ એક પ્રકારનો ફ્રેમ અને પોલીલાઈન અને પોઈન્ટ્સનો બનેલો બહુકોણ છે.
આવશ્યકપણે પોઈન્ટ્સ અને તેમની વચ્ચેના જોડાણોનો ડેટાબેઝ.

સૌથી મહત્વાકાંક્ષી મેપિંગ મિશનમાંનું એક છે ગૈયા ટેલિસ્કોપ મિશન જે આપણી ગેલેક્સીને મેપ કરે છે. અલંકારિક રીતે કહીએ તો, આપણી આકાશગંગા, સમગ્ર બ્રહ્માંડની જેમ, એક સતત છૂટાછવાયા એરે છે: ખાલીપણાની વિશાળ જગ્યાઓ જેમાં દુર્લભ નાના બિંદુઓ છે - તારાઓ. ખાલી જગ્યા 99,999999…….% છે. અમારી ગેલેક્સીના નકશાને સંગ્રહિત કરવા માટે, વૈશ્વિક ડેટાબેઝ પસંદ કરવામાં આવ્યો હતો - Caché.

મને આ પ્રોજેક્ટમાં ગ્લોબલ્સની ચોક્કસ રચના ખબર નથી, હું ધારી શકું છું કે તે કંઈક સમાન છે:

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 છે ગેલેક્ટીક કોઓર્ડિનેટ્સ અક્ષાંશ, રેખાંશ અને સૂર્યનું અંતર.

ગ્લોબલનું લવચીક માળખું તમને તારાઓ અને ગ્રહોની કોઈપણ આવશ્યક લાક્ષણિકતાઓને બચાવવા માટે પરવાનગી આપે છે, કારણ કે ગ્લોબલ પરના પાયા યોજનાથી ઓછા છે.

આપણા બ્રહ્માંડના નકશાને સંગ્રહિત કરવા માટે, Caché ને માત્ર તેની લવચીકતા માટે જ નહીં, પણ ઝડપી શોધ માટે ઇન્ડેક્સ વૈશ્વિક બનાવવાની સાથે સાથે ખૂબ જ ઝડપથી ડેટાના પ્રવાહને સ્ટોર કરવાની ક્ષમતા માટે પણ પસંદ કરવામાં આવ્યું હતું.

જો આપણે પૃથ્વી પર પાછા ફરો, તો વૈશ્વિક પર કાર્ટોગ્રાફિક પ્રોજેક્ટ્સ બનાવવામાં આવ્યા હતા ઓપનસ્ટ્રીટમેપ 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

કૉલમ વેરીએબલ વિશે રસપ્રદ બાબત એ છે કે અમારી પાસે સ્પાર્સ એરે પણ છે, જેને એક્સેસ કરવું આવશ્યક છે $GET, કારણ કે તેમાં ડિફોલ્ટ મૂલ્યો સંગ્રહિત નથી.

ફંક્શનનો ઉપયોગ કરીને નાના પ્રોગ્રામ દ્વારા જગ્યાના ટુકડાઓ પણ પસંદ કરી શકાય છે $ઓર્ડર. આ ખાસ કરીને એવી જગ્યાઓ પર અનુકૂળ છે કે જેના સૂચકાંકો પરિમાણિત નથી (કાર્ટોગ્રાફી).

નિષ્કર્ષ

વર્તમાન સમય નવા મહત્વાકાંક્ષી કાર્યો ઉભો કરે છે. આલેખ અબજો શિરોબિંદુઓથી બનેલા હોઈ શકે છે, અબજો બિંદુઓથી બનેલા નકશા, અને કેટલાક તેમના પોતાના બ્રહ્માંડને સેલ્યુલર ઓટોમેટા (1, 2).

જ્યારે સ્પાર્સ એરેમાંથી ડેટાનું વોલ્યુમ હવે RAM માં ફિટ થઈ શકતું નથી, પરંતુ તમારે તેમની સાથે કામ કરવાની જરૂર છે, તો તે વૈશ્વિક અને COS પર સમાન પ્રોજેક્ટ્સ અમલમાં મૂકવાની શક્યતાને ધ્યાનમાં લેવા યોગ્ય છે.

તમારા ધ્યાન બદલ આભાર! અમે ટિપ્પણીઓમાં તમારા પ્રશ્નો અને શુભેચ્છાઓની રાહ જોઈ રહ્યા છીએ.

જવાબદારીનો ઇનકાર: આ લેખ અને તેના પર મારી ટિપ્પણીઓ મારો અભિપ્રાય છે અને તેનો ઇન્ટરસિસ્ટમ્સ કોર્પોરેશનની સત્તાવાર સ્થિતિ સાથે કોઈ સંબંધ નથી.

સોર્સ: www.habr.com