1

特にHadoopによって実装されたMapReduceフレームワークについてまだ学んでおり、次のタスクを実行するように変更できるかどうか疑問に思っています:

Map() 関数は、キーがサイズ 2 の配列、たとえば int[2] である (key,value) ペアを出力します。共通の 2 つの整数のいずれかを含むすべてのペアを同じレデューサーにマップしたいと思います。

たとえば、Map() が ([2,3],4),([2,4],5),([6,5],2),([5,7],1),次に、Reduce1 は最初の 2 つのペアを受け取り、Reduce2 は次の 2 つのペアを受け取る必要があります (最初の 2 つは 2 を共有し、2 番目の 2 つは 5 を共有します)。これは、頂点が int[] 内の整数であり、エッジが同じ int[] 内の任意の 2 つの整数間で共有される連結成分の問題と見なすことができます。

4

1 に答える 1

1

アルゴリズムの変更により、おそらくこれを達成できますが、各エッジを2回放出する必要があります

現在出力しているエッジごとに、両方の頂点 ID を出力し、出力値を修正して、もう一方のエッジ、重み、およびオプションで方向を含める必要があります (エッジの方向がアルゴリズムにとって重要な場合)。

したがって、これの代わりに：

([2,3],4)
([2,4],5)
([6,5],2)
([5,7],1)

これを出力します (S はキーが送信元であることを示し、D はキーが送信先であることを示します):

(2, [3, 4, S])
(3, [2, 4, D])
(2, [4, 5, S])
(4, [2, 5, D])
(6, [5, 2, S])
(5, [6, 2, D])
(5, [7, 1, S])
(7, [5, 1, D])

レデューサーでは、頂点 ID でグループ化し、他の頂点 ID、重み、および方向を含む他のタプルを反復処理できるようになります。

(2, [3, 4, S])
(2, [4, 5, S])

(3, [2, 4, D])

(4, [2, 5, D])

(5, [6, 2, D])
(5, [7, 1, S])

(6, [5, 2, S])

(7, [5, 1, D])

特にエッジが 2 つの頂点間に両方向に存在する場合は、各エッジが 2 回処理される可能性があることに注意する必要があります。

于 2013-05-23T00:03:21.857 に答える