Глобалы — мечи-кладенцы для хранения данных. Разреженные массивы. Часть 3

    В прошлых частях (1, 2) мы говорили о глобалах как о деревьях, в этой мы рассмотрим глобалы как разреженные массивы.

    Разреженный массив — это разновидность массива, в котором большинство значений принимает одинаковое значение.

    На практике часто встречаются настолько огромные разреженные массивы, что нет никакого смысла занимать память одинаковыми элементами. Поэтому есть смысл разреженные массивы реализовывать так, чтобы память не расходовалась на хранение одинаковых значений.
    В некоторых языках программирования разреженные массивы входят в сам язык, например в J, MATLAB. В других языках программирования есть специальные библиотеки, которые позволяют реализовать их. Для С++ — Eigen и др.

    Глобалы — хорошие кандидаты для реализации разреженных массивов, потому что:

    1. Хранят значения только определённых узлов и не хранят значения неопределённых;
    2. Интерфейс доступа к значению узла чрезвычайно похож на то, как во многих языках программирования реализован доступ к элементу многомерного массива.

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

    3. Глобал — достаточно низкоуровневая структура для хранения данных, поэтому обладают выдающими скоростными характеристиками (от сотен тысяч до десятков миллионов транзакций в секунду в зависимости от железа, см. 1)

    Поскольку глобал — персистентная структура, то разреженные массивы делать на них имеет смысл тогда, когда заранее известно, что объёма оперативной памяти будет недостаточно.

    Одним из свойств реализаций разреженных массивов является возврат некоторого значения по-умолчанию, если обращение ведётся к неопределённой ячейке.

    Это можно реализовать, используя функцию $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-страничную книгу «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 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: представление индекса на глобалах:



    Глобал ^way используется для хранения точек полилиний (дорог, мелких рек и т.п.) и полигонов (замкнутые области: здания, леса и т.д.).

    Грубая классификация использования разреженных массивов на глобалах.


    1. Мы храним координаты неких объектов и их состояния (картирование, клеточные автоматы)
    2. Мы храним разреженные матрицы.

    Для случая 2) при запросе определённой координаты, где элементу не присвоено значение, мы должны получить значение элемента разреженного массива по умолчанию.

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


    Быстрое удаление и/или выборки кусков пространства, кратных строкам, плоскостям, кубам и т.д. Для случаев, когда используются целочисленные индексы, может оказаться полезной возможность быстрого удаления и/или выборки кусков пространства, кратных строкам, плоскостям, кубам и т.д.

    Командой Kill мы можем удалить как отдельный элемент, так и строку, и даже целую плоскость. Благодаря свойствам глобалов, это происходит очень быстро — в тысячи раз быстрее, чем поэлементное удаление.

    На рисунке показан трёхмерный массив в глобале ^a и разные виды удалений.



    Для выборки кусков пространства по известным индексам можно использовать команду Merge.

    Выборка столбца матрицы в переменную 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, так как значения по умолчанию в нём не хранятся.

    Выборка кусков пространства также может делаться через небольшую программу с использование функции $Order. Это в особенности удобно на пространствах, индексы которых неквантованы (картография).

    Заключение


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

    Когда объём данных разреженных массивов уже никак не может быть вмещён в оперативную память, а работать с ними нужно, то стоит рассмотреть возможность реализации подобных проектов на глобалах и COS.

    Спасибо за внимание! Ждём ваших вопросов и пожеланий в комментариях.

    Disclaimer: данная статья и мои комментарии к ней является моим мнением и не имеют отношения к официальной позиции корпорации InterSystems.
    InterSystems
    InterSystems IRIS: СУБД, ESB, BI, Healthcare

    Комментарии 17

      +2
      А готовые матричные операции над глобалами есть?
        0
        Пока не слышал о таких.
          0
          Окей, а как получить все заполненные значения из конкретного вектора?
            0
            С помощью команды Merge.
              0
              Она создает копию данных?
                0
                Да. Но как иначе?

                Если нужно получить все заполненные значения, то это просто копия глобала.
                  0
                  Да. Но как иначе?

                  Через прямое прямое обращение к оригинальным данным (иначе говоря, слайс/окно поверх матрицы). Операция копирования может быть недешевой.
                    0
                    Не вижу никаких проблем для прямого обращения к глобалу. Можно спокойно обойти все заполненные элементы с помощью команд $Order и $Data.
        +1
        На рисунке показан трёхмерный массив в глобале ^a и разные виды удалений.

        А как удалить «плоскость», параллельную плоcкости, проходящей через оси x-z (аналогично — x-y)? Строчку, параллельную оси x или y?
          0
          Важно при разработке правильно выбирать порядок осей, чтобы потом всё было без проблем.

          Гораздо более важная функция чем удаление — это выборка. Чтобы делать это быстро я бы создавал индексные глобалы.
            0
            Важно при разработке правильно выбирать порядок осей, чтобы потом всё было без проблем.

            А если оси равноправны?
              0
              Тогда придётся делать ещё 2 вспомогательных индексных глобала для дополнительных двух плоскостей.
          +1
          MathLab

          Вообще-то Matrix Laboratory.
          А MethLab — это Уолтер Уайт.
            +2
            Для хранения карты нашей вселенной Caché была выбрана не только из-за гибкости, но и из-за способности очень быстро сохранять поток данных, при этом попутно создавая индексные глобалы для быстрого поиска.


            А про это можно по-конкретнее и по-подробнее? Пока что я видел только очень обтекаемый пресс-релиз от Intersystems, из которого невозможно понять для чего конкретно применяется Caché. От самих участников проекта Gaia слышал про Caché только как про промежуточный буфер для данных, но никак не место хранения «карты нашей вселенной».
              –3
              глобалы не только в Кеш`э, есть(были) какие-то Мампс реализации, сие только немногим тормознутее Кеш`э, а так «насладиться» интуЭтиФно ясными Глобалами можно и без Intersystems.
                0
                Вот в этом документе даже можно посмотреть одну из реальных структур данных (стр. 3 по внутренней нумерации). Судя по документу используется ещё некая БД, а Caché используется в Java-программах, которые уточняют результат.

                Там многоитерационный процесс.

                А вот интервью с разработчиками.

                А вообще есть целая книга про Gaia, в которой рассказывается как была выбрана Caché (стр. 111-112).
                  +1
                  Вот в этом документе даже можно посмотреть одну из реальных структур данных (стр. 3 по внутренней нумерации).

                  Угу, и эта структура показывает, что ничего общего с вашим разреженным массивом тамошнее хранение не имеет. Это просто отдельные наблюдения.

              Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.

              Самое читаемое