Në pjesët e kaluara (, ) kemi folur për globalët si pemë, në këtë do të shikojmë globalët si masa të shpërndara.
është një lloj mase në të cilën shumica e vlerave merr një vlerë të njëjtë.
Në praktikë, shpesh hasen kaq të mëdha masa të shpërndara, saqë nuk ka asnjë kuptim të zëvendësohen kujtesa me elemente të njëjtë. Prandaj ka kuptim për të implementuar masat e shpërndara në mënyrë që kujtesa të mos harxhohet për ruajtjen e vlerave të njëjta.
NĂ« disa gjuhĂ« programuese, masat e shpĂ«rndara pĂ«rfshihen nĂ« vetĂ« gjuhĂ«n, , . NĂ« gjuhĂ« tĂ« tjera programuese ka biblioteka speciale qĂ« lejojnĂ« implementimin e tyre. PĂ«r C++ â etj.
Globalët janë kandidatë të mirë për implementimin e masave të shpërndara, sepse:
- Ruajnë vlerat e nyjeve të caktuara dhe nuk ruajnë vlerat e paqarta;
- Interfejsi i qasjes në vlerën e një nyjeje është jashtëzakonisht i ngjashëm me atë se si në shumë gjuhë programuese implementohet qasja në elementin e një mase shumëdimensionale.
Set ^a(1, 2, 3)=5 Write ^a(1, 2, 3) - Globali është një strukturë mjaft në nivel të ulët për ruajtjen e të dhënave, prandaj ka përfitime të shkëlqyera në shpejtësi (nga qindra mijëra deri në dhjetëra milion transaksione në sekondë në varësi të hardware-it, shih. )
Pasi që globali është një strukturë e përhershme, ka kuptim të krijosh masa të shpërndara mbi to kur dihet paraprakisht se do të mungoj kapaciteti i kujtesës RAM.
Një nga veçoritë e implementimeve të masave të shpërndara është kthimi i një vlerë që është e definuar si default, nëse qasja kryhet në një qelizë të paqartë.
Kjo mund të implementohet duke përdorur funksionin në COS. Në këtë shembull shqyrtohet një masë tre-dimensionale.
SET a = $GET(^a(x,y,z), defValue)Në cilat probleme kërkohen masat e shpërndara dhe si mund të ndihmojnë globalët?
Matricat e lidhjes
përdoren për të përfaqësuar grafet:
ĂshtĂ« e qartĂ« se sa mĂ« i madh tĂ« jetĂ« grafi, aq mĂ« shumĂ« zero do tĂ« ketĂ« nĂ« matricĂ«. NĂ«se, pĂ«r shembull, e marrĂ« njĂ« graf tĂ« rrjetit social dhe ta pĂ«rfaqĂ«sosh atĂ« si njĂ« matricĂ« tĂ« tillĂ«, atĂ«herĂ« ai do tĂ« pĂ«rbĂ«het kryesisht nga zero, dmth do tĂ« jetĂ« njĂ« masĂ« e shpĂ«rndarĂ«.
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 matricën e lidhjes, si dhe numrin e lidhjeve për çdo nyje (kush është miq me kë dhe numrin e miqve).
NĂ«se numri i elementeve nĂ« graf nuk Ă«shtĂ« mĂ« shumĂ« se 29 milion (kjo numĂ«r merret si produkt i 8 * ), atĂ«herĂ« ka njĂ« mĂ«nyrĂ« edhe mĂ« ekonomike pĂ«r ruajtjen e kĂ«tyre matricave â vargjet e bitĂ«ve, pasi nĂ« implementimin e tyre optimizohen nĂ« mĂ«nyrĂ« speciale hapĂ«sirat e mĂ«dha.
Manovrat me vargjet e bitëve kryhen me funksionin .
; vendosja e bitit
SET $BIT(rowID, positionID) = 1
; marrja e bitit
Write $BIT(rowID, positionID)
Tabelat e kalimeve të automatit të kufizuar
Duke qenĂ« se grafi i kalimeve tĂ« automatit tĂ« kufizuar Ă«shtĂ« njĂ« grafik i zakonshĂ«m, ashtu Ă«shtĂ« edhe tabela e kalimeve tĂ« automatit tĂ« kufizuar â Ă«shtĂ« po ajo matricĂ« e lidhjes pĂ«r tĂ« cilĂ«n u pĂ«rmend mĂ« sipĂ«r.
Automatet qelizore
Automati mĂ« i njohur qelizor Ă«shtĂ« , e cila pĂ«r shkak tĂ« rregullave tĂ« saj (kur njĂ« qelizĂ« ka shumĂ« fqinjĂ« â ajo vdes) pĂ«rfaqĂ«son njĂ« masĂ« tĂ« shpĂ«rndarĂ«.
Stephen Wolfram, beson se automatet qelizore janë një . Në vitin 2002 ai publikoi librin 1280-faqesh "A New Kind of Science", ku argumenton gjerësisht se arritjet në fushën e automatëve qelizorë nuk janë të izoluara, por mjaft të qëndrushme dhe kanë një rëndësi të madhe për të gjitha fushat e shkencës.
ĂshtĂ« provuar se çdo algoritĂ«m qĂ« mund tĂ« ekzekutohet nĂ« njĂ« kompjuter mund tĂ« implementohet nĂ«pĂ«rmjet njĂ« automati qelizor. AutomatĂ«t qelizorĂ« pĂ«rdoren pĂ«r modelimin e mjediseve dhe sistemeve dinamike, pĂ«r zgjidhjet e problemeve algoritmike dhe pĂ«r qĂ«llime tĂ« tjera.
Nëse kemi një fushë të madhe dhe na nevojitet të shkruajmë të gjitha gjendjet ndërmjetëse të automatit qelizor, atëherë ka kuptim të përdorim globalët.
Kartografia
E para që më vjen në mendje kur flasim për përdorimin e masave të shpërndara është detyrat kartografike.
Si rregull, në hartat ka shumë hapësirë të zbrazët. Nëse e përfaqësojmë hartën si pikselet e mëdha, atëherë 71% e pikseleve të Tokës do të ishin të zëna nga oqeani. Një masë e shpërndarë. Dhe nëse aplikojmë vetëm krijesat e dorës së njeriut, atëherë hapësira e zbrazët do të jetë më shumë se 95%.
Sigurisht, askush nuk i ruan hartat si masa rastere, përdoret përfaqësimi vektorial.
Por çfarë përfaqësojnë harta vektoriale? Ato janë një kuadër dhe përbëhen nga pika, polilinje dhe poligone.
Faktikisht, baza e të dhënave të pikave dhe lidhjeve midis tyre.
NjĂ« nga detyrat mĂ« ambicioze tĂ« hartĂ«zimit Ă«shtĂ« misioni i hartĂ«zimit tĂ« galaktikĂ«s sonĂ« me teleskopin Gaia. Metaforikisht, galaktika jonĂ«, ashtu si tĂ« gjithĂ« universi, Ă«shtĂ« njĂ« masĂ« e holluar: hapĂ«sira tĂ« mĂ«dha bosh, nĂ« tĂ« cilat ka pika tĂ« vogla tĂ« rralla - yje. HapĂ«sirĂ« e zbrazĂ«t 99,999999âŠâŠ.%. PĂ«r tĂ« ruajtur hartĂ«n e galaktikĂ«s sonĂ«, Ă«shtĂ« zgjedhur njĂ« bazĂ« tĂ« dhĂ«nash nĂ« globalĂ«t - CachĂ©.
Nuk e di strukturën e saktë të globalëve në këtë projekt, mund të supozoj se është diçka si:
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"; variante blackhole, quasar, 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 globalëve lejon ruajtjen e karakteristikave të nevojshme të yjeve dhe planetëve, pasi bazat në globalët janë pa skema (scheme-less).
Për ruajtjen e hartës së universit tonë, Caché u zgjodh jo vetëm për fleksibilitetin e saj, por edhe për aftësinë për të ruajtur shumë shpejt fluxin e të dhënave, duke krijuar njëkohësisht globalë indeksues për kërkimin e shpejtë.
NĂ«se kthehemi nĂ« TokĂ«, janĂ« krijuar projekte hartĂ«zimi nĂ« globalĂ« dhe forku OpenStreetMap â .
Së fundmi në janë realizuar indekset gjeohapësinore . Po presim nga autorët e artikullit detajet e implementimit.
Implementimi i indekseve hapësinore në global në OpenStreetMap XAPI
Imazhet janë marrë nga .
Të gjithë globi tokësor ndahet në katrorë, pastaj nënkatrore, dhe nënkatrore në nën-nënkatrore dhe 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 nevojshëm ose ta pastrojmë atë, ku të gjitha nënkatrorët gjithashtu do të kthehen ose pastrohen.
Një skemë të tillë në globalë 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) = idPikaEParë
Set ^m(a, b, a, c, d, a, b, c, d, a, b, a, c, d, a, b, c, d, a, 2) = idPikaEDytë
...Opsioni 2:
Set ^m('abacdabcdabacdabcda', 1) = idPikaEParë
Set ^m('abacdabcdabacdabcda', 2) = idPikaESecond
...Në të dy rastet, nuk është e vështirë në COS/M të kërkosh pikat që ndodhen në katrorin e çdo niveli. Disa më lehtë do të jetë të pastrosh copat katrore të hapësirës së çdo niveli në versionin e parë, por kjo është e rrallë.
Një shembull i një nga katrorët e nivelit të ulët:
Dhe këtu janë disa globalë nga projekti XAPI: paraqitja e indeksit në globalë:
Global ^way përdoret për ruajtjen e pikave (rrugë, lume, etj.) dhe poligoneve (zona të mbyllura: ndërtesa, pyje, etj.).
Klasifikimi i bardhë i përdorimit të masivave të holluara në globalë.
- Ne ruajmë koordinatat e disa objekteve dhe gjendjet e tyre (hartëzimi, automatat qelizore)
- Ne ruajmë matrica të holluara.
Për rastin 2) kur etiketat e caktuara për koordinatën nuk janë caktuar, duhet të marrim vlerën e elementit të masivave të holluara sipas parimit të parazgjedhjes.
Bonuset që marrim nga ruajtja e matrica të shumë dimensionale në globalë
Shkëputje dhe/ose seleksionimi i copave të hapësirës, që janë të shumëfishueshme nga rreshta, panelet, kubet, etj. Për rastet kur përdoren indekse të numrave të plotë, mund të jetë e dobishme mundësia e shpejtë për të fshirë dhe/ose seleksionuar copat e hapësirës, që janë të shumëfishueshme nga rreshta, panelet, kubet, etj.
Me komandĂ«n mund tĂ« fshijmĂ« si njĂ« element tĂ« vetĂ«m, ashtu edhe njĂ« rresht, dhe madje njĂ« panel tĂ« tĂ«rĂ«. FalĂ« pronave tĂ« globalĂ«ve, kjo ndodh shumĂ« shpejt â mijĂ«ra herĂ« mĂ« shpejt sesa fshirja element pas elementi.
Në figurë është paraqitur një masiv tre-dimensional në globalin ^a dhe llojet e ndryshme të fshirjeve.
Për seleksionimin e copave të hapësirës sipas indekseve të njohura, mund të përdoret komanda .
Selektoje kolonën e matricës në variablën Column:
; Le të caktuar një masiv të holluar tre-dimensional 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)
; Le të nxjerrim variablën Column
Zwrite Column
Dalja:
Column(0)=1
Column(2)=1
ĂfarĂ« Ă«shtĂ« interesante nĂ« variablĂ«n Column Ă«shtĂ« se ne gjithashtu kemi njĂ« masiv tĂ« holluar, tĂ« cilin duhet ta adresojmĂ« gjithashtu pĂ«rmes , pasi vlerat e parazgjedhura nĂ« tĂ« nuk ruhen.
Selektysi i 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 përshtatshme në hapësirat, të cilat indekset e tyre nuk janë të kuantizuar (hartëzimi).
PĂ«rfundimi
Koha aktuale sjell detyra të reja ambicioze. Grafet mund të përbëhen nga miliarda majash, hartat nga miliarda pikash, dhe ndokush madje mund të dëshirojë të nisë universin e tij me automatat qelizore (, ).
Kur volume i të dhënave të masivave të shpërndara nuk mund të vendoset më në memo rinore, por është e nevojshme të punohet me to, është e arsyeshme të shqyrtohet mundësia e realizimit të projekteve të tilla në globalë dhe COS.
Faleminderit për vëmendjen! Presim pyetjet dhe sugjerimet tuaja në komentet.
Shënim ligjor: Ky artikull dhe komentet e mia për të janë mendimi im dhe nuk kanë lidhje me pozitat zyrtare të korporatës InterSystems.
Burimi: habr.com
