0

直径が大きい場合がある (最大のコンポーネントが 1m に達することもある) グラフで接続コンポーネントを見つけるための単純なアルゴリズムを探しました。

非常に洗練された MR アルゴリズムが多数見つかりました。

非常に単純なアルゴリズムの何が問題なのか:

  • foreach コンポーネントで、node として flatten(nodes_bag) を生成し、comp_id として node_with_the_smallest_id を生成します。
  • ノードごとにグループ化
  • 複数の comp_id を持つノードをフィルタリングし、「大きな comp_id を小さな comp_id に更新」テーブルを構築します。
  • 大きな comp_id を持つすべてのノードを、対応する新しい小さな comp_id に更新し、ダーティとしてマークします。

これらの汚れたノードを使用して次の反復に進みます...ここで何が欠けているのでしょうか?

4

2 に答える 2

0

Ok。この非常に単純なアルゴリズムを使用できない理由は、ビルドの「大きな comp_id を小さな comp_id に更新する」ステージが再帰的になる可能性があるというバグがあるためです。たとえば、前の反復から 3 つのコンポーネントがある場合:

A->{1,2}
B->{2,3}
C->{3,4}

group by と filter により、次の変換テーブルが作成されます。

A->B
B->C

そして、これにより、場合によっては反復回数が線形 (最大直径) になります = このミニ例のような長いチェーンは、収束に長い時間がかかります。

于 2013-07-03T14:48:29.540 に答える