Глобали су ризнице за складиштење података. Ретки низови. део 3

У претходним деловима (1, 2) говорили смо о глобалима као стаблима, у овом ћемо глобале посматрати као ретке низове.

Спарсе Арраи је тип низа у којем већина вредности узима исту вредност.

У пракси, ретки низови су често толико огромни да нема смисла заузимати меморију идентичним елементима. Због тога има смисла имплементирати ретке низове на такав начин да се меморија не троши на чување идентичних вредности.
У неким програмским језицима, ретки низови су укључени у сам језик, на пример у Ј, Матлаб. Други програмски језици имају посебне библиотеке које вам омогућавају да их имплементирате. За Ц++ - Еиген итд

Глобални су добри кандидати за имплементацију ретких низова јер:

1. Они чувају вредности само одређених чворова и не чувају вредности недефинисаних;
2. Интерфејс за приступ вредности чвора је изузетно сличан томе колико програмских језика имплементира приступ вишедимензионалном елементу низа.

   Set ^a(1, 2, 3)=5
   Write ^a(1, 2, 3)

3. Глобал је структура прилично ниског нивоа за складиштење података, стога има изванредне карактеристике брзине (од стотина хиљада до десетина милиона трансакција у секунди, у зависности од хардвера, погледајте доле). 1)

Пошто је глобал трајна структура, има смисла креирати ретке низове на њима када се унапред зна да количина РАМ-а неће бити довољна.

Једно од својстава имплементације ретког низа је враћање неке подразумеване вредности ако се приступи недефинисаној ћелији.

Ово се може имплементирати помоћу функције $ГЕТ у ЦОС. Овај пример разматра 3-димензионални низ.

SET a = $GET(^a(x,y,z), defValue)

Који задаци захтевају ретке низове и како глобали могу помоћи?

Матрица суседности (повезивости).

Такве матрице користи се за представљање графикона:

Очигледно, што је већи график, то ће више нула бити у матрици. Ако, на пример, узмемо граф друштвене мреже и представимо га у облику сличне матрице, онда ће се он скоро у потпуности састојати од нула, тј. биће ретки низ.

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
....

У овом примеру штедимо глобално ^m матрица повезивања, као и број ивица на сваком чвору (ко је с ким пријатељ и број пријатеља).

Ако број елемената на графикону није већи од 29 милиона (овај број се узима као производ 8 * максимална величина линије), односно још економичнији начин складиштења оваквих матрица су бит стрингови, пошто њихова имплементација на посебан начин оптимизује велике празнине.

Манипулације са стринговима битова врши функција $БИТ.

; установка бита
SET $BIT(rowID, positionID) = 1
; получение бита
Write $BIT(rowID, positionID)

Табела прелаза државног строја

Пошто је прелазни граф коначног аутомата обичан граф, онда је табела прелаза коначног аутомата иста матрица суседности о којој је горе дискутовано.

Ћелијски аутомати

Најпознатији ћелијски аутомат је игра "Живот", који је по својим правилима (када ћелија има много суседа, она умире) ретки низ.

Стивен Волфрам верује да су ћелијски аутомати нова област науке. Године 2002. објавио је књигу од 1280 страница, Нова врста науке, у којој широко тврди да напредак у ћелијским аутоматима није изолован, већ је трајан и има велике импликације за све области науке.

Доказано је да се било који алгоритам који се може извршити на рачунару може имплементирати помоћу ћелијског аутомата. Ћелијски аутомати се користе за моделирање динамичких окружења и система, за решавање алгоритамских проблема и за друге сврхе.

Ако имамо огромно поље и треба да забележимо сва међустања ћелијског аутомата, онда има смисла користити глобалне вредности.

картографија

Прва ствар која ми пада на памет када је у питању коришћење ретких низова су задаци мапирања.

По правилу, на картама има пуно празног простора. Ако је мапа представљена као велики пиксели, онда ће 71% Земљиних пиксела бити заузето океаном. Спарсе арраи. А ако примените само дела људских руку, онда ће празан простор бити више од 95%.

Наравно, нико не чува карте у облику растерских низова;
Али шта су векторске карте? Ово је нека врста оквира и полилинија и полигона који се састоје од тачака.
У суштини база података о тачкама и везама између њих.

Једна од најамбициознијих мисија мапирања је мисија телескопа Гаиа за мапирање наше галаксије. Сликовито речено, наша галаксија, као и цео универзум, је непрекидан ретки низ: огромни простори празнине у којима се налазе ретке мале тачке – звезде. Празан простор је 99,999999…….%. За чување мапе наше галаксије изабрана је глобална база података - Цацхе.

