Në pjesët e mëparshme (, ) folëm për globalët si pemë, në këtë do t'i shikojmë globalët si vargje të rralla.
është një lloj grupi në të cilin shumica e vlerave marrin të njëjtën vlerë.
Në praktikë, grupet e rralla janë shpesh aq të mëdha sa që nuk ka asnjë pikë për të zënë kujtesën me elementë identikë. Prandaj, ka kuptim të zbatohen vargje të rralla në atë mënyrë që kujtesa të mos harxhohet për ruajtjen e vlerave identike.
Në disa gjuhë programimi, vargje të rralla përfshihen në vetë gjuhën, , . Gjuhët e tjera të programimit kanë biblioteka të veçanta që ju lejojnë t'i zbatoni ato. Për C++ - etj
Globalët janë kandidatë të mirë për zbatimin e vargjeve të rralla sepse:
- Ata ruajnë vlerat e vetëm nyjeve të caktuara dhe nuk ruajnë vlerat e atyre të papërcaktuara;
- Ndërfaqja për të hyrë në vlerën e një nyje është jashtëzakonisht e ngjashme me atë se sa gjuhë programimi zbatojnë aksesin në një element grupi shumëdimensional.
Set ^a(1, 2, 3)=5 Write ^a(1, 2, 3) - Global është një strukturë mjaft e nivelit të ulët për ruajtjen e të dhënave, prandaj ka karakteristika të jashtëzakonshme të shpejtësisë (nga qindra mijëra në dhjetëra miliona transaksione në sekondë, në varësi të harduerit, shih më poshtë). )
Meqenëse globali është një strukturë e qëndrueshme, ka kuptim të krijohen vargje të rralla mbi to kur dihet paraprakisht se sasia e RAM-it nuk do të jetë e mjaftueshme.
Një nga vetitë e zbatimeve të vargjeve të rralla është të kthejnë disa vlera të paracaktuara nëse bëhet një akses në një qelizë të papërcaktuar.
Kjo mund të zbatohet duke përdorur funksionin në COS. Ky shembull shqyrton një grup 3-dimensional.
SET a = $GET(^a(x,y,z), defValue)Cilat detyra kërkojnë vargje të rralla dhe si mund të ndihmojnë globalët?
Matrica e fqinjësisë (lidhshmërisë).
përdoret për të paraqitur grafikët:
Natyrisht, sa më i madh të jetë grafiku, aq më shumë zero do të ketë në matricë. Nëse, për shembull, marrim një grafik të rrjetit social dhe e paraqesim atë në formën e një matrice të ngjashme, atëherë ai pothuajse tërësisht do të përbëhet nga zero, d.m.th. do të jetë një grup i rrallë.
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 kursejmë globalisht ^m matrica e lidhjes, si dhe numri i skajeve në secilën nyje (kush është shok me kë dhe numri i miqve).
Nëse numri i elementeve në grafik nuk është më shumë se 29 milion (ky numër merret si prodhim i 8 * ), domethënë, një mënyrë edhe më ekonomike për të ruajtur matrica të tilla janë vargjet e bitave, pasi zbatimi i tyre optimizon boshllëqet e mëdha në një mënyrë të veçantë.
Manipulimet me vargjet e biteve kryhen nga funksioni .
; установка бита
SET $BIT(rowID, positionID) = 1
; получение бита
Write $BIT(rowID, positionID)
Tabela e tranzicionit të makinës së gjendjes
Meqenëse grafiku i tranzicionit të një automati të fundëm është një grafik i zakonshëm, atëherë tabela e tranzicionit e automatit të fundëm është e njëjta matricë fqinjësie e diskutuar më sipër.
Automata celulare
Automatoni celular më i famshëm është , e cila, për shkak të rregullave të saj (kur një qelizë ka shumë fqinjë, ajo vdes) është një grup i rrallë.
Stephen Wolfram beson se automatet celulare janë . Në vitin 2002, ai botoi një libër me 1280 faqe, Një lloj i ri i shkencës, në të cilin ai argumenton gjerësisht se përparimet në automatet celulare nuk janë të izoluara, por janë të qëndrueshme dhe kanë implikime të mëdha për të gjitha fushat e shkencës.
Është vërtetuar se çdo algoritëm i ekzekutueshëm në një kompjuter mund të zbatohet duke përdorur një automat celular. Automatat celulare përdoren për të modeluar mjedise dhe sisteme dinamike, për zgjidhjen e problemeve algoritmike dhe për qëllime të tjera.
Nëse kemi një fushë të madhe dhe duhet të regjistrojmë të gjitha gjendjet e ndërmjetme të një automati celular, atëherë ka kuptim të përdorim globalët.
Hartografia
Gjëja e parë që më vjen në mendje kur bëhet fjalë për përdorimin e grupeve të rralla janë detyrat e hartës.
Si rregull, ka shumë hapësirë boshe në harta. Nëse harta paraqitet si pikselë të mëdhenj, atëherë 71% e pikselave të Tokës do të pushtohen nga oqeani. Varg i rrallë. Dhe nëse aplikoni vetëm vepra të duarve të njeriut, atëherë hapësira boshe do të jetë më shumë se 95%.
Sigurisht, askush nuk i ruan hartat në formën e grupeve raster; përdoret një paraqitje vektoriale.
Por çfarë janë hartat vektoriale? Ky është një lloj kornize dhe polilinash dhe poligonesh të përbërë nga pika.
Në thelb një bazë të dhënash pikash dhe lidhjesh ndërmjet tyre.
Një nga misionet më ambicioze të hartës është misioni i teleskopit Gaia për të hartuar galaktikën tonë. Në mënyrë figurative, galaktika jonë, si i gjithë universi, është një grup i rrallë i vazhdueshëm: hapësira të mëdha zbrazëtie në të cilat ka pika të rralla të vogla - yje. Hapësira e zbrazët është 99,999999…….%. Për të ruajtur hartën e galaktikës sonë, u zgjodh një bazë të dhënash globale - Cache.
Nuk e di strukturën e saktë të globalëve në këtë projekt, mund të supozoj se është diçka e ngjashme me:
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
...
Ku janë b, l, d dhe distancën nga Dielli.
Struktura fleksibël e globalëve ju lejon të ruani çdo karakteristikë të nevojshme të yjeve dhe planetëve, pasi bazat në globale janë pa skema.
Për të ruajtur hartën e universit tonë, Cache u zgjodh jo vetëm për fleksibilitetin e tij, por edhe për aftësinë e tij për të ruajtur një rrjedhë të dhënash shumë shpejt, duke krijuar njëkohësisht indekse globale për kërkime të shpejta.
Nëse kthehemi në Tokë, atëherë u krijuan projekte hartografike mbi globalët dhe një degë e OpenStreetMap - .
Kohët e fundit në u zbatuan indekset gjeohapësinore . Ne presim një artikull nga autorët me detajet e zbatimit.
Zbatimi i indekseve hapësinore në një global në OpenStreetMap XAPI
Fotot e marra nga .
I gjithë globi është i ndarë në katrorë, pastaj në nën-katrorë dhe nën-katrorë në nën-katrorë, e kështu me radhë. Në përgjithësi, marrim një strukturë hierarkike për ruajtjen e të cilave janë krijuar globalët.
Në çdo moment, ne mund të kërkojmë pothuajse menjëherë katrorin e dëshiruar ose ta pastrojmë atë, dhe të gjitha nën-sheshet gjithashtu do të kthehen ose pastrohen.
Një skemë e ngjashme për globalët mund të zbatohet 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) = idПервойТочки
Set ^m(a, b, a, c, d, a, b,c, d, a, b, a, c, d, a, b,c, d, a, 2) = idВторойТочки
...Opsioni 2:
Set ^m('abacdabcdabacdabcda', 1) = idПервойТочки
Set ^m('abacdabcdabacdabcda', 2) = idВторойТочки
...Në të dyja rastet, nuk është e vështirë të përdorësh COS/M për të kërkuar pika të vendosura në një shesh të çdo niveli. Do të jetë disi më e lehtë për të pastruar pjesë katrore të hapësirës në çdo nivel në opsionin e parë, por kjo është rrallë e nevojshme.
Një shembull i një prej katrorëve të nivelit më të ulët:
Dhe këtu janë disa globale nga projekti XAPI: përfaqësimi i një indeksi mbi globalët:
globale ^ mënyrë përdoret për të ruajtur pikat (rrugë, lumenj të vegjël etj.) dhe poligone (zona të mbyllura: ndërtesa, pyje etj.).
Klasifikimi i përafërt i përdorimit të vargjeve të rralla në globale.
- Ne ruajmë koordinatat e objekteve të caktuara dhe gjendjet e tyre (hartë, automata celulare)
- Ne ruajmë matrica të rralla.
Për rastin 2) kur kërkojmë një koordinatë specifike ku elementit nuk i caktohet një vlerë, duhet të marrim vlerën e elementit të paracaktuar të grupit të rrallë.
Bonuset që marrim kur ruajmë matricat shumëdimensionale në globale
Hiqni shpejt dhe/ose zgjidhni pjesë të hapësirës që janë shumëfish rreshtash, planesh, kubesh, etj. Për rastet kur përdoren indekset e numrave të plotë, mund të jetë e dobishme aftësia për të hequr dhe/ose për të marrë me shpejtësi pjesë të hapësirës që janë shumëfish rreshtash, planesh, kubesh etj.
ekipi ne mund të fshijmë ose një element të vetëm ose një rresht, ose edhe një plan të tërë. Falë vetive të globalëve, kjo ndodh shumë shpejt - mijëra herë më shpejt se heqja element pas elementi.
Figura tregon një grup tre-dimensional në një global ^a dhe lloje të ndryshme fshirjesh.
Për të zgjedhur pjesë të hapësirës duke përdorur indekse të njohura, mund të përdorni komandën .
Zgjedhja e një kolone matrice në variablin Column:
; Зададим трёхмерный разреженный массив 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
Përfundim:
Column(0)=1
Column(2)=1
Ajo që është interesante për variablin Column është se ne kemi gjithashtu një grup të rrallë, i cili gjithashtu duhet të aksesohet përmes , pasi vlerat e paracaktuara nuk ruhen në të.
Përzgjedhja e pjesëve të hapësirës mund të bëhet gjithashtu përmes një programi të vogël duke përdorur funksionin . Kjo është veçanërisht e përshtatshme për hapësirat, indekset e të cilave nuk janë të kuantizuara (hartografia).
Përfundim
Kohët aktuale parashtrojnë detyra të reja ambicioze. Grafikët mund të përbëhen nga miliarda kulme, hartat e përbëra nga miliarda pika dhe disa madje mund të dëshirojnë të drejtojnë universin e tyre në automata celulare (, ).
Kur vëllimi i të dhënave nga grupe të rralla nuk mund të futet më në RAM, por duhet të punoni me ta, atëherë ia vlen të merret parasysh mundësia e zbatimit të projekteve të ngjashme në globale dhe COS.
Faleminderit per vemendjen! Ne presim pyetjet dhe dëshirat tuaja në komente.
Mohim përgjegjësie: Ky artikull dhe komentet e mia për të janë mendimi im dhe nuk përfaqësojnë qëndrimin zyrtar të InterSystems Corporation.
Burimi: www.habr.com