1

タイトルが言うように。私はさらに別の言語オタク：継続渡しスタイルを読んでいて、MapReduceが継続渡しスタイル（別名CPS）の1つの形式として分類できるかどうか疑問に思っていました。

また、CPSが複数のコンピューターを利用して複雑な計算を実行するにはどうすればよいのか疑問に思っています。たぶん、CPSはアクターモデルでの作業を容易にします。

4

4 に答える 4

1

私はそうは言いません。MapReduceはユーザー定義関数を実行しますが、これらは「コールバック」としてよく知られています。CPSは非常に抽象的な概念であり、関数、コルーチン、コールバック、ループなどのよく知られた概念の動作をモデル化するために一般的に使用されていると思います。通常、直接使用されることはありません。

繰り返しになりますが、CPSと継続自体を混同している可能性があります。私はどちらの専門家でもありません。

于 2010-05-06T18:19:57.563 に答える
1

私は彼らが反対だと思います。MapReduceは明らかに、Mapが独立してサブタスクを実行できるディストリビューションに適しています。CPSを使用すると、各呼び出しが小さなケースで戻ってくるのを待っている再帰関数を記述します。

CPSは、Guy Steeleが、The Future of Parallel：プログラマーは何をすべきかについての講演で、私たちが成長し、学ぶ必要がないものとして説明しているプログラミング手法の1つだと思います。

于 2010-05-06T18:22:57.570 に答える
1

CPSとMapReduceはどちらも、高階関数を利用しています。これは、両方が関数を引数として取る関数を含むことを意味します。

CPSの場合、結果をどう処理するかを示す引数を持つ関数（継続と呼ばれる）があります。通常（常にではありませんが）、継続は1回使用されます。これは、残りの計算全体をどのように続行するかを指定する関数です。これはまた、それをシリアルのようなものにします。通常、実行スレッドは1つであり、継続はそれがどのように継続されるかを指定します。

MapReduceの場合、複数回使用される関数の引数を提供しています。これらの引数関数は、実際には残りの計算全体を表すのではなく、繰り返し使用されるほんのわずかな構成要素を表します。「何度も」ビットは、多くの場合、複数のマシンに分散されるため、これは並列の種類のものになります。

ですから、あなたは共通点を見るのは正しいです。しかし、一方は実際にはもう一方の例ではありません。

于 2010-05-06T18:26:05.770 に答える
1

Map-reduceは実装です。その実装を使用できるようにするコーディングインターフェイスでは、継続を使用できます。それは実際には、フレームワークとジョブ制御がどのように抽象化されるかという問題です。PigなどのHadoopの宣言型インターフェース、またはSQLなどの一般的な宣言型言語を検討してください。インターフェイスの下の機械は、さまざまな方法で実装できます。

たとえば、抽象化されたPythonmap-reduceの実装は次のとおりです。

def mapper(input_tuples):
    "Return a generator of items with qualifying keys, keyed by item.key"
    # we are seeing a partition of input_tuples
    return (item.key, item) for (key, item) in input_items if key > 1)

def reducer(input_tuples):
    "Return a generator of items with qualifying keys"
    # we are seeing a partition of input_tuples
    return (item for (key, item) in input_items if key != 'foo')

def run_mapreduce(input_tuples):
    # partitioning is magically run across boxes
    mapper_inputs = partition(input_tuples)
    # each mapper is magically run on separate box
    mapper_outputs = (mapper(input) for input in mapper_inputs)
    # partitioning and sorting is magically run across boxes
    reducer_inputs = partition(
        sort(mapper_output for output in mapper_outputs))
    # each reducer is magically run on a separate box
    reducer_outputs = (reducer(input) for input in reducer_inputs)

そして、コルーチンを使用した同じ実装がありますが、さらに魔法の抽象化が隠されています：

def mapper_reducer(input_tuples):
    # we are seeing a partition of input_tuples
    # yield mapper output to caller, get reducer input
    reducer_input = yield (
        item.key, item) for (key, item) in input_items if key > 1)
    # we are seeing a partition of reducer_input tuples again, but the
    # caller of this continuation has partitioned and sorted
    # yield reducer output to caller
    yield (item for (key, item) in input_items if key != 'foo')
于 2010-05-06T19:13:41.653 に答える