Эффективная интерпретация графа C++

Question

У меня есть эта проблема: У меня есть график с узлами, значение которых составляет от 1 до 200 М. График имеет 200M узлов и не более 300M переходов. Переходы с символами символов (между 'a' и 'z') , поэтому я держу их всех в этом: map < char, int> переходы [200000000]; , но это очень дорого. в переходах [i] i - единственное значение состояния, а переходы [i] [c], где c - символ символа, - это состояние, которое мы переходим от «i» с char «c» Однако если У меня 8M состояний, он занимает 1,6 ГБ памяти. И у меня есть ограничение на 8 ГБ памяти для этого, чтобы работать с 200М узлами. Не могли бы вы дать мне совет для чего-то более эффективного? У меня также есть 2 x int массива с размером 200 миллионов. Который должен также вписаться в этот 8-гигабайтный баран. Он принимает как баран :) 1,6 Гб

Answer 1

Кажется, используя

std::vector<std::pair<std::pair<int, char>, int>> edges; 

будет более эффективным: вступление ((f, x), t) будет представлять собой переход от узла к узлу ft с символом z. Вы сохранили бы этот вектор и отсортировали бы его, используя std::lower_bound(edges.begin(), edges.end(), predicate) с подходящим предикатом. Объем памяти, вероятно, будет примерно 3 * sizeof(int) * e, где e - количество ребер.