1

このグラフにはグラフとパスのリストがあります。エッジごとにe、 を使用するパスを見つけ、eこれらのパスに基づいて他の作業を行う必要があります。グラフのサイズとメモリ使用量の制限により、セットの配列を構築するすべてのパスを一度だけ反復することはできません。ここで、セットiには edge を使用するパスが含まれますi。

うまくいくブルートフォースアプローチは次のとおりです。

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

メモリ効率を維持しながら時間効率を向上させるにはどうすればよいですか?

4

1 に答える 1

1

あなたの仕様は明確ではありません。グラフとパスはどこから取得しますか? それらはすでに事前に計算され、ディスクに保存されていますか? グラフ内のすべてのエッジに対して設定されたパスを同時に RAM に保持する必要がありますか?それとも、それらを 1 つずつ処理してからメモリを解放できますか? セットを作成するときにパスのコピーを保存しますか?それとも単一のコピーにインデックスを作成できますか?

十分な RAM がない場合は、ディスク上で動作するいくつかのデータ構造を使用できます。STXXLライブラリは、そのようなライブラリの 1 つです。

于 2012-07-05T07:06:09.603 に答える