巨大的圖形存儲問題

我想了解如何存儲具有大量數據的圖形。我正在設計一個具有巨大鐵路路線圖的應用程序。其中vertices是railway station name。我在C++中設計使用adjacency list。但是現在我發現它消耗的內存非常高，有時候我也會得到no-memory錯誤。我想知道如何存儲如此巨大的圖表，以便可以使用圖表上的algorithm。巨大的圖形存儲問題

圖被定義爲

std::map<std::string, std::set<std::string> > railway_graph;

或谷歌如何/商店實有圖形數據結構。

來源

2011-12-26 Avinash

也許某種鏈表結構？或者也許是一個稀疏的鄰接列表 - 你只是存儲邊緣。 – 2011-12-26 05:38:41

你可以發佈你現在使用的數據結構嗎？另外，大圖中有多少個節點和邊？ – 2011-12-26 05:43:03

你選擇的數據結構將需要很多多餘的內存，動態分配在堆上。 std::map和std::string將爲每個單個條目分配一塊內存（加上它自己的開銷）。 std::string也將爲該字符串分配一段內存。

這很舒服，在很多情況下完全可以。但對於大型數據結構來說並不好。

最後，你有一個映射，其中包含指針（它本身被逐一分配）給集合，它包含指向字符串的指針（它本身被逐個分配），它包含指向實際字符串緩衝區的指針。

您的實際問題是動態分配產生的開銷。在大多數平臺上，堆分配只需要一個額外的16字節內存來管理堆（儘管數字會有所不同）。

我建議，通過以下方式，你重新定義你的圖形：

// a list of node names, its index (a size_t) is used in the following data structures 
// - alternatively, you may use an std::map<int,std::string> here, to simplify the 
// "index" to "name" lookup... 
typedef size_t NodeId; 
typedef std::vector<std::string> NodeList; 

// an edge 
typedef std::pair<NodeId,NodeId> Edge; 
// or alternatively: 
struct Edge { 
    NodeId from, to; 
}; 

// a plain list of edges 
typedef std::vector<Edge> EdgeList;

，或者下面的數據結構可以爲您的使用情況更容易。它類似於你的榜樣，但更緊湊的內存中表示：

// a list of node names, its index (a size_t) is used in the following data structures 
typedef size_t NodeId; 
typedef std::vector<std::string> NodeList; 

typedef std::vector<NodeId> NodeIdList; 

// a map from one node to its adjacent nodes 
typedef std::map< NodeId, NodeIdList > Graph;

編輯：添加和使用NodeIdList ...

如果這仍然消耗了太多的內存，那麼你應該考慮關於將數據保存在磁盤上並按需加載。

如果你的節點名稱是常量，那麼你還應該考慮某種string-table，這是一種更緊湊的字符串數據在內存中的表示形式。但這是相當低級的東西。

嘗試先使用更好的數據結構！

來源

2011-12-26 06:15:17 Frunsi

將數據保存在磁盤上並按需加載。 ??這個怎麼用。 – Avinash 2011-12-26 06:45:45

@Avinash：這是一個獨立的話題。但是，您目前從哪裏獲得數據？從磁盤？從web服務？它是隨機生成的嗎？必須有一些來源 - AFAIK計算機不可能直接從您的想象中讀取數據。 – Frunsi 2011-12-26 10:34:05

但是，請不要忽略我的建議：首先嚐試使用更好的數據結構！ – Frunsi 2011-12-26 10:36:28

使用鄰接矩陣表示而不是鄰接表可以減少密集矩陣的內存分配。

由於您沒有提及系統的大小或嘗試運行的算法類型，因此很難判斷您的算法是否需要檢查不適當的內存消耗，或者實際上是否需要在整個程序中使用文件作爲間歇性的「記憶」，以使計算成爲可能。

來源

2011-12-26 05:47:19

class Node 
{ 
    string id; 
    Data data; // fetch data by ID when required from some database 
}

您可以在數據庫中存儲與每個站的數據，並在需要時通過id去取。

圖形密度定義爲D = 2|E|/(|V|(|V|-1))。您必須根據D設計數據結構。

如果你有密集圖，那麼你可以使用矩陣表示。您只需要| V | * | V |位大約。

對於稀疏圖邊緣列表表示法是好的。

來源

2011-12-26 06:15:23

使用這樣的映射和字符串會增加大量冗餘內存使用。如果使用整數索引將名稱存儲在一個向量和鄰接列表中，它應該更加緊湊。

std::vector<std::string> name; 
std::vector<std::vector<size_t> > adj_list;

來源

2011-12-26 06:16:31

在

http://redis.io/

我會建議是把你的地圖，並將其轉換爲redis的地圖，然後可以在本地文件系統堅持看看。查找速度非常快，不應該損害性能。

來源

2011-12-26 17:15:18 FUD

巨大的圖形存儲問題

回答

相關問題