Не знам тачну структуру глобала у овом пројекту, могу претпоставити да је нешто слично:

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
...

Где су б, л, д галактичке координате географска ширина, дужина и удаљености до Сунца.

Флексибилна структура глобала вам омогућава да сачувате све неопходне карактеристике звезда и планета, пошто су базе на глобалима без шема.

За складиштење мапе нашег универзума, Цацхе је изабран не само због своје флексибилности, већ и због своје способности да веома брзо складишти ток података, док истовремено креира индексе глобала за брзу претрагу.

Ако се вратимо на Земљу, онда су на глобалима креирани картографски пројекти ОпенСтреетМап КСАПИ и рачва ОпенСтреетМап-а - ФОСМ.

Недавно на хацкатхон Цацхе имплементирани су геопросторни индекси Просторни. Чекамо чланак од аутора са детаљима имплементације.

Имплементација просторних индекса на глобалном у ОпенСтреетМап КСАПИ

Слике преузете из ову презентацију.

Цела земаљска кугла је подељена на квадрате, затим на подквадрате, а потквадрате на под-подквадрате и тако даље. Уопштено говорећи, добијамо хијерархијску структуру за чување тога који су глобали креирани.

У сваком тренутку можемо скоро тренутно да затражимо жељени квадрат или га обришемо, а сви подквадрати ће такође бити враћени или очишћени.

Слична шема на глобалима може се имплементирати на неколико начина.

Опција КСНУМКС:

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ВторойТочки
...

Опција КСНУМКС:

Set ^m('abacdabcdabacdabcda', 1) = idПервойТочки
Set ^m('abacdabcdabacdabcda', 2) = idВторойТочки
...

У оба случаја, није тешко користити ЦОС/М да бисте захтевали тачке које се налазе у квадрату било ког нивоа. У првој опцији биће нешто лакше очистити квадратне делове простора на било ком нивоу, али то је ретко потребно.

Пример једног од квадрата нижег нивоа:

А ево неколико глобала из КСАПИ пројекта: представљање индекса на глобалима:

глобално ^ начин користи се за чување поена полилиније (путеви, реке итд.) и полигони (затворена подручја: зграде, шуме итд.).

Груба класификација употребе ретких низова на глобалима.

1. Чувамо координате одређених објеката и њихова стања (мапирање, ћелијски аутомати)
2. Чувамо ретке матрице.

За случај 2) када захтевамо одређену координату где елементу није додељена вредност, морамо добити вредност подразумеваног елемента разређеног низа.

Бонуси које добијамо када чувамо вишедимензионалне матрице у глобалима

Брзо уклоните и/или изаберите делове простора који су вишеструки редовима, равнима, коцкама итд. За случајеве у којима се користе целобројни индекси, може бити корисна могућност брзог уклањања и/или преузимања делова простора који су вишеструки од редова, равни, коцки итд.

тим убити можемо избрисати или један елемент или ред, или чак читаву раван. Захваљујући својствима глобала, ово се дешава веома брзо - хиљаде пута брже од уклањања елемент по елемент.

На слици је приказан тродимензионални низ у глобалу ^a и различите врсте брисања.

Да бисте изабрали делове простора користећи познате индексе, можете користити команду Стопити.

Избор колоне матрице у променљивој Цолумн:

; Зададим трёхмерный разреженный массив 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

Закључак:

Column(0)=1
Column(2)=1

Оно што је интересантно у вези са променљивом Цолумн је да имамо и ретки низ, коме се такође мора приступити преко $ГЕТ, пошто подразумеване вредности нису ускладиштене у њему.

Одабир делова простора се такође може обавити кроз мали програм помоћу функције $Ордер. Ово је посебно погодно на просторима чији индекси нису квантизовани (картографија).

Закључак

Садашње време поставља нове амбициозне задатке. Графови могу бити састављени од милијарди врхова, мапе сачињене од милијарди тачака, а неки би чак желели да покрећу сопствени универзум на ћелијским аутоматима (1, 2).

Када обим података из ретких низова више не може да стане у РАМ, али морате да радите са њима, онда је вредно размислити о могућности имплементације сличних пројеката на глобалима и ЦОС-у.

Хвала на пажњи! Чекамо ваша питања и жеље у коментарима.

Одрицање од одговорности: Овај чланак и моји коментари на њега су моје мишљење и немају никакве везе са званичним ставом ИнтерСистемс Цорпоратион.

Извор: ввв.хабр.цом