В предишните части (, ) говорихме за глобалите като дървета, в тази част ще разгледаме глобалите като разредени масиви.
— това е разновидност на масив, в която повечето стойности приемат една и съща стойност.
В практиката често се срещат толкова огромни разредени масиви, че няма смисъл да се заема памет с еднакви елементи. Затова е разумно разредените масиви да се реализират по начин, който да не харчи памет за съхранение на еднакви стойности.
В някои езици за програмиране разредените масиви са част от езика, , . В други езици за програмиране има специални библиотеки, които позволяват тяхната реализация. За C++ — и др.
Глобалите са добри кандидати за реализация на разредени масиви, защото:
- Съхраняват стойности само на определени възли и не съхраняват стойности на неопределени;
- Интерфейсът за достъп до стойността на възел е изключително подобен на начина, по който в много езици за програмиране се реализира достъп до елемент на многомерен масив.
Set ^a(1, 2, 3)=5 Write ^a(1, 2, 3) - Глобал — достатъчно нискоуровнева структура за съхранение на данни, следователно притежава изключителни скоростни характеристики (от стотици хиляди до десетки милиони транзакции в секунда в зависимост от хардуера, виж. )
Тъй като глобалът е персистентна структура, разредените масиви е разумно да се правят на тях, когато предварително се знае, че обемът на оперативната памет ще бъде недостатъчен.
Едно от свойствата на реализациите на разредени масиви е връщането на определена стойност по подразбиране, ако се прави достъп до неопределена клетка.
Това може да се реализира, използвайки функцията в COS. В този пример е разгледан 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-странична книга „A New Kind of Science“, в която широко аргументира, че постиженията в областта на клетъчните автомати не са изолирани, а по-скоро стабилни и имат голямо значение за всички области на науката.
Доказано е, че всеки алгоритъм, който може да се изпълни на компютър, може да бъде реализиран посредством клетъчен автомат. Клетъчните автомати се използват за моделиране на динамични среди и системи, за решаване на алгоритмични задачи и за други цели.
Ако имаме огромно поле и трябва да запишем всички междинни състояния на клетъчния автомат, напълно разумно е да използваме глобалите.
Картография
Първото, което ми идва на ум, когато става дума за използване на разредени масиви, е картографските задачи.
Като правило на картите има много празно пространство. Ако картата се представя под формата на големи пиксели, то 71% от пикселите на Земята ще бъдат заети от океана. Разреден масив. А ако рисуваме само произведения на човешкия труд, то празното пространство ще бъде над 95%.
Разбира се, никой не съхранява картите под формата на растерни масиви, използва се векторно представяне.
Но какво представляват векторните карти? Това е нещо като рамка, състояща се от точки, полилинии и полигони.
Всъщност, база данни от точки и връзки между тях.
Една от най-амбициозните задачи в картографията е мисията за картографиране на нашата галактика с телескопа Гая. Образно казано, нашата галактика, както и вселената, представлява сплошен разреден масив: огромни пространства празнота, в които се намират редки малки точки — звезди. Празното пространство е 99,999999…….%. За съхранение на картата на нашата галактика беше избрана база данни на глобалите — Caché.
Не знам точната структура на глобалите в този проект, но мога да предположа, че е нещо подобно на:
Set ^galaxy(b, l, d) = 1; Номер на звездата по каталога, ако има
Set ^galaxy(b, l, d, "name") = "Слънце"
Set ^galaxy(b, l, d, "type") = "нормална"; варианти blackhole, quasar, red_dwarf и т.н.
Set ^galaxy(b, l, d, "weight") = 14E50
Set ^galaxy(b, l, d, "planetes") = 7
Set ^galaxy(b, l, d, "planetes", 1) = "Меркурий"
Set ^galaxy(b, l, d, "planetes", 1, weight) = 1E20
...
Където b, l, d — това са и разстояние до Слънцето.
Гъвкавата структура на глобалите позволява да се запазят всякакви нужни характеристики на звездите и планетите, тъй като базите на глобалите са безсхемни (scheme-less).
За съхранение на картата на нашата вселена, Caché беше избрана не само заради гъвкавостта си, но и за способността много бързо да съхранява поток от данни, създавайки индексирани глобали за бързо търсене.
Ако обаче се върнем на Земята, то на глобалите бяха създадени картографски проекти и форк на OpenStreetMap — .
Напоследък на бяха реализирани геопространствени индекси . Очакваме от авторите на статията детайли относно реализацията.
Реализацията на пространствени индекси на глобала в 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: представяне на индексите на глобалите:
Глобал ^way се използва за съхранение на точки (пътища, малки реки и т.н.) и полигони (затворени области: сгради, гори и т.д.).
Груба класификация на използването на разредени масиви в глобалите.
- Съхраняваме координатите на определени обекти и техните състояния (картографиране, клетъчни автомати)
- Съхраняваме разредени матрици.
За случай 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 също получаваме разреден масив, до който трябва да се достъпва също чрез , тъй като стойностите по подразбиране в него не се съхраняват.
Извличането на парчета пространство също може да се извършва чрез малка програма, използваща функцията . Това е особено удобно в пространствата, чийто индекси са неквантизирани (картография).
Заключение
Настоящето поставя нови амбициозни предизвикателства. Графите могат да се състоят от милиарди върхове, картите от милиарди точки, а някой дори може да пожелае да стартира собствена вселена на клетъчни автомати (, ).
Когато обемът на данните в разредени масиви вече не може да бъде приет в оперативната памет, а работата с тях е необходимо, тогава си струва да се разгледа реализацията на подобни проекти на глобали и COS.
Благодарим ви за вниманието! Очакваме вашите въпроси и желания в коментарите.
Отказ: тази статия и моите коментари към нея са мое мнение и нямат отношение към официалната позиция на корпорацията InterSystems.
Източник: habr.com
