Каков наилучший/самый быстрый способ построения очень большой цепи марков из данных моделирования?

Я написал программу на С++, которая имитирует определенный процесс, который я изучаю. Он выводит дискретные "состояния" каждый момент времени симуляции. Например:

a
b
c
b
c
b

будет результатом запуска симуляции с начальным условием (установленным мной или произвольно сгенерированным), а b и c - состояниями, которые система продолжает колебаться между ними.

Я хотел бы объединить многие из этих пробегов в цепь Маркова, чтобы он превратился в граф со следующими вершинами и ребрами. (Предпочтительно во время выполнения, так как сохранение вывода сначала занимает много дискового пространства.) Число между круглыми скобками указывает количество раз, когда встречалась определенная вершина или край, поэтому это также должно быть сохранено.

Vertices: a(1), b(3) and c(2).

Edges: a->b(1), b->c(2), c->b(2).

Реальные состояния содержат 112 бит информации, и я генерирую миллиарды этих переходов. Проблема в том, что я не нашел графическую библиотеку или программу для генерации цепи Маркова эффективно и быстро. Я занимаюсь с:

Редкий хэш Google для построения собственного класса графа в С++.
Neo4J (я только начинал с этого)
Библиотека лимона

Я только что закончил "Google редкий хеш-график", но он оказывается очень медленным на полпути к прогонам. Примерно через день (использование памяти превышает 20 ГБ, а не проблема сама по себе, потому что есть путь больше), она замедляется и занимает около трех недель.

У меня есть доступ к компьютерам с 12 или 16 ядрами и 256 или 512 ГБ памяти, и я чувствую, что они должны быть для работы.

Поскольку я не обученный программист, и я программирую довольно медленно, я ищу некоторую информацию, прежде чем потратить много времени на работу над еще одним несовершенным решением.

Какая будет лучшая программа/библиотека, которая может быстро принять большое количество вершин и ребер для построения цепи Маркова?
Является ли медленность результатом использования неправильных инструментов или несовершенного кодирования (что я подозреваю), или я просто пытаюсь сделать что-то, что всегда будет занимать много времени?

Надеюсь, я смог сделать свою проблему ясной. Заранее благодарим за любую мудрость или ответы.

EDIT:

Основываясь на вопросах и ответах в комментариях, я думаю, мой вопрос должен был быть: что такое подходящая библиотека быстрых матриц для С++?

Ответ 1

Вы посмотрели на boost:: numeric:: ublas? Он имеет членную разреженную матрицу, которая дает вам матрицу как доступ, но вместо построения массива NxN в памяти хранится список ребер на node.

Итак, если N - количество узлов вместо массива NxN в памяти, вы сохраняете Nx30 -avg количество ребер на node -

Однако даже если предположить, что вы можете использовать один байт, чтобы подсчитать повторяемость ребер, у вас все еще есть 600M узлов со списком из 30 ребер.

запись списка - это имя края uint32, а содержимое - не менее 1 байт. поэтому для этого списка должно быть 150 байтов. который доходит до минимума 90 ГБ в памяти. вероятно, выше, потому что в списке есть служебные данные за элемент.

Если вы можете сохранить все это в памяти без обмена данными ОС на диск, тогда нет причин, по которым он не должен работать быстро. Конечно, возможно, что упорядоченная карта выйдет из hash_map. Это зависит от реализации и используемой хеш-функции.

Наивно std::map<uint32, std::map<uint32, unint8>> Если дерево сбалансировано, длина большого дерева равна 30, а маленькая - маленькая. Поэтому доступ не должен занять возраст. Возможно, что hash_map будет работать лучше для столбцов, хотя и не определен: hash_map<uint32, std::map<uint32, unint8>> (google sparse hash map настроен на память, а не на скорость, а карта столбцов будет очень большой, что, вероятно, плохо подходит)

Наконец, вы должны рассмотреть возможность хранения этой информации на диске, а не в памяти. Фактически вы можете использовать внешнюю службу данных, такую как БД, с таблицей для каждого node (NodeId, NumOfHits) и таблицы для края (NodeId, NodeId, NumOfHits) {это представление занимает намного больше места}

Я бы попробовал что-то вроде Cassandra, которое может управлять диском против кэша памяти для вас и может легко масштабироваться для нескольких компьютеров. И вам не нужно накладные расходы на сложные модели транзакций и т.д.