viz*_*z12 6 c++ graph vector bigdata
我正在处理一个包含5亿个节点的非常大的图,平均节点数是100.所以它是一种稀疏图.我还必须存储每个边缘的重量.我目前正在使用两个向量,如下所示
// V could be 100 million
vector<int> *AdjList = new vector<int>[V];
vector<int> *Weight = new vector<int>[V];
使用vector的vector似乎不被有效利用空间.它需要超过400GB的存储空间.有没有更好的节省空间的方法将这个大图存储在内存中？有关使用任何c ++库的建议吗？
初步评论
您可以考虑使用向量向量而不是使用动态内存分配:
vector<vector<int>> AdjList(V);
无论如何,你vector<int>的邻接列表中的V会有所不同.每个向量都需要一些空间开销来管理其项目的大小和位置.不幸的是,通过将权重保持在不同的向量/数组中,您可以将此开销(以及添加新链接时的相关隐藏内存管理)加倍.
那么为什么不重新组合邻接列表和权重呢？
struct Link {
int target; // node number that was in adj list. Hope none is negative!!
int weight;
};
vector<vector<Link>> AdjList(V);
结构稀疏吗？
如果绝大多数节点都有某种链接,那就很好了.
如果相反,许多节点没有传出链接(或者如果您有大量未使用的节点ID范围),那么您可以考虑:
map<int, vector<Link>> AdjList;
该地图是一个关联数组.只有具有传出链接的节点的向量.顺便说一句,您可以使用您想要的任何编号方案,甚至是负数.
你甚至可以更进一步,并使用双地图.第一个映射为您提供传出节点.第二个映射将目标节点映射到权重:
map<int, map<int, int>> Oulala;
但这可能会带来更大的内存密集性.
大卷？
map并vector使用默认分配器动态管理内存.但是你有很多预定大小的小物件.所以你可以考虑使用自己的分配器.这可以显着优化内存管理开销.
此外,如果使用向量,当您加载新节点的邻接列表时,立即保留向量的大小(如果您知道)可能是有效的.这可以避免对载体的增长进行几次连续的重新分配.有数百万个节点,这可能非常昂贵.
图书馆？
搜索第三方库超出了SO的范围.但是,如果上述提示不充分,您可以考虑使用现有的图库,例如:
还有一些其他图形库,但许多图像似乎不再维护或不适用于大卷.
您应该将该图实现为二元决策图数据结构。
简而言之，其思想是，通过使用图的特征函数，可以将图表示为二元函数。
使用特征函数将图编码为二元函数的方法有多种。在我在帖子末尾发布的文章和视频中，有一种方法可以做到这一点。
BDD 以紧凑的方式对二进制函数进行快速运算编码。这可能是宇宙中最强大的数据结构。
BDD 的思想与trie几乎相同，但是在每个节点，我们不分派下一个输入的函数，而是每个节点都有 as attribute X，它表示变量的索引，如果函数F(..X=true..)是true，继续在该节点的高分支上到达叶子节点true，如果F(..X=false..)为 true，则继续在低分支上向下到达代表 true 的叶子节点。这称为布尔函数的香农展开（通过使用相同的展开公式也是使用多路复用器计算布尔函数的硬件设计的一种方法）。
一般来说，对于函数为真的输入值 X_i 的每个可能组合，我们有一个从根节点到叶子的唯一分支true，在输入变量的函数中的每个节点处分支Xi（我们在低或高方向上分支）是 Xi 值 true 或 false 的函数）。同一个图可以用来保留多个功能（每个节点是一个不同的功能）。
有 2 个优化可将二元决策树转换为二元决策图，从而使其紧凑。优化的思想与有限自动机的最小化算法的优化相同。与自动机的情况相同，最小 BDD 对于该函数是唯一的（因此要查看两个任意函数是否相同，只需将它们转换为 BDD 并查看代表一个函数的节点是否与根相同）其他函数的节点（比较 2 个指针值的复杂性 O(1)（恒定时间））。
一种优化是，如果一个节点的所有边都与其他节点位于相同的物理节点中，则我们将这两个节点统一为一个节点（这可以在创建时通过保留所有创建的节点的哈希表来完成）。
其他优化表示，如果变量 X 的节点的低沿和高沿进入变量 Y 的同一物理节点，则 X 节点消失，因为该函数具有相同的 F(...X=true. ..)=F(...X=假...)。
有数千篇关于 BDD 及其衍生物的文章（改变我们得到的每个节点的调度解释，例如 ZDD，用于无序集的紧凑表示）。有关该主题的典型文章是哪些图可以通过 BDD 有效表示？作者：C. Dong P. Molitor。
了解 BDD 的基础知识后，如果您有耐心进行较长的演示，该视频非常好，它总结了如何将图编码为 BDD。
BDD 是当今专业软件在需要管理数百万个节点时所做的工作。