非同期 Python とgraphlib を使用した DAG の処理

私は最近、Python の底なしの標準ライブラリ、graphlib で興味深いモジュールを見つけました。これまでに使用したことがない場合は、これは Python 3.9 で追加された小さなユーティリティであり、TopologicalSorter という 1 つのクラスのみを実装しています。

名前は一目瞭然です -- これはグラフのトポロジカルソートのためのクラスです。しかし、これは、prepare() メソッドや is_active() など、かなり不可解だが信じられないほど便利な API を備えているため、元々はソートだけを念頭に置いて書かれたとは思えません。ドキュメント内のこの例は、その背後にある動機を示唆しています:

リーリー

したがって、graphlib はグラフを並べ替えるだけのモジュールではなく、トポロジカルな順序でタスクのグラフを実行するためのユーティリティでもあります。これは、ワークロードに他のタスクの結果に依存するタスクがある場合に役立ちます。グラフはこの問題をモデル化する優れた方法であり、トポロジー的順序はタスクが正しい順序で処理されることを確認する方法です。

ドキュメントに欠けているものの 1 つは asyncio の例ですが、これは非常に簡単に作成できることがわかりました。 asyncio を使用すると、スレッドセーフに対処する必要がないため、スレッドを同期するためのキューや、その他の追加の複雑さを使用せずに済みます。

単純な非同期ノードの訪問者関数を定義します:

リーリー

現実の世界では、I/O バウンドの作業を行っている限り、これはいくらでも複雑になる可能性があるため、asyncio のメリットを享受してください。重要なのは、関数の最後で sorter.done(node) を呼び出して、TopologicalSorter のインスタンスにこのノードの処理が完了し、次のノードに進むことができることを知らせることです。

次に、訪問関数をトポロジー的に順序付けされた実行に接続します。

リーリー

動作するスクリプトの完全なソース コードは、この要点にあります。

graphlib の独特な側面の 1 つは、TopologicalSorter が引数として受け入れるグラフの形式です。これは、一般的なグラフ表現とは逆の順序になっています。例えば。このようなグラフがある場合、A -> B -> C、通常は次のように表します:

リーリー

しかし、TopologicalSorter はこのグラフのエッジ方向を反転させたいと考えています:

オプションのグラフ引数が指定される場合、それはキーがノードであり、値がグラフ内のそのノードのすべての先行ノードの反復可能である有向非巡回グラフを表す辞書である必要があります

A -> を表す正しい方法は次のとおりです。 B -> TopologicalSorter の C は次のとおりです:

リーリー

これに関する詳しい情報と白熱した議論は、こちらでご覧いただけます: https://bugs.python.org/issue46071.

コーディングを楽しんでください!

以上が非同期 Python とgraphlib を使用した DAG の処理の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。