Në pjesët e mëparshme (, ) folëm për globalët si pemë, në këtë pjesë do të shqyrtojmë globalët si masa të holluar.
është një lloj mase, ku shumica e vlerave merr të njëjtën vlerë.
Në praktikë, shpesh hasen masa kaq të mëdha të holluara, saqë nuk ka asnjë kuptim të zënë memorie me elemente të njëjta. Prandaj, ka kuptim që masat e holluara të realizohen në mënyrë që memorja të mos harxhohet për ruajtjen e vlerave të njëjta.
NĂ« disa gjuhĂ« programimi, masat e holluara janĂ« pjesĂ« e gjuhĂ«s vetĂ«, , . NĂ« gjuhĂ« tĂ« tjera programimi ka biblioteka speciale qĂ« lejojnĂ« realizimin e tyre. PĂ«r C++ â etj.
Globalët janë kandidatë të mirë për realizimin e masave të holluara, sepse:
- Ruajnë vlerat vetëm të nyjeve të caktuara dhe nuk ruajnë vlerat e paregjistruara;
- Ndërfaqja e qasjes në vlerën e nyjes është jashtëzakonisht e ngjashme me mënyrën se si është realizuar qasja në elementin e një mase shumëdimensionale në shumë gjuhë programimi.
Set ^a(1, 2, 3)=5 Write ^a(1, 2, 3) - Globali është një strukturë mjaft e ulët për ruajtjen e të dhënave, prandaj ka karakteristika të shkëlqyera shpejtësie (nga qindra mijëra deri në dhjetëra miliona transaksione në sekondë, në varësi të harduerit, shih. )
Duke qenë se globali është një strukturë persistente, ka kuptim të bësh masa të holluara mbi to kur dihet paraprakisht se volumi i memories operuese do të jetë i pamjaftueshëm.
Një nga veçoritë e realizimeve të masave të holluara është kthimi i një vlerë për default nëse adresa e caktuar është e paregjistruar.
Kjo mund të realizohet duke përdorur funksionin në COS. Në këtë shembull, shqyrtohet një masë tridimensionale.
SET a = $GET(^a(x,y,z), defValue)Cilat janë detyrat për të cilat kërkohen masat e holluara dhe si mund t'i ndihmojnë globalët?
Matrica e fqinjësisë (lidshmërisë)
përdoren për të paraqitur grafet:
E qartë është se sa më i madh të jetë grafi, aq më shumë zero do të ketë në matricë. Nëse, për shembull, marrim një graf të një rrjeti social dhe e paraqesim atë si një matricë të tillë, do të përbëhet pothuajse krejtësisht nga zero, dmth do të jetë një masë e holluar.
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
....
Në këtë shembull, ne ruajmë në globalin ^m matrica e lidhjes, si dhe numri i skajeve për secilën nyjë (kush është miq me kë, dhe numri i miqve).
NĂ«se numri i elementeve nĂ« grafik nuk kalon 29 milionĂ« (ky numĂ«r merret si produkti 8 * ), atĂ«herĂ« ka njĂ« mĂ«nyrĂ« edhe mĂ« ekonomike pĂ«r tĂ« ruajtur kĂ«to matrica â vargje bitore, pasi nĂ« realizimin e tyre optimizohen nĂ« mĂ«nyrĂ« speciale boshllĂ«qet e mĂ«dha.
Manipulimet me vargjet bitore kryhen nga funksioni .
; vendosja e bitit
SET $BIT(rowID, positionID) = 1
; marrja e bitit
Write $BIT(rowID, positionID)
Tabela e kalimeve të automatit përfundimtar
Pasi grafi i kalimeve të automatit përfundimtar është një grafik i zakonshëm, tabela e kalimeve të automatit përfundimtar është po ajo matrica e afërsisë, për të cilën u fol më sipër.
Automatet qelizore
Automati qelizor mĂ« i njohur Ă«shtĂ« , e cila pĂ«r shkak tĂ« rregullave tĂ« saj (kur njĂ« qelizĂ« ka shumĂ« fqinjĂ« â ajo vdes) paraqet njĂ« masĂ« tĂ« shkurtruar.
Stephen Wolfram, mendon se automatet qelizore janë një . Në vitin 2002 publikon librin 1280-faqesh "Një Lloj i Ri Shkence", ku argumenton gjerësisht se arritjet në fushën e automatheve qelizore nuk janë të izoluara, por të qëndrueshme dhe përbëjnë një rëndësi të madhe për të gjitha fushat e shkencës.
ĂshtĂ« provuar se çdo algoritem i realizueshĂ«m nĂ« kompjuter mund tĂ« realizohet pĂ«rmes automatit qelizor. Automatet qelizore pĂ«rdoren pĂ«r modelimin e ambienteve dhe sistemeve dinamike, pĂ«r zgjidhjen e problemeve algoritmike dhe pĂ«r qĂ«llime tĂ« tjera.
Nëse kemi një fushë të madhe dhe na nevojitet të regjistrojmë të gjitha gjendjet ndërmjetëse të automatit qelizor, është shumë e arsyeshme të përdorim globale.
Kartografia
E para qĂ« mĂ« vjen nĂ« mendje, kur flitet pĂ«r pĂ«rdorimin e masave tĂ« shkurtra â janĂ« problemet kartografike.
Si zakonisht, mbi hartat ka shumë hapësirë të zbrazët. Nëse harta paraqitet si pikse të mëdha, atëherë 71% e pikseve të Tokës do të ishte e zënë nga oqeanet. Një masë e shkurtruar. Dhe nëse shënohen vetëm ndërtimet njerëzore, hapësira e zbrazët do të kalonte mbi 95%.
Sigurisht, askush nuk i ruan hartat si masa rastere, por përdoret përfaqësimi vektorik.
Por çfarë përfaqësojnë hartat vektorike? Ato janë një kornizë e cila përbëhet nga pika, polilinjat dhe poliagonet.
Në thelb, është një bazë të dhënash të pikave dhe lidhjeve midis tyre.
NjĂ« nga detyrat mĂ« ambicioze tĂ« hartografisĂ« Ă«shtĂ« misioni pĂ«r tĂ« kartuar galaktikĂ«n tonĂ« me teleskopin Gaia. Figurativisht, galaktika jonĂ«, ashtu si e gjithĂ« universi, Ă«shtĂ« njĂ« grumbull me densitet tĂ« ulĂ«t: hapĂ«sira tĂ« mĂ«dha bosh nĂ« tĂ« cilat ka pika tĂ« vogla tĂ« rralla - yje. Hapsira bosh zĂ« 99,999999âŠâŠ.%. PĂ«r tĂ« ruajtur hartĂ«n e galaktikĂ«s tonĂ«, u zgjodh njĂ« bazĂ« tĂ« dhĂ«nash nĂ« globals - CachĂ©.
Nuk e di strukturën e saktë të globals në këtë projekt, mund të supozoj se është diçka e ngjashme me:
Set ^galaxy(b, l, d) = 1; Numri i yllit sipas katalogut, nëse ka
Set ^galaxy(b, l, d, "name") = "Dielli"
Set ^galaxy(b, l, d, "type") = "normal" ; opsionet blackhole, quazar, red_dwarf etj.
Set ^galaxy(b, l, d, "weight") = 14E50
Set ^galaxy(b, l, d, "planetes") = 7
Set ^galaxy(b, l, d, "planetes", 1) = "Merkuri"
Set ^galaxy(b, l, d, "planetes", 1, weight) = 1E20
...
Ku b, l, d janë dhe distanca nga Dielli.
Struktura fleksibile e globals lejon ruajtjen e çdo karakteristike të nevojshme për yjet dhe planetet, pasi bazat globale janë pa skemë (scheme-less).
Për ruajtjen e hartës së universin ton, Caché u zgjodh jo vetëm për fleksibilitetin, por edhe për aftësinë për të ruajtur me shpejtësi flukse të dhënash, duke krijuar gjithashtu globals indekse për kërkime të shpejta.
Nëse kthehemi te Toka, projekti i hartografisë u krijua në globals dhe fork OpenStreetMap - .
Së fundmi në u realizuan indekse gjeospaçiale . Po presim detaje nga autorët e artikullit për implementimin.
Implementimi i indekseve hapësinore në global në OpenStreetMap XAPI
Imazhet janë marrë nga .
Të gjithë globi i Tokës ndahet në katrorë, pastaj në katrorë më të vegjël, dhe kështu me radhë. Në thelb, ne krijojmë një strukturë hierarkike për ruajtjen e të cilave janë krijuar globals.
Në çdo moment mund të kërkojmë pothuajse me shpejtësi të menjëhershme katrorin e nevojshëm ose ta pastrrojmë atë, ndërsa të gjitha katrorët e vegjël gjithashtu do të kthehen ose pastrohen.
Një skemë të tillë në globals mund të realizohet në disa mënyra.
Opsioni 1:
Set ^m(a, b, a, c, d, a, b,c, d, a, b, a, c, d, a, b,c, d, a, 1) = idPikaE parë
Set ^m(a, b, a, c, d, a, b,c, d, a, b, a, c, d, a, b,c, d, a, 2) = idPikaE dytë
...Opsioni 2:
Set ^m('abacdabcdabacdabcda', 1) = idPikaE parë
Set ^m('abacdabcdabacdabcda', 2) = idPikaE dytë
...Në të dyja rastet, nuk është e vështirë të kërkosh piket që ndodhen në katrorin e çdo niveli në COS/M. Do të jetë pak më e lehtë të pastrosh copat katrore të hapësirës çdo niveli në variantin e parë, por kjo është e rrallë e nevojshme.
Shembulli i një katrori të nivelit të ulët:
Ja disa globale nga projekti XAPI: paraqitja e indeksit në globale:
Global ^way përdoret për ruajtjen e pikave (rrugëve, lumenjve të vegjël etj.) dhe poligoneve (zona të mbyllura: ndërtesa, pyje etj.).
Klasifikimi i përafërt i përdorimit të masave të hollë në globale.
- Ne ruajmë koordinatat e disa objekteve dhe gjendjet e tyre (hartimi, automatikët celularë).
- Ne ruajmë matrica të hollë.
Për rastin 2) kur kërkohet një koordinatë e caktuar, ku elementit nuk i është caktuar një vlerë, ne duhet të marrim vlerën standarde të elementit të masës së hollë.
Bonuset që marrim kur ruajmë matrica shumëdimensionale në globale.
Fshirje dhe/ose zgjedhje e shpejtë e copave të hapësirës, shumëfish i rreshtave, planeve, kubëve etj. Për rastet kur përdoren indekset e numrave të plotë, mund të jetë e dobishme mundësia e fshirjes dhe/ose zgjedhjes së shpejtë të copave të hapësirës, shumëfish i rreshtave, planeve, kubëve etj.
Me komandĂ«n ne mund tĂ« fshijmĂ« si njĂ« element tĂ« veçantĂ«, ashtu edhe njĂ« rresht, madje edhe njĂ« tĂ«rĂ« plan. FalĂ« pronave tĂ« globaleve, kjo ndodh shumĂ« shpejt â mijĂ«ra herĂ« mĂ« shpejt se fshirja element pas elementi.
Në figurë është paraqitur një masë tri-dimensionale në global ^a dhe lloje të ndryshme fshirjesh.
Për të zgjedhur copat e hapësirës sipas indekseve të njohura, mund të përdorim komandën .
Zgjedhja e kolonës së matricës në variablin Column:
; Le të caktojmë një masë të hollë tri-dimensionale 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)
; Do të nxjerrim variablin Column
Zwrite Column
PĂ«rfundimi:
Column(0)=1
Column(2)=1
Ajo që është interesante është se në variablin Column kemi gjithashtu një masë të hollë, ndaj duhet të qasemi gjithashtu përmes , pasi vlerat standarde nuk ruhen aty.
Zgjedhja e copave të hapësirës gjithashtu mund të bëhet përmes një programi të vogël duke përdorur funksionin . Kjo është veçanërisht e dobishme në hapësirat, ku indekset nuk janë të kuantizuara (hartografia).
PĂ«rfundim
Koha aktuale vendos sfida të reja ambicioze. Grafet mund të përbëhen nga miliarda nodë, hartat nga miliarda pika, dhe ndonjëherë dikush mund të dëshirojë të fillojë universin e tij me automata qelizorë (, ).
Kur volumi i të dhënave të matrikseve të rralla nuk mund të përballohet më nga memoria e përkohshme, dhe ne duhet të punojmë me to, është e arsyeshme të shqyrtojmë mundësinë e realizimit të projekteve të tilla në globalë dhe COS.
Faleminderit për vëmendjen! Presim pyetjet dhe dëshirat tuaja në komentet.
Kufizimi: Ky artikull dhe komentet e mia për të janë mendimi im dhe nuk kanë të bëjnë me pozitat zyrtare të kompanisë InterSystems.
Burimi: habr.com
