In vorige dele (, ) ons het gepraat oor globale as bome, in hierdie een sal ons kyk na globale as yl skikkings.
is 'n tipe skikking waarin die meeste van die waardes dieselfde waarde neem.
In die praktyk is yl skikkings dikwels so groot dat dit geen sin is om geheue met identiese elemente te beset nie. Daarom maak dit sin om yl skikkings op so 'n manier te implementeer dat geheue nie vermors word om identiese waardes te stoor nie.
In sommige programmeertale word yl skikkings by die taal self ingesluit, , . Ander programmeertale het spesiale biblioteke wat jou toelaat om dit te implementeer. Vir C++ - ens.
Globale is goeie kandidate vir die implementering van yl skikkings omdat:
- Hulle stoor die waardes van slegs sekere nodusse en stoor nie die waardes van ongedefinieerdes nie;
- Die koppelvlak vir toegang tot 'n nodus se waarde is baie soortgelyk aan hoeveel programmeertale toegang tot 'n multidimensionele skikkingselement implementeer.
Set ^a(1, 2, 3)=5 Write ^a(1, 2, 3) - Global is 'n redelike lae-vlak struktuur vir die stoor van data, daarom het dit uitstekende spoedeienskappe (van honderdduisende tot tienmiljoene transaksies per sekonde, afhangend van die hardeware, sien hieronder). )
Aangesien die globale 'n aanhoudende struktuur is, maak dit sin om yl skikkings daarop te skep wanneer dit vooraf bekend is dat die hoeveelheid RAM nie genoeg sal wees nie.
Een van die eienskappe van yl skikking-implementerings is om 'n standaardwaarde terug te gee as 'n toegang tot 'n ongedefinieerde sel gemaak word.
Dit kan geïmplementeer word met behulp van die funksie in COS. Hierdie voorbeeld beskou 'n 3-dimensionele skikking.
SET a = $GET(^a(x,y,z), defValue)Watter take vereis yl skikkings en hoe kan globals help?
Adjacency (konnektiwiteit) matriks
gebruik om grafieke voor te stel:
Natuurlik, hoe groter die grafiek, hoe meer nulle sal daar in die matriks wees. As ons byvoorbeeld 'n sosiale netwerkgrafiek neem en dit in die vorm van 'n soortgelyke matriks aanbied, dan sal dit feitlik geheel en al uit nulle bestaan, d.w.s. sal 'n yl verskeidenheid wees.
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
....
In hierdie voorbeeld spaar ons wêreldwyd ^m konnektiwiteitsmatriks, sowel as die aantal rande by elke nodus (wie is vriende met wie en die aantal vriende).
As die aantal elemente in die grafiek nie meer as 29 miljoen is nie (hierdie getal word geneem as die produk van 8 * ), dit wil sê, 'n selfs meer ekonomiese manier om sulke matrikse te stoor, is bietjie snare, aangesien die implementering daarvan groot gapings op 'n spesiale manier optimaliseer.
Manipulasies met bisstringe word deur die funksie uitgevoer .
; установка бита
SET $BIT(rowID, positionID) = 1
; получение бита
Write $BIT(rowID, positionID)
Staat masjien oorgang tabel
Aangesien die oorgangsgrafiek van 'n eindige outomaat 'n gewone grafiek is, is die oorgangstabel van die eindige outomaat dieselfde aangrensende matriks wat hierbo bespreek is.
Sellulêre outomatiese
Die bekendste sellulêre outomaat is , wat as gevolg van sy reëls (wanneer 'n sel baie bure het, sterf dit) 'n yl skikking is.
Stephen Wolfram glo dat sellulêre outomatiese is . In 2002 het hy 'n boek van 1280 XNUMX bladsye, A New Kind of Science, gepubliseer waarin hy breedweg aanvoer dat vooruitgang in sellulêre outomatate nie geïsoleer is nie, maar blywend is en groot implikasies vir alle gebiede van die wetenskap inhou.
Dit is bewys dat enige algoritme wat op 'n rekenaar uitgevoer kan word, met behulp van 'n sellulêre outomaat geïmplementeer kan word. Sellulêre outomata word gebruik om dinamiese omgewings en stelsels te modelleer, om algoritmiese probleme op te los en vir ander doeleindes.
As ons 'n groot veld het en ons moet al die tussentoestande van 'n sellulêre outomaat opneem, dan maak dit sin om globales te gebruik.
Kartografie
Die eerste ding wat by my opkom wanneer dit kom by die gebruik van yl skikkings, is karteringtake.
As 'n reël is daar baie leë spasie op kaarte. As die kaart as groot pixels voorgestel word, sal 71% van die Aarde se pixels deur die see beset word. Skaars verskeidenheid. En as jy slegs werke van menslike hande toepas, sal die leë spasie meer as 95% wees.
Natuurlik stoor niemand kaarte in die vorm van raster-skikkings nie; 'n vektorvoorstelling word gebruik.
Maar wat is vektorkaarte? Dit is 'n soort raam en veellyne en veelhoeke wat uit punte bestaan.
In wese 'n databasis van punte en verbindings tussen hulle.
Een van die mees ambisieuse karteringsendings is die Gaia Telescope-sending om ons sterrestelsel te karteer. Figuurlik gesproke is ons sterrestelsel, soos die hele heelal, 'n aaneenlopende yl verskeidenheid: groot ruimtes van leegheid waarin daar skaars klein punte - sterre - is. Leë spasie is 99,999999…….%. Om die kaart van ons sterrestelsel te stoor, is 'n globale databasis gekies - Caché.
Ek ken nie die presiese struktuur van globale in hierdie projek nie, ek kan aanneem dat dit iets soortgelyks is aan:
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
...
Waar b, l, d is en afstand na die son.
Die buigsame struktuur van globaal laat jou toe om enige nodige kenmerke van sterre en planete te stoor, aangesien die basisse op globaal skemaloos is.
Om die kaart van ons heelal te stoor, is Caché nie net gekies vir sy buigsaamheid nie, maar ook vir sy vermoë om 'n stroom data baie vinnig te stoor, terwyl dit terselfdertyd indeksglobale skep vir vinnige soektogte.
As ons terugkeer na die aarde, dan is kartografiese projekte op globales geskep en 'n vurk van OpenStreetMap - .
Onlangs aan georuimtelike indekse is geïmplementeer . Ons wag vir 'n artikel van die skrywers met implementeringsbesonderhede.
Implementering van ruimtelike indekse op 'n globale in OpenStreetMap XAPI
Foto's geneem uit .
Die hele aardbol is verdeel in vierkante, dan sub-kwadrate, en sub-kwadrate in sub-sub-kwadrate, ensovoorts. Oor die algemeen kry ons 'n hiërargiese struktuur om te stoor watter globales geskep word.
Op enige oomblik kan ons byna onmiddellik die verlangde vierkant aanvra of dit uitvee, en alle sub-vierkante sal ook teruggestuur of skoongemaak word.
'n Soortgelyke skema op globales kan op verskeie maniere geïmplementeer word.
Opsie 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ВторойТочки
...Opsie 2:
Set ^m('abacdabcdabacdabcda', 1) = idПервойТочки
Set ^m('abacdabcdabacdabcda', 2) = idВторойТочки
...In beide gevalle is dit nie moeilik om COS/M te gebruik om punte aan te vra wat in 'n vierkant van enige vlak geleë is nie. Dit sal ietwat makliker wees om vierkantige stukke spasie op enige vlak in die eerste opsie skoon te maak, maar dit is selde nodig.
'n Voorbeeld van een van die laer vlak vierkante:
En hier is verskeie globale van die XAPI-projek: voorstelling van 'n indeks op globale:
wêreldwyd ^ manier gebruik om punte te stoor (paaie, klein riviere, ens.) en veelhoeke (geslote gebiede: geboue, woude, ens.).
Rowwe klassifikasie van die gebruik van yl skikkings op globales.
- Ons stoor die koördinate van sekere voorwerpe en hul toestande (kartering, sellulêre outomatiese)
- Ons stoor yl matrikse.
Vir geval 2) wanneer 'n spesifieke koördinaat versoek word waar die element nie 'n waarde toegeken is nie, moet ons die waarde van die verstek yl skikking element kry.
Bonusse wat ons ontvang wanneer multidimensionele matrikse in globales gestoor word
Verwyder en/of kies stukke spasie vinnig wat veelvoude van rye, vlakke, kubusse, ens. Vir gevalle waar heelgetalindekse gebruik word, kan die vermoë om vinnig stukke spasie wat veelvoude van rye, vlakke, kubusse, ens. is, te verwyder en/of te haal, nuttig wees.
span ons kan óf 'n enkele element óf 'n ry uitvee, of selfs 'n hele vliegtuig. Danksy die eienskappe van globale, gebeur dit baie vinnig - duisende kere vinniger as element-vir-element verwydering.
Die figuur toon 'n driedimensionele skikking in 'n globale ^a en verskillende tipes skrappings.
Om stukke spasie te kies met behulp van bekende indekse, kan jy die opdrag gebruik .
Kies 'n matrikskolom in die Kolomveranderlike:
; Зададим трёхмерный разреженный массив 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
Gevolgtrekking:
Column(0)=1
Column(2)=1
Wat interessant is omtrent die Kolom-veranderlike, is dat ons ook 'n yl skikking het, wat ook deur , aangesien verstekwaardes nie daarin gestoor word nie.
Die keuse van stukkies spasie kan ook gedoen word deur 'n klein program met behulp van die funksie . Dit is veral gerieflik op spasies waarvan die indekse nie gekwantiseer is nie (kartografie).
Gevolgtrekking
Die huidige tye bied nuwe ambisieuse take. Grafieke kan saamgestel word uit biljoene hoekpunte, kaarte wat uit biljoene punte bestaan, en sommige sal dalk selfs hul eie heelal op sellulêre outomata wil bestuur (, ).
Wanneer die volume data van yl skikkings nie meer in RAM kan pas nie, maar jy moet daarmee werk, dan is dit die moeite werd om die moontlikheid te oorweeg om soortgelyke projekte op globale en COS te implementeer.
Dankie vir jou aandag! Ons wag vir jou vrae en wense in die kommentaar.
Vrywaring: Hierdie artikel en my kommentaar daarop is my mening en verteenwoordig nie die amptelike standpunt van InterSystems Corporation nie.
Bron: will.com