У мінулых частках (, ) мы казалі аб глабалах як аб дрэвах, у гэтай мы разгледзім глабалы як разрэджаныя масівы.
- Гэта разнавіднасць масіва, у якім большасць значэнняў прымае аднолькавае значэнне.
На практыцы часта сустракаюцца настолькі вялізныя разрэджаныя масівы, што няма ніякага сэнсу займаць памяць аднолькавымі элементамі. Таму ёсць сэнс разрэджаныя масівы рэалізоўваць так, каб памяць не расходавалася на захоўванне аднолькавых значэнняў.
У некаторых мовах праграмавання разрэджаныя масівы ўваходзяць у саму мову, , . У іншых мовах праграмавання ёсць спецыяльныя бібліятэкі, якія дазваляюць рэалізаваць іх. Для З++ - і інш
Глобалы - добрыя кандыдаты для рэалізацыі разрэджаных масіваў, таму што:
- Захоўваюць значэння толькі пэўных вузлоў і не захоўваюць значэння нявызначаных;
- Інтэрфейс доступу да значэння вузла надзвычай падобны на тое, як у многіх мовах праграмавання рэалізаваны доступ да элемента шматмернага масіва.
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") = "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 - гэта і адлегласць да Сонца.
Гнуткая структура глабалаў дазваляе захаваць любыя патрэбныя характарыстыкі зорак і планет, бо базы на глабалах бяссхемныя (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