給出一個通過圖的路徑列表，高效地找到使用每條邊的路徑

Question

我有一張圖和圖中的路徑列表。對於每個邊緣e，我需要找到使用e的路徑，然後根據這些路徑做一些其他工作。圖的大小和對內存使用的限制是這樣的，我不能只遍歷所有建立一組數組的路徑，其中設置i包含使用邊i的路徑。

的暴力方法，將工作是：

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

我怎樣才能得到更好的時間效率，同時保持存儲效率？

Answer 1

您的規格不明確。你從哪裏得到圖表和路徑？它們是否已經預先計算並存儲在磁盤中？您是否需要同時維護RAM中圖形中所有邊的路徑集，還是可以逐個處理它們，然後釋放內存？在創建集合時是否存儲路徑的副本，或者是否可以索引到單個副本？

如果你沒有足夠的RAM，你可以使用一些在磁盤上運行的數據結構。 STXXL庫就是這樣一個庫。