Ist MapReduce eine Form der Continuation-Passing Style (CPS)?

Question

Wie der Titel schon sagt. Ich las Noch eine Sprache Geek: Continuation Passing Stil und ich war irgendwie gefragt, ob MapReduce kann als eine Form der Continuation-Passing-Art aka CPS kategorisiert werden.

Ich frage mich auch, wie kann CPS nutzen mehr als ein Computer komplexe Berechnung durchzuführen. Vielleicht CPS macht es einfacher, die Arbeit mit Schauspieler Modell .

Answer 1

Ich würde sagen, sie sind Gegensätze. MapReduce verleiht offensichtlich selbst Verteilung, wo Map Unteraufgaben unabhängig machen kann. Mit CPS schreiben Sie eine rekursive Funktion, wo jeder Anruf auf einem kleineren Fall wartet wieder zu bekommen.

Ich denke, CPS eine der Programmiertechniken ist, dass Guy Steele als Dinge beschreibt müssen wir entwachsen und verlernen, in seinem Vortrag auf Die Zukunft der parallel:? Was ist ein Programmierer tun

Answer 2

Das würde ich nicht sagen. MapReduce tut benutzerdefinierte Funktionen ausführen, aber diese sind als „Callbacks“ besser bekannt ist. Ich denke, CPS ein sehr abstraktes Konzept ist, die häufig verwendet wird, um das Verhalten der besser bekannte Konzepte wie Funktionen, Koroutinen, Rückrufe und Schleifen zu modellieren. Es ist im Allgemeinen nicht direkt verwendet.

Dann wieder, kann ich mit Fortsetzungen selbst verwirrend CPS sein. Ich bin kein Experte auf beide ein.

Answer 3

Sowohl CPS und MapReduce nutzen Funktionen höherer Ordnung. Dies bedeutet, dass beide beinhalten Funktionen, die Funktionen als Argumente.

Im Fall von CPS haben Sie eine Funktion mit einem Argument (eine Fortsetzung genannt), der sagt, was mit einem Ergebnis zu tun. Typischerweise (aber nicht immer) ist die Fortsetzung einmal verwendet. Es ist eine Funktion, die angibt, wie die Gesamtheit des Restes der Berechnung fortgesetzt werden sollte. Dies macht es auch eine serielle Art der Sache. Normalerweise haben Sie einen Thread der Ausführung und die Fortsetzung gibt an, wie es geht, um fortzufahren.

Im Fall von MapReduce Sie Funktionsargumente sind die Bereitstellung, die mehrfach verwendet werden. Diese Argumentation Funktionen stellen nicht wirklich den ganzen Rest der Berechnung, sondern nur kleine Bausteine, die verwendet werden, immer und immer wieder. Die „immer und immer wieder“ Bit oft über mehrere Maschinen verteilt werden, so dass diese eine parallele Art der Sache.

Sie sind also Recht, eine Gemeinsamkeit zu sehen. Aber man ist nicht wirklich ein Beispiel für die andere.

Answer 4

Karte-zu reduzieren, ist eine Implementierung. Die Codierung Schnittstelle, die Sie verwenden, dass die Umsetzung Fortsetzungen verwenden könnte; es ist wirklich eine Frage, wie der Rahmen und Auftragssteuerung abstrahiert werden. Betrachten Sie deklarative Schnittstellen für Hadoop wie Schwein oder deklarativen Sprachen im Allgemeinen wie SQL; die Maschinen unterhalb der Schnittstelle in vielerlei Hinsicht umgesetzt werden können.

Zum Beispiel, hier ist eine abstrahierte Python Karten reduzieren Implementierung:

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)

Und hier ist die gleiche Umsetzung Koroutinen verwenden, mit noch mehr magischen Abstraktion versteckt:

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')