효과적인 그래프 해석 C++

Question

나는이 문제를 가지고있다 : 나는 값이 1에서 200M 사이 인 노드를 가진 그래프를 가지고있다. 그리고이 그래프는 200M 개의 노드와 300M 이상의 전환을 가지고 있습니다. 전환은 숯 기호 ('a'와 'z'사이) 인 이므로 모두 다음 내용으로 유지하십시오. map < char, int> transitions [200000000]; 하지만 매우 비용이 많이 든다. 전환 중 [i] i는 상태의 고유 값이고 전환 [i] [c] (여기서 c는 char 기호 임)는 char "c"로 "i"에서 이동하는 상태입니다 그러나 나는 8M 주가 있는데, 1.6GB 램이 필요합니다. 그리고 나는 200M 노드와 함께 작동하기 위해 8GB RAM의 한계를 가지고 있습니다. 좀 더 효과적인 것에 대한 조언을 해 주시겠습니까? 나는 또한 200 만 크기의 2 x int 배열을 가지고있다. 이 8 기가 바이트 숫양에도 적합해야합니다. 그것은 더 효과적 일 것

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

을 사용, 1.6GB 램 :

Answer 1

것 같다처럼 취 항목 ((f, x), t) 심볼 z와 t을 노드에서 노드 f의 전환을 나타내는 것입니다. 이 벡터를 정렬 된 상태로 유지하고 적합한 술어를 사용하여 std::lower_bound(edges.begin(), edges.end(), predicate)을 사용하여 전환을 찾습니다. 메모리 풋 프린트는 대략 3 * sizeof(int) * e 일 수 있습니다. 여기서 e은 모서리 수입니다.