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

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

Ретка низа е тип на низа во која повеќето од вредностите ја земаат истата вредност.

Во пракса, ретките низи често се толку огромни што нема смисла да се окупира меморијата со идентични елементи. Затоа, има смисла да се имплементираат ретки низи на таков начин што меморијата не се троши за складирање на идентични вредности.
Во некои програмски јазици, ретки низи се вклучени во самиот јазик, на пример во Ј, MATLAB. Другите програмски јазици имаат специјални библиотеки кои ви дозволуваат да ги имплементирате. За C++ - Ејген итн

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

1. Тие ги чуваат вредностите на само одредени јазли и не ги складираат вредностите на недефинираните;
2. Интерфејсот за пристап до вредноста на јазолот е екстремно сличен на тоа колку програмски јазици спроведуваат пристап до елемент од повеќедимензионална низа.

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

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

Бидејќи глобалната е постојана структура, има смисла да се создаваат ретки низи на нив кога однапред се знае дека количината на RAM меморија нема да биде доволна.

Едно од својствата на имплементациите на ретка низа е да се врати некоја стандардна вредност ако се направи пристап до недефинирана ќелија.

Ова може да се имплементира со помош на функцијата $GET во 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 * максимална големина на линијата), односно, уште поекономичен начин за складирање на такви матрици се битните низи, бидејќи нивната имплементација ги оптимизира големите празнини на посебен начин.

Манипулациите со низи на битови се вршат од функцијата $BIT.

; установка бита
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
...

Каде се b, l, d галактички координати географска ширина, должина и растојание до Сонцето.

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

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

Ако се вратиме на Земјата, тогаш беа создадени картографски проекти на глобални OpenStreetMap XAPI и дел од 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: претставување на индекс на глобални:

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

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

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

Она што е интересно за променливата Column е тоа што имаме и ретка низа, до која исто така мора да се пристапи преку $GET, бидејќи стандардните вредности не се зачувани во него.

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

Заклучок

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

Кога обемот на податоци од ретки низи повеќе не може да се вклопи во RAM меморијата, но треба да работите со нив, тогаш вреди да се разгледа можноста за спроведување слични проекти на глобални и COS.

Ви благодариме за вниманието! Ги очекуваме вашите прашања и желби во коментарите.

Општи услови: Оваа статија и моите коментари за неа се мое мислење и немаат врска со официјалниот став на InterSystems Corporation.

Извор: www.habr.com