Глобалите са съкровища мечове за съхранение на данни. Разредени масиви. Част 3

В предишните части1, 2) говорихме за глобали като дървета, в този ще разглеждаме глобалите като редки масиви.

Оскъден масив е вид масив, в който повечето от стойностите приемат една и съща стойност.

На практика често има толкова огромни редки масиви, че няма смисъл да се заема паметта с едни и същи елементи. Следователно има смисъл да се прилагат редки масиви по такъв начин, че паметта да не се изразходва за съхраняване на идентични стойности.
В някои езици за програмиране редките масиви са част от самия език, например в Дж, MATLAB. Други езици за програмиране имат специални библиотеки, които ви позволяват да ги внедрявате. За C++ - Собствен и др.

Глобалите са добри кандидати за прилагане на редки масиви, защото:

1. Те съхраняват стойностите само на дефинирани възли и не съхраняват стойностите на недефинирани;
2. Интерфейсът за достъп до стойността на възел е изключително подобен на това колко езици за програмиране реализират достъп до елемент от многоизмерен масив.

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

3. Global е структура на сравнително ниско ниво за съхранение на данни, следователно те имат изключителни характеристики на скоростта (от стотици хиляди до десетки милиони транзакции в секунда, в зависимост от хардуера, вижте по-долу). 1)

Тъй като глобалът е постоянна структура, има смисъл да се правят редки масиви върху тях, когато предварително се знае, че количеството RAM няма да е достатъчно.

Едно от свойствата на реализациите на редки масиви е да връщат някаква стойност по подразбиране, ако достъпът е до недефинирана клетка.

Това може да стане с помощта на функцията $GET в COS. В този пример се разглежда триизмерен масив.

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)

Таблица за прескачане на State Machine

Тъй като графиката на прехода на краен автомат е обикновена графика, тогава таблицата на прехода на краен автомат е същата матрица на съседство, която беше обсъдена по-горе.

Клетъчни автомати

Най-известният клетъчен автомат игра "живот", който поради своите правила (когато една клетка има много съседи, тя умира) е разреден масив.

Стивън Волфрам, вярва, че клетъчните автомати са нова област на науката. През 2002 г. той публикува Нов вид наука, книга от 1280 страници, в която аргументира широко, че напредъкът в клетъчните автомати не е изолиран, а е много стабилен и от голямо значение за всички области на науката.

Доказано е, че всеки алгоритъм, който може да бъде реализиран на компютър, може да бъде реализиран с помощта на клетъчен автомат. Клетъчните автомати се използват за моделиране на динамични среди и системи, за решаване на алгоритмични проблеми и за други цели.

Ако имаме огромно поле и трябва да запишем всички междинни състояния на клетъчен автомат, тогава е съвсем разумно да използваме глобали.

Картография

Първото нещо, което ми идва на ум, когато става въпрос за използване на разредени масиви, са задачите за картографиране.

По правило на картите има много празно място. Ако картата е представена като големи пиксели, тогава 71% от пикселите на Земята ще бъдат заети от океана. Разреден масив. И ако приложите само произведенията на човешките ръце, тогава ще има повече от 95% празно пространство.

Разбира се, никой не съхранява карти като растерни масиви, използва се векторно представяне.
Но какво представляват векторните карти? Това е един вид рамка и полилинии и полигони, състоящи се от точки.
Всъщност база данни от точки и връзки между тях.

Една от най-амбициозните мисии за картографиране е мисията на телескопа Gaia за картографиране на нашата галактика. Образно казано, нашата галактика, както и цялата вселена, е непрекъснат рядък масив: огромни пространства от пустота, в които има редки малки точки - звезди. Празно място 99,999999…….%. За съхраняване на картата на нашата галактика беше избрана база данни за глобали - Caché.

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

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

Където са b, l, d галактически координати ширина, дължина и разстояние от слънцето.

Гъвкавата структура на глобалите ви позволява да запазите всякакви желани характеристики на звезди и планети, тъй като базите на глобалите са без схеми.

За да съхрани карта на нашата вселена, Caché беше избран не само поради своята гъвкавост, но и поради способността му да съхранява поток от данни много бързо, като същевременно създава глобални индекси по пътя за бързо търсене.

Ако се върнем на Земята, тогава картографските проекти са създадени върху глобали OpenStreetMap XAPI и разклонение на OpenStreetMap - FOSM.

Наскоро на Хакатон Caché бяха внедрени геопространствени индекси Geospatial. Очакваме статии с подробности за изпълнението от авторите.

Внедряване на пространствени индекси върху глобалното в OpenStreetMap XAPI

Снимки, взети от тази презентация.

Цялото земно кълбо е разделено на квадрати, след това подквадрати, а подквадратите на подподквадрати и т.н. Като цяло получаваме йерархична структура за съхраняване на създадените глобали.

По всяко време можем почти моментално да поискаме желания квадрат или да го изчистим, докато всички подквадрати също ще бъдат върнати или изчистени.

Такава схема върху глобали може да се приложи по няколко начина.

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

Вариант 2:

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

И в двата случая не е трудно да поискате точки, разположени в квадрат на произволно ниво на COS/M. Ще бъде малко по-лесно да изчистите квадратни парчета пространство от всяко ниво в първата опция, но това рядко е необходимо.

Пример за един от квадратите на по-ниско ниво:

И ето някои глобални елементи от проекта XAPI: представяне на индекс на глобални елементи:

глобален ^ начин използвани за съхраняване на точки полилинии (пътища, плитки реки и др.) и полигони (затворени зони: сгради, гори и др.).

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

1. Ние съхраняваме координатите на определени обекти и техните състояния (картографиране, клетъчни автомати)
2. Ние съхраняваме разредени матрици.

За случай 2), когато изискваме конкретна координата, където на елемента не е присвоена стойност, трябва да получим стойността на елемента от редкия масив по подразбиране.

Бонуси, които получаваме, когато съхраняваме многомерни матрици в глобали

Бързо изтриване и/или селекция на парчета пространство, кратни низове, равнини, кубчета и др. За случаите, когато се използват целочислени индекси, може да бъде полезно да можете бързо да премахвате и/или избирате части от пространство, които са кратни на низове, равнини, кубове и т.н.

Екип Убий можем да изтрием както отделен елемент, така и линия и дори цяла равнина. Благодарение на свойствата на глобалните, това е много бързо - хиляди пъти по-бързо от изтриването елемент по елемент.

Фигурата показва триизмерен масив в глобалното ^a и различни видове изтривания.

За да изберете части от пространството по известни индекси, можете да използвате командата Обединяване.

Избиране на колона на матрица в променливата 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

Заключение:

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

Това, което е интересно в променливата Column, ние също получихме разреден масив, който също трябва да бъде достъпен чрез $GET, тъй като стойностите по подразбиране не се съхраняват в него.

Вземането на проби от парчета пространство може да се направи и чрез малка програма, използваща функцията $Поръчка. Това е особено удобно за пространства, чиито индекси не са квантувани (картография).

Заключение

Настоящето време поставя нови амбициозни задачи. Графите могат да имат милиарди върхове, картите могат да имат милиарди точки и някой може дори да иска да управлява своя собствена вселена върху клетъчни автомати (1, 2).

Когато обемът на данните на разредените масиви вече не може да се побере в RAM и трябва да работите с тях, тогава си струва да обмислите възможността за внедряване на такива проекти на глобали и COS.

Благодаря за вниманието! Очакваме вашите въпроси и желания в коментарите.

Отказ от отговорност: Тази статия и моите коментари към нея са мое мнение и не представляват официалната позиция на InterSystems Corporation.

Източник: www.habr.com