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