algorithm - 並行して実行できる非可換レデューサーはmapreduceにありますか？

Question

中央値や平均などの一部の演算は非可換です。この場合、レデューサーはグローバルビューを持つ必要があるため、レデューサーは1つしか存在できないようです。並行して実行できるmap-reduceに非可換レデューサーはありますか？非可換演算に遭遇したとき、人々は本当にmap-reduceを使用しますか？それとも、非常に強力なマシンで実行しますか？非可換演算を可換演算に分割する一般的な方法はありますか？

ありがとう

Answer 1

ここで「可換」という言葉を使うのが適切かどうかはわかりませんが、あなたの言っていることは理解できます。

Hadoop では、マッピング後のフェーズは実際には 2 つのステップに分割されます: aCombinerと aReducerで、同じシグネチャを持ちます。はCombinerマッパーで実行され、キーでソートされてレデューサーに送信される前に、出力のサイズを縮小します。a だけを指定するReducerと、両方に使用されます。しかし、それらを分離して、思ったよりも驚くほど多くのことを行うことができます。

カウント操作を行う単純なケースでは、結合ステップとリデュース ステップの両方に使用できるカウント リデューサーを使用します。これにより、同じキーをネットワーク経由で複数回送信する必要がなくなります。

異なるコンバイナーとリデューサーを定義することで、平均を計算する際に同様の効率を達成できます。たとえば、マッパーは(number, 1)、数値とカウント 1 に対応する値を出力します。コンバイナーは、値のコレクションを(sum, count)タプルまたはタプルのいずれかにマップできます。(mean, count)リデューサーは、カウントされた重みを使用してこれらを集計し、平均を生成できます。(余談ですが、Kahan summationを使用すると、多くの数値を加算する際のエラーを大幅に減らすことができます)。これにより、マッパーは単純なカウントの例と同じようにいくつかの結合を行うことができます。

1 回の map-reduce ステップで多くの巧妙なことを行うことができます。ただし、これは中央値では不可能だと思います。その場合、実際には 1 台のマシンの状態を介してすべての数値を送信する必要があります。