algorithm - 给定通过图的路径列表，有效地找到使用每条边的路径

Question

我有一个图表和这个图表中的路径列表。对于每条边e，我需要找到使用的路径e，然后根据这些路径做一些其他的工作。图的大小和对内存使用的限制使得我不能只遍历所有构建集合数组的路径一次，其中 seti包含使用 edge 的路径i。

可行的蛮力方法是：

for edge in edges:
    x = []
    for path in paths:
        if edge in path:
          x.append(path)
    f(x)

如何在保持内存效率的同时获得更好的时间效率？

Answer 1

你的规格不清楚。你从哪里得到图表和路径？它们是否已经预先计算并存储在磁盘中？是需要在RAM中同时维护图中所有边的路径集，还是可以一一处理，然后释放内存？创建集合时是否存储路径的副本，或者可以索引到单个副本中？

如果您没有足够的 RAM，您可以使用一些在磁盘上运行的数据结构。STXXL库就是这样一个库。