13

一部のプログラミング言語 ( など) では、モジュール間の循環依存が許可されています。コンパイラは、1 つのモジュールのコンパイル中にインポートされたすべてのモジュールのすべての定義を知る必要があるため、一部のモジュールが相互にインポートしたり、他の種類のサイクルが発生したりする場合、通常、追加の作業を行う必要があります。その場合、コンパイラは、インポートされた関数がまだ分析されていない可能性があるため、インポートサイクルのないモジュールほどコードを最適化できない場合があります。バイナリオブジェクトには依存関係がないため、通常、サイクルの 1 つのモジュールのみをそのようにコンパイルする必要があります。そのようなモジュールをループブレーカーと呼びましょう

特に、インポート サイクルがインターリーブされている場合、何百ものモジュールで構成される大きなプロジェクトをコンパイルするときに、ループ ブレーカーの数を最小限に抑える方法を知ることは興味深いことです。

プログラムを正常にコンパイルするためにループブレーカーとしてコンパイルする必要がある依存関係のセットが出力されるモジュールの最小数を指定するアルゴリズムはありますか?

例

この例で私が何を意味するのかを明確にしようとしています。

A、B、Cおよびの 4 つのモジュールを含むプロジェクトを考えてみましょうD。これは、これらのモジュール間の依存関係のリストです。エントリのX y手段は以下yに依存しxます:

交流
広告
学士
CB
DB

アスキー図として視覚化された同じ関係:

D ---> B
^ / ^
| | / |
| | / |
| | 中 |
A ---> C

この依存関係グラフには と の 2 つのサイクルがありADBますACB。これらのサイクルを断ち切るには、たとえばモジュールCをコンパイルしD、ループ ブレーカーとして使用できます。明らかに、これは最良のアプローチではありません。ループ ブレーカーとしてコンパイルAするだけで両方のループを完全に解除でき、ループ ブレーカーとしてコンパイルする必要があるモジュールが 1 つ少なくなります。

4

2 に答える 2

19

これは、最小フィードバック頂点セットとして知られる NP 困難 (および APX 困難) 問題です。Demetrescu と Finocchiによる近似アルゴリズム(pdf, Combinatorial Algorithms for Feedback Problems in Directed Graphs (2003)")は、長い単純なサイクルがない場合に実際にうまく機能します。

于 2012-05-15T20:18:06.753 に答える
3

これを Python で行う方法は次のとおりです。

from collections import defaultdict

def topological_sort(dependency_pairs):
    'Sort values subject to dependency constraints'
    num_heads = defaultdict(int)   # num arrows pointing in
    tails = defaultdict(list)      # list of arrows going out
    for h, t in dependency_pairs:
        num_heads[t] += 1
        tails[h].append(t)

    ordered = [h for h in tails if h not in num_heads]
    for h in ordered:
        for t in tails[h]:
            num_heads[t] -= 1
            if not num_heads[t]:
                ordered.append(t)
    cyclic = [n for n, heads in num_heads.iteritems() if heads]
    return ordered, cyclic

def is_toposorted(ordered, dependency_pairs):
    '''Return True if all dependencies have been honored.
       Raise KeyError for missing tasks.
    '''
    rank = {t: i for i, t in enumerate(ordered)}
    return all(rank[h] < rank[t] for h, t in dependency_pairs)

print topological_sort('aa'.split())
ordered, cyclic = topological_sort('ah bg cf ch di ed fb fg hd he ib'.split())
print ordered, cyclic
print is_toposorted(ordered, 'ah bg cf ch di ed fb fg hd he ib'.split())
print topological_sort('ah bg cf ch di ed fb fg hd he ib ba xx'.split())

実行時間は、エッジ (依存関係のペア) の数に線形に比例します。

このアルゴリズムは、先行 (着信矢印) の数をカウントする num_heads と呼ばれるルックアップ テーブルを中心に構成されています。このah bg cf ch di ed fb fg hd he ib例では、カウントは次のとおりです。

node  number of incoming edges
----  ------------------------
 a       0
 b       2
 c       0
 d       2
 e       1
 f       1  
 g       2
 h       2
 i       1

このアルゴリズムは、先行ノードのないノードを「訪問」することによって機能します。たとえば、ノードaとcには着信エッジがないため、最初にアクセスされます。

訪問とは、ノードが出力され、グラフから削除されることを意味します。ノードが訪問されると、その後続ノードをループし、着信カウントを 1 減らします。

たとえば、訪問中のノードaでは、その後続ノードに移動してh、着信カウントを 1 減らします (つまり、. h 2h 1

同様に、ノード にアクセスすると、その後続ノードおよびcをループし、それらのカウントを 1 減らします (したがって、はおよび になります)。 fhf 1f 0h 1h 0

ノードfと にhは入力エッジがなくなったので、すべてのノードが訪問されるまで、それらを出力してグラフから削除するプロセスを繰り返します。例では、訪問順序 (トポロジー ソートは次のとおりです):

a c f h e d i b g

入力エッジのないノードがない状態に num_heads が到達した場合は、トポロジー的にソートできないサイクルが存在し、アルゴリズムが終了することを意味します。

于 2012-05-15T19:59:13.397 に答える