Was ist Map / Reduce?

Ich höre viel über Map / Reduce, insbesondere im Zusammenhang mit Googles massiv parallelem Rechensystem. Was genau ist das?

Aus der Zusammenfassung der MapReduce- Forschungspublikationsseite von Google :

MapReduce ist ein Programmiermodell und eine zugehörige Implementierung zum Verarbeiten und Generieren großer Datenmengen. Benutzer geben eine Zuordnungsfunktion an, die ein Schlüssel / Wert-Paar verarbeitet, um einen Satz von Zwischenschlüssel / Wert-Paaren zu generieren, und eine Reduzierungsfunktion, die alle Zwischenwerte zusammenführt, die demselben Zwischenschlüssel zugeordnet sind.

Der Vorteil von MapReduce besteht darin, dass die Verarbeitung parallel auf mehreren Verarbeitungsknoten (mehreren Servern) ausgeführt werden kann, sodass das System sehr gut skaliert werden kann.

Da es auf dem funktionalen Programmiermodell basiert , haben die Schritte mapund reducekeine Nebenwirkungen (der Status und die Ergebnisse der einzelnen Unterabschnitte eines mapProzesses hängen nicht von einem anderen ab), sodass der Datensatz, der abgebildet und reduziert wird, getrennt werden kann über mehrere Verarbeitungsknoten.

Joel's Kann Ihre Programmiersprache dies tun? In diesem Artikel wird erläutert, wie wichtig es war, die funktionale Programmierung in Google zu verstehen, um MapReduce zu entwickeln, das die Suchmaschine antreibt. Es ist eine sehr gute Lektüre, wenn Sie mit der funktionalen Programmierung nicht vertraut sind und wissen, wie sie skalierbaren Code ermöglicht.

Siehe auch: Wikipedia: MapReduce

Verwandte Frage: Bitte erklären Sie mapreduce einfach

MapReduce erklärt .

Es erklärt besser als ich kann. Hilft es?

Map ist eine Funktion, die eine andere Funktion auf alle Elemente in einer Liste anwendet, um eine weitere Liste mit allen Rückgabewerten zu erstellen. (Eine andere Möglichkeit, "f auf x anwenden" zu sagen, ist "f aufrufen, x übergeben". Manchmal klingt es also besser, "anwenden" anstelle von "aufrufen" zu sagen.)

So wird map wahrscheinlich in C # geschrieben (es heißt Selectund befindet sich in der Standardbibliothek):

public static IEnumerable<R> Select<T, R>(this IEnumerable<T> list, Func<T, R> func)
{
    foreach (T item in list)
        yield return func(item);
}

Da Sie ein Java-Typ sind und Joel Spolsky GROSSLY UNFAIR LIES gerne erzählt, wie beschissen Java ist (eigentlich lügt er nicht, es ist beschissen, aber ich versuche, Sie für sich zu gewinnen), ist hier mein sehr grober Versuch eine Java-Version (Ich habe keinen Java-Compiler und erinnere mich vage an Java-Version 1.1!):

// represents a function that takes one arg and returns a result
public interface IFunctor
{
    object invoke(object arg);
}

public static object[] map(object[] list, IFunctor func)
{
    object[] returnValues = new object[list.length];

    for (int n = 0; n < list.length; n++)
        returnValues[n] = func.invoke(list[n]);

    return returnValues;
}

Ich bin sicher, dass dies auf millionenfache Weise verbessert werden kann. Aber es ist die Grundidee.

Reduzieren ist eine Funktion, die alle Elemente in einer Liste in einen einzigen Wert umwandelt. Dazu muss eine andere Funktion funczugewiesen werden, die zwei Elemente in einen einzigen Wert verwandelt. Es würde funktionieren, wenn man die ersten beiden Punkte an gibt func. Dann das Ergebnis davon zusammen mit dem dritten Punkt. Dann das Ergebnis davon mit dem vierten Element und so weiter, bis alle Elemente verschwunden sind und wir einen Wert haben.

In C # wird reduzieren aufgerufen Aggregateund befindet sich wieder in der Standardbibliothek. Ich werde direkt zu einer Java-Version springen:

// represents a function that takes two args and returns a result
public interface IBinaryFunctor
{
    object invoke(object arg1, object arg2);
}

public static object reduce(object[] list, IBinaryFunctor func)
{
    if (list.length == 0)
        return null; // or throw something?

    if (list.length == 1)
        return list[0]; // just return the only item

    object returnValue = func.invoke(list[0], list[1]);

