有效的圖形解釋C++

Question

我有這個問題： 我有一個圖節點，其值在1和200M之間。圖中有200M節點，不超過300M的轉換。轉換使用char符號（'a'和'z'之間） 因此我將它們全部保留在此： map < char，int>轉換[200000000]; 但它是非常不便的。 in transitions [i] i是狀態的唯一值，並且transition [i] [c]（其中c是char符號）是我們從「i」轉到char「c」的狀態。但是，如果我有8M的狀態，它需要1.6GB的內存。我有一個8 GB的RAM的限制，這個與200M節點一起工作。 你能給我一個更有效的建議嗎？我也有2個200萬大小的int數組。這也應該適合這些8GB的內存。它需要像1.6GB RAM :)

Answer 1

看來，使用

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

會更有效：入門((f, x), t)將是從節點f過渡與符號z節點t。你會保持這個向量的排序，並使用std::lower_bound(edges.begin(), edges.end(), predicate)和適當的謂詞來定位轉換。內存佔用可能大致爲3 * sizeof(int) * e，其中e是邊數。