巨大的图形存储问题

Question

我想了解如何存储大数据图形。我正在设计一个应用程序，其中包含一个巨大的铁路路线网络图。其中vertices是railway station name。我使用C++中的adjacency list进行设计。但现在我发现它消耗非常高的内存，并且有时还会出现no-memory错误。我想知道如何存储如此庞大的图形，以便可以对其进行algorithm操作。

图形定义为： std::map<std::string, std::set<std::string> > railway_graph; 或者说，谷歌/ Facebook 如何存储他们的图形数据结构。

- Avinash

---

也许是某种链表结构？或者是一种稀疏邻接表 - 只存储存在的边。 - Utkarsh Sinha

你能发布一下你现在使用的数据结构吗？另外，一个大图中有多少个节点和边？ - Bowie Owens

Answer 1

使用邻接矩阵表示法代替邻接表表示法可以减少稠密矩阵的内存分配。

由于您没有提到系统的大小或尝试运行的算法类型，因此很难判断您的算法是否需要检查不适当的内存消耗，或者是否实际上需要在程序中使用文件作为临时“内存”，以便进行计算。

- Zéychin

Answer 2

你选择的数据结构将需要大量冗余内存，在堆上动态分配。 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...

如果这仍然消耗太多内存，那么您应该考虑将数据保存在磁盘上，并按需加载。

如果您的节点名称是恒定不变的，则还应考虑某种字符串表，一种更紧凑的内存中字符串数据表示。但这是相当低级的东西。

首先尝试使用更好的数据结构！

- Frunsi

---

将数据保存在磁盘上，并按需加载。这是如何工作的？ - Avinash

@Avinash：这是一个独立的话题。但是，你目前从哪里获取数据？从磁盘？从Web服务？还是随机生成的？肯定有某个来源 - 据我所知，目前还不可能让计算机直接从你的想象中读取数据。 - Frunsi

然而，请不要忽略我的建议：首先尝试使用更好的数据结构！ - Frunsi

Answer 3

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|位。

对于稀疏图，边缘列表表示法很好。

- Pratik Deoghare

Answer 4

使用map和string这样的数据结构会增加很多冗余的内存使用。如果你将名称存储在一个向量中，并且仅使用整数索引来存储邻接列表，它应该会更加紧凑。

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

- Bowie Owens

Answer 5

请看一下

http://redis.io/

我建议的是将您的map转换为Redis中的一张表，然后可以将其持久化在本地文件系统中。查询速度非常快，不会对性能造成太大影响。

- FUD