    for (int n = 1; n < list.length; n++)
        returnValue = func.invoke(returnValue, list[n]);

    return returnValue;
}

Diese Java-Versionen müssen durch Generika ergänzt werden, aber ich weiß nicht, wie das in Java geht. Aber Sie sollten in der Lage sein, ihnen anonyme innere Klassen zu übergeben, um die Funktoren bereitzustellen:

string[] names = getLotsOfNames();

string commaSeparatedNames = (string)reduce(names, 
   new IBinaryFunctor {
       public object invoke(object arg1, object arg2)
           { return ((string)arg1) + ", " + ((string)arg2); }
   }

Hoffentlich würden Generika die Abgüsse loswerden. Das typsichere Äquivalent in C # lautet:

string commaSeparatedNames = names.Aggregate((a, b) => a + ", " + b);

Warum ist das "cool"? Einfache Möglichkeiten, größere Berechnungen in kleinere Teile zu zerlegen, damit sie auf unterschiedliche Weise wieder zusammengesetzt werden können, sind immer cool. Google wendet diese Idee auf die Parallelisierung an, da sowohl Map als auch Reduce auf mehrere Computer verteilt werden können.

Die wichtigste Voraussetzung ist jedoch NICHT, dass Ihre Sprache Funktionen als Werte behandeln kann. Das kann jede OO-Sprache. Die eigentliche Voraussetzung für die Parallelisierung ist, dass die kleinen funcFunktionen, die Sie an die Zuordnung und Reduzierung übergeben, keinen Status verwenden oder aktualisieren dürfen. Sie müssen einen Wert zurückgeben, der nur von den an sie übergebenen Argumenten abhängt. Andernfalls werden die Ergebnisse völlig durcheinander gebracht, wenn Sie versuchen, das Ganze parallel auszuführen.

Nachdem ich entweder mit sehr langen Waffeln oder sehr kurzen vagen Blog-Posts am meisten frustriert war, entdeckte ich schließlich dieses sehr gute, strenge, prägnante Papier .

Dann habe ich es durch die Übersetzung in Scala präziser gestaltet, wo ich den einfachsten Fall angegeben habe, in dem ein Benutzer einfach nur die mapund reduceTeile der Anwendung spezifiziert . In Hadoop / Spark wird streng genommen ein komplexeres Programmiermodell verwendet, bei dem der Benutzer explizit vier weitere Funktionen angeben muss, die hier beschrieben werden: http://en.wikipedia.org/wiki/MapReduce#Dataflow

import scalaz.syntax.id._

trait MapReduceModel {
  type MultiSet[T] = Iterable[T]

  // `map` must be a pure function
  def mapPhase[K1, K2, V1, V2](map: ((K1, V1)) => MultiSet[(K2, V2)])
                              (data: MultiSet[(K1, V1)]): MultiSet[(K2, V2)] = 
    data.flatMap(map)

  def shufflePhase[K2, V2](mappedData: MultiSet[(K2, V2)]): Map[K2, MultiSet[V2]] =
    mappedData.groupBy(_._1).mapValues(_.map(_._2))

  // `reduce` must be a monoid
  def reducePhase[K2, V2, V3](reduce: ((K2, MultiSet[V2])) => MultiSet[(K2, V3)])
                             (shuffledData: Map[K2, MultiSet[V2]]): MultiSet[V3] =
    shuffledData.flatMap(reduce).map(_._2)

  def mapReduce[K1, K2, V1, V2, V3](data: MultiSet[(K1, V1)])
                                   (map: ((K1, V1)) => MultiSet[(K2, V2)])
                                   (reduce: ((K2, MultiSet[V2])) => MultiSet[(K2, V3)]): MultiSet[V3] =
    mapPhase(map)(data) |> shufflePhase |> reducePhase(reduce)
}

// Kinda how MapReduce works in Hadoop and Spark except `.par` would ensure 1 element gets a process/thread on a cluster
// Furthermore, the splitting here won't enforce any kind of balance and is quite unnecessary anyway as one would expect
// it to already be splitted on HDFS - i.e. the filename would constitute K1
// The shuffle phase will also be parallelized, and use the same partition as the map phase.  
abstract class ParMapReduce(mapParNum: Int, reduceParNum: Int) extends MapReduceModel {
  def split[T](splitNum: Int)(data: MultiSet[T]): Set[MultiSet[T]]

  override def mapPhase[K1, K2, V1, V2](map: ((K1, V1)) => MultiSet[(K2, V2)])
                                       (data: MultiSet[(K1, V1)]): MultiSet[(K2, V2)] = {
    val groupedByKey = data.groupBy(_._1).map(_._2)
    groupedByKey.flatMap(split(mapParNum / groupedByKey.size + 1))
    .par.flatMap(_.map(map)).flatten.toList
  }

  override def reducePhase[K2, V2, V3](reduce: ((K2, MultiSet[V2])) => MultiSet[(K2, V3)])
                             (shuffledData: Map[K2, MultiSet[V2]]): MultiSet[V3] =
    shuffledData.map(g => split(reduceParNum / shuffledData.size + 1)(g._2).map((g._1, _)))
    .par.flatMap(_.map(reduce))
    .flatten.map(_._2).toList
}

MapReduce und / oder SQL:

http://www.data-miners.com/blog/2008/01/mapreduce-and-sql-aggregations.html

http://www.data-miners.com/blog/

Kritik an MapReduce

http://www.databasecolumn.com/2008/01/mapreduce-a-major-step-back.html

http://www.databasecolumn.com/2008/01/mapreduce-continued.html

Map ist eine native JS-Methode, die auf ein Array angewendet werden kann. Es erstellt ein neues Array als Ergebnis einer Funktion, die jedem Element im ursprünglichen Array zugeordnet ist. Wenn Sie also eine Funktion (ein Element) {return element * 2;} zuordnen, wird ein neues Array zurückgegeben, wobei jedes Element verdoppelt wird. Das ursprüngliche Array würde unverändert bleiben.

https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Array/map

Reduzieren ist eine native JS-Methode, die auch auf ein Array angewendet werden kann. Es wendet eine Funktion auf ein Array an und hat einen anfänglichen Ausgabewert, der als Akkumulator bezeichnet wird. Es durchläuft jedes Element im Array, wendet eine Funktion an und reduziert sie auf einen einzelnen Wert (der als Akkumulator beginnt). Dies ist nützlich, da Sie jede gewünschte Ausgabe haben können. Sie müssen nur mit dieser Art von Akkumulator beginnen. Wenn ich also etwas in ein Objekt reduzieren wollte, würde ich mit einem Akkumulator {} beginnen.

https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Array/Reduce?v=a

Karte verkleinern:

Um etwas Großes auszuführen, können wir die Rechenleistung verschiedener Computer in unserem Büro verwenden. Der schwierige Teil besteht darin, die Aufgabe auf verschiedene Computer aufzuteilen. Dies erfolgt über die MapReduce-Bibliothek.

Die Grundidee ist, dass Sie den Job in zwei Teile teilen: eine Karte und eine Reduzieren. Map nimmt das Problem im Grunde genommen auf, teilt es in Unterteile auf und sendet die Unterteile an verschiedene Maschinen - so dass alle Teile gleichzeitig ausgeführt werden. Reduzieren nimmt die Ergebnisse aus den Unterteilen und kombiniert sie wieder, um eine einzige Antwort zu erhalten.

Die Eingabe ist eine Liste von Datensätzen. Das Ergebnis der Kartenberechnung ist eine Liste von Schlüssel / Wert-Paaren. Reduzieren verwendet jeden Wertesatz mit demselben Schlüssel und kombiniert sie zu einem einzigen Wert. Sie können nicht feststellen, ob der Job in 100 oder 2 Teile aufgeteilt wurde. Das Endergebnis ähnelt dem Ergebnis einer einzelnen Karte.

Bitte schauen Sie sich die einfache Karte an und reduzieren Sie das Programm:

Die Kartenfunktion wird verwendet, um eine Funktion auf unsere ursprüngliche Liste anzuwenden, und daher wird eine neue Liste generiert. Die map () -Funktion in Python verwendet eine Funktion und eine Liste als Argument. Eine neue Liste wird zurückgegeben, indem auf jedes Listenelement eine Funktion angewendet wird.

li = [5, 7, 4, 9] 
final_list = list(map(lambda x: x*x , li)) 
print(final_list)  #[25, 49, 16, 81]

Die Funktion redu () in Python verwendet eine Funktion und eine Liste als Argument. Die Funktion wird mit einer Lambda-Funktion und einer Liste aufgerufen und ein neues reduziertes Ergebnis zurückgegeben. Dies führt eine sich wiederholende Operation über die Paare der Liste aus.

#reduce func to find product/sum of list
x=(1,2,3,4)
from functools import reduce
reduce(lambda a,b:a*b ,x) #24