如何高效合并多图，按组件ID对Edge的value值求和？

问题背景 #

现有两个Graph结构，均包含Block、Node、Edge三类组件：

• 每个Block包含专属的Node列表，每个Node包含若干Edge
• Block、Node、Edge的ID均为递增序列，Edge带有浮点型value值

示例结构 #

Graph 1：

Graph1 -> Block[id=1] -> Node[id=1] -> Edge[id=1,value=5]
Graph1 -> Block[id=2] -> Node[id=2] -> Edge[id=2,value=7]

（含2个Block，每个Block内有1个Node及1个Edge）

Graph 2：

Graph2 -> Block[id=1] -> Node[id=1] -> Edge[id=1,value=15]
Graph2 -> Block[id=2] -> Node[id=2] -> Edge[id=2,value=17]

任务要求 #

快速对两图中ID为1、2的Edge的value值求和，生成结果图：

ResultGraph -> Block[id=1] -> Node[id=1] -> Edge[id=1,value=20]
ResultGraph -> Block[id=2] -> Node[id=2] -> Edge[id=2,value=24]

当前仅能想到逐层遍历图的求和方法，寻求更优实现方案及适用算法。

优化方案与算法 #

1. 哈希映射快速定位（O(1)查询复杂度） #

跳过逐层遍历Block、Node的过程，直接为两个图的Edge构建ID-Value哈希表：

• 遍历Graph1，将每个Edge的ID作为key，value作为值存入哈希表edge_map1
• 同理遍历Graph2，构建哈希表edge_map2
• 对目标Edge ID（1、2），直接通过edge_map1[id] + edge_map2[id]得到求和结果，再复用原有的Block/Node结构生成结果图

这种方法把查询时间从遍历的O(n)降到O(1)，适合ID不连续的场景。

2. 数组直接寻址（利用ID递增特性） #

由于Edge ID是递增序列，若ID连续且已知最大范围，可使用数组替代哈希表：

• 确定两个图中Edge的最大ID，创建对应长度的数组arr1、arr2
• 遍历Graph1时，将Edge的value存入arr1[edge_id]（索引直接对应ID），Graph2存入arr2[edge_id]
• 目标ID的求和结果直接通过arr1[id] + arr2[id]获取

数组寻址比哈希表更快，无哈希冲突开销，适合ID连续的场景。

3. 并行构建映射（大规模图场景） #

若图的规模极大，可通过多线程并行处理两个图：

• 开启两个线程，分别遍历Graph1和Graph2构建映射表（哈希表或数组）
• 映射表构建完成后，再批量计算目标ID的求和值
• 这种方式能将映射构建的时间缩短近一半

4. 复用原有层级结构 #

结果图的Block、Node结构与原完全一致，无需重新创建：

• 直接复制其中一个图的Block、Node层级框架
• 仅替换对应ID的Edge的value为求和后的值
• 节省创建新结构的内存开销与时间成本

内容的提问来源于stack exchange，提问作者Мурад Ахундов