A fréieren Deeler (, ) hu mir iwwer Globalen als Beem geschwat, an dësem wäerte mir d'Globaler als spatzen Arrays kucken.
ass eng Zort Array an där déi meescht Wäerter dee selwechte Wäert huelen.
An der Praxis sinn sparse Arrays dacks sou enorm datt et kee Sënn ass fir Erënnerung mat identeschen Elementer ze besetzen. Dofir ass et Sënn fir spatzen Arrays op sou eng Manéier ëmzesetzen datt d'Erënnerung net verschwend gëtt fir identesch Wäerter ze späicheren.
An e puer Programméierungssprooche sinn sparse Arrays an der Sprooch selwer abegraff, , . Aner Programméierungssproochen hu speziell Bibliothéiken déi Iech erlaben se ëmzesetzen. Fir C++ - an anerer.
Globale si gutt Kandidate fir sparse Arrays ëmzesetzen well:
- Si späicheren d'Wäerter vu bestëmmte Wirbelen a späicheren net d'Wäerter vun ondefinéierten;
- D'Interface fir Zougang zu engem Node Wäert ass extrem ähnlech wéi vill Programméierungssproochen Zougang zu engem multidimensionalen Array-Element implementéieren.
Set ^a(1, 2, 3)=5 Write ^a(1, 2, 3) - Global ass eng zimlech niddereg-Niveau Struktur fir Daten ze späicheren, dofir huet et aussergewéinlech Geschwindegkeetseigenschaften (vun honnertdausende bis zéngdausende vu Millioune Transaktiounen pro Sekonn, ofhängeg vun der Hardware, kuckt hei ënnen). )
Well d'Global eng persistent Struktur ass, mécht et Sënn fir spatzen Arrays op hinnen ze kreéieren wann et am Viraus bekannt ass datt d'Quantitéit vum RAM net genuch ass.
Ee vun den Eegeschafte vu sparse Array-Implementatiounen ass e puer Standardwäert zréckzeginn wann en Zougang zu enger ondefinéierter Zell gemaach gëtt.
Dëst kann mat der Funktioun ëmgesat ginn an der COS. Dëst Beispill betruecht eng 3-zweedimensional Array.
SET a = $GET(^a(x,y,z), defValue)Wéi eng Aufgaben erfuerderen schaarf Arrays a wéi kënne Globale hëllefen?
Adjacency (Konnektivitéit) Matrixentgasung
benotzt fir Grafiken ze representéieren:
Natierlech, wat d'Grafik méi grouss ass, wat méi Nullen an der Matrix sinn. Wa mir zum Beispill e sozialen Netzwierk Grafik huelen a se a Form vun enger ähnlecher Matrix presentéieren, da besteet se bal ganz aus Nullen, d.h. wäert eng schaarf Array sinn.
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
....
An dësem Beispill späichere mir global ^m Konnektivitéitsmatrix, souwéi d'Zuel vun de Kanten op all Node (wien ass Frënn mat wiem an d'Zuel vu Frënn).
Wann d'Zuel vun den Elementer an der Grafik net méi wéi 29 Milliounen ass (dës Zuel gëtt als Produkt vun 8 geholl * ), dat heescht, eng nach méi ekonomesch Manéier fir esou Matrizen ze späicheren ass Bit Strings, well hir Ëmsetzung grouss Lücken op eng speziell Manéier optiméiert.
Manipulatioune mat Bit Strings ginn duerch d'Funktioun ausgefouert .
; установка бита
SET $BIT(rowID, positionID) = 1
; получение бита
Write $BIT(rowID, positionID)
Staat Maschinn Transitioun Dësch
Zënter datt d'Iwwergangsgrafik vun engem endlechen Automat eng gewéinlech Grafik ass, dann ass d'Iwwergangstabelle vum endlechen Automaton déiselwecht Adjacency Matrix, déi hei uewen diskutéiert gouf.
Zellautomaten
De bekanntste celluläre Automat ass , déi wéinst senge Reegelen (wann eng Zell vill Noperen huet, stierft se) e spatzen Array ass.
De Stephen Wolfram mengt datt cellulär Automaten sinn . Am Joer 2002 huet hien en 1280-Säit Buch publizéiert, A New Kind of Science, an deem hien breet argumentéiert datt Fortschrëtter an de celluläre Automaten net isoléiert sinn, mee dauerhaft sinn a grouss Implikatioune fir all Beräicher vun der Wëssenschaft hunn.
Et gouf bewisen datt all Algorithmus ausféierbar op engem Computer ka mat engem celluläre Automat implementéiert ginn. Cellular Automata gi benotzt fir dynamesch Ëmfeld a Systemer ze modelléieren, fir algorithmesch Probleemer ze léisen an fir aner Zwecker.
Wa mir e grousst Feld hunn a mir mussen all Zwëschenzoustand vun engem celluläre Automat ophuelen, da mécht et Sënn fir Globalen ze benotzen.
Kartographie
Déi éischt Saach déi a mengem Kapp kënnt wann et drëm geet spatzen Arrays ze benotzen ass Kartéierungsaufgaben.
Als Regel, ass et vill eidel Plaz op Kaarten. Wann d'Kaart als grouss Pixel duergestallt gëtt, da wäerten 71% vun de Pixel vun der Äerd vum Ozean besat sinn. Spuert Array. A wann Dir nëmmen Wierker vu mënschlechen Hänn applizéiert, da wäert den eidele Raum méi wéi 95% sinn.
Natierlech späichert keen Kaarten a Form vu Rasterarrays; eng Vektorrepresentatioun gëtt benotzt.
Awer wat sinn Vektorkaarten? Dëst ass eng Aart Frame a Polylinen a Polygone besteet aus Punkten.
Wesentlech eng Datebank vu Punkten a Verbindungen tëscht hinnen.
Eng vun den ambitiéissten Kartéierungsmissiounen ass d'Gaia Telescope Missioun fir eis Galaxis ze kartéieren. Figurativ gesinn ass eis Galaxis, wéi de ganzen Universum, eng kontinuéierlech spatzen Array: rieseg Leerraum an deenen et selten kleng Punkte gëtt - Stären. Eidel Plaz ass 99,999999…….%. Fir d'Kaart vun eiser Galaxis ze späicheren, gouf eng global Datebank gewielt - Caché.
Ech weess net déi exakt Struktur vun de Globalen an dësem Projet, ech kann unhuelen datt et eppes ähnlech ass wéi:
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
...
Wou b, l, d sinn an Distanz zu der Sonn.
Déi flexibel Struktur vu Globalen erlaabt Iech all néideg Charakteristike vu Stären a Planéiten ze späicheren, well d'Basis op Globale Schema-manner sinn.
Fir d'Kaart vun eisem Universum ze späicheren, gouf Caché gewielt net nëmme fir seng Flexibilitéit, awer och fir seng Fäegkeet fir e Stream vun Daten ganz séier ze späicheren, a gläichzäiteg Indexglobale fir séier Recherchen ze kreéieren.
Wa mir op d'Äerd zréckkommen, da goufe kartographesch Projeten op Globalen erstallt an eng Gabel vun OpenStreetMap - .
Viru kuerzem op geospatial Indexen ëmgesat goufen . Mir waarden op en Artikel vun den Auteuren mat Ëmsetzungsdetailer.
Ëmsetzung vun raimlechen Indexen op engem globale an OpenStreetMap XAPI
Biller geholl aus .
De ganze Globus ass opgedeelt a Quadrat, dann Ënner-Quadraten, an Ënner-Square an Ënner-Ënner-Square, a sou weider. Allgemeng kréie mir eng hierarchesch Struktur fir ze späicheren wéi eng Globale erstallt ginn.
Zu all Moment kënne mir bal direkt de gewënschten Quadrat ufroen oder se läschen, an all Ënnerplaze ginn och zréck oder geläscht.
En ähnleche Schema op Globalen kann op verschidde Manéieren ëmgesat ginn.
Optioun 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ВторойТочки
...Optioun 2:
Set ^m('abacdabcdabacdabcda', 1) = idПервойТочки
Set ^m('abacdabcdabacdabcda', 2) = idВторойТочки
...A béide Fäll ass et net schwéier COS / M ze benotzen fir Punkten op engem Quadrat vun all Niveau ze froen. Et gëtt e bësse méi einfach fir quadratesch Plazen op all Niveau an der éischter Optioun ze botzen, awer dëst ass selten néideg.
E Beispill vun engem vun den ënneschten Niveau Quadrat:
An hei sinn e puer Globalen aus dem XAPI Projet: Representatioun vun engem Index op Globalen:
global ^ Wee benotzt fir Punkten ze späicheren (Stroossen, kleng Flëss, etc.) a Polygonen (zougemaach Beräicher: Gebaier, Bëscher, etc.).
Rau Klassifikatioun vun der Benotzung vun spatzen Arrays op Globalen.
- Mir späicheren d'Koordinate vu bestëmmten Objeten an hiren Zoustand (Mapping, Zellautomaten)
- Mir späicheren spatzen matrices.
Fir Fall 2) wann Dir eng spezifesch Koordinat ufrot, wou d'Element net e Wäert zougewisen ass, musse mir de Wäert vum Standard-sparse Array-Element kréien.
Bonus déi mir kréien wann mir multidimensional Matrixentgasung am Globale späicheren
Schnell ewechhuelen an / oder Plazen auswielen, déi Multiple vu Reihen, Fligeren, Cubes, asw. Fir Fäll wou ganz Indexen benotzt ginn, kann d'Fähigkeit fir séier Stécker vu Raum ze läschen an / oder z'erreechen, déi Multiple vu Reihen, Fligeren, Cubes, etc.
Equipe mir kënnen entweder en eenzegt Element oder eng Rei läschen, oder souguer e ganze Fliger. Duerch d'Eegeschafte vu Globale geschitt dëst ganz séier - Dausende vu Mol méi séier wéi Element-fir-Element Entfernung.
D'Figur weist eng dreidimensional Array an enger globaler ^a a verschidden Zorte vu Läschen.
Fir Stécker vum Raum ze wielen mat bekannten Indexen, kënnt Dir de Kommando benotzen .
Auswiel vun enger Matrix Kolonn an der Kolonn Variabel:
; Зададим трёхмерный разреженный массив 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
Fazit:
Column(0)=1
Column(2)=1
Wat interessant ass iwwer d'Kolonn Variabel ass datt mir och e spatzen Array hunn, déi och zougänglech muss duerch , well Standardwäerter net dran gespäichert sinn.
D'Auswiel vu Stécker Plaz kann och duerch e klenge Programm mat der Funktioun gemaach ginn . Dëst ass besonnesch praktesch op Plazen deenen hir Indizes net quantiséiert sinn (Kartographie).
Konklusioun
Déi aktuell Zäit stellen nei ambitiéis Aufgaben op. Grafike kënnen aus Milliarden Wirbelen zesummegesat sinn, Kaarten aus Milliarde Punkten, an e puer wëllen souguer hiren eegene Universum op celluläre Automaten lafen (, ).
Wann de Volume vun Daten aus spatzen Arrays kann net méi an RAM passen, mä Dir musst mat hinnen schaffen, dann ass et derwäert op d'Méiglechkeet vun Ëmsetzung vun ähnlechen Projeten op Globalen an COS betruecht.
Merci fir är Opmierksamkeet! Mir waarden op Är Froen a Wënsch an de Kommentaren.
Verzichterklärung: Dësen Artikel a meng Kommentaren dozou sinn meng Meenung an hu keng Relatioun zu der offizieller Positioun vun InterSystems Corporation.
Source: will.com