Что такое Map/Reduce?

Я много слышал о карте/сокращении, особенно в контексте широкомасштабной параллельной вычислительной системы Google. Что это такое?

Ответ 1

Из реферала Google MapReduce страница публикации исследования:

MapReduce - это модель программирования и связанная реализация для обработки и генерации больших данных наборы. Пользователи задают функцию карты который обрабатывает пару ключ/значение сгенерировать набор промежуточных пары ключ/значение и функция уменьшения который объединяет все промежуточные значения связанные с одним и тем же промежуточным ключ.

Преимущество MapReduce заключается в том, что обработка может выполняться параллельно на нескольких узлах обработки (несколько серверов), поэтому это система, которая может масштабироваться очень хорошо.

Поскольку он основан на функциональном программировании, шаги map и reduce не имеют побочных эффектов ( состояние и результаты каждого подраздела процесса map не зависят от другого), поэтому набор данных, отображаемый и уменьшенный, может быть разделен на несколько обрабатывающих узлов.

Joel Может ли ваш язык программирования сделать это? в части обсуждается, как понимание функционального программирования было существенным в Google, чтобы придумать MapReduce, поисковый движок. Это очень хорошо читается, если вы не знакомы с функциональным программированием и как он позволяет масштабируемый код.

Смотрите также: Википедия: MapReduce

Связанный с этим вопрос: Пожалуйста, объясните, как просто изменить mapreduce

Ответ 2

MapReduce Explained.

Это объясняет лучше, чем я могу. Помогает ли это?

Ответ 3

Карта - это функция, которая применяет другую функцию ко всем элементам в списке, чтобы создать другой список со всеми возвращаемыми значениями на нем. (Еще один способ сказать "применить f к x" - это "вызов f, передающий его x". Поэтому иногда лучше сказать "применить" вместо "вызова".)

Так как карта, вероятно, написана на С# (она называется Select и находится в стандартной библиотеке):

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

Как вы - чувак Java, а Джоэл Спольский любит рассказывать, что неряшливая Java (на самом деле, он не лжет, это дерьмово, но я пытаюсь вас победить), вот мой очень грубая попытка Java-версии (у меня нет компилятора Java, и я смутно помню Java-версию 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;
}

Я уверен, что это может быть улучшено миллионами способов. Но это основная идея.

Сокращение - это функция, которая превращает все элементы в список в одно значение. Для этого ему нужно предоставить еще одну функцию func, которая превращает два элемента в одно значение. Это сработало бы, передав первые два элемента в func. Тогда результат этого вместе с третьим пунктом. Затем результат этого с четвертым элементом и так далее, пока все предметы не исчезнут, и мы останемся с одним значением.

В С# сокращение называется Aggregate и снова находится в стандартной библиотеке. Я перейду прямо к версии Java:

// 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;
}

Эти версии Java нуждаются в добавлении к ним дженериков, но я не знаю, как это сделать на Java. Но вы должны иметь возможность передавать им анонимные внутренние классы для предоставления функторов:

string[] names = getLotsOfNames();

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

Надеюсь, дженерики избавятся от приведения. Типичным эквивалентом в С# является:

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

Почему это "круто"? Простые способы разбивать большие вычисления на более мелкие кусочки, поэтому их можно комбинировать по-разному, всегда здорово. Способ, которым Google применяет эту идею, заключается в распараллеливании, поскольку и карта, и сокращение могут быть разделены на нескольких компьютерах.

Но ключевым требованием НЕ является то, что ваш язык может рассматривать функции как значения. Любой язык OO может это сделать. Фактическое требование для распараллеливания состоит в том, что маленькие func функции, которые вы передаете на карту, и сокращение не должны использовать или обновлять какое-либо состояние. Они должны возвращать значение, зависящее только от переданного им аргумента (ов). В противном случае результаты будут полностью запутаны, когда вы попытаетесь запустить все это параллельно.

Ответ 4

После того, как вы расстроились либо очень длинными ваффлями, либо очень короткими неопределенными сообщениями в блоге, я в конце концов обнаружил эту очень хорошую строгую краткими бумагами.

Затем я пошел дальше и сделал его более кратким, переведя на Scala, где я представил простейший случай, когда пользователь просто просто указывает части приложения map и reduce. В Hadoop/Spark, строго говоря, используется более сложная модель программирования, которая требует от пользователя явно указать еще 4 функции, описанные здесь: 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
}

Ответ 5

MapReduce и/или SQL:

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

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

критика MapReduce

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

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

Ответ 6

Карта - это собственный метод JS, который может быть применен к массиву. Он создает новый массив в результате некоторой функции, сопоставленной каждому элементу исходного массива. Поэтому, если вы сопоставили функцию (элемент) {return element * 2;}, она возвращала новый массив с каждым элементом в два раза. Исходный массив будет немодифицирован.

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

Сокращение - это собственный JS-метод, который также может применяться к массиву. Он применяет функцию к массиву и имеет начальное значение вывода, называемое аккумулятором. Он проходит через каждый элемент массива, применяет функцию и сводит их к одному значению (которое начинается как накопитель). Это полезно, потому что вы можете получить любой вывод, который вам нужен, вам просто нужно начать с этого типа аккумулятора. Поэтому, если бы я хотел что-то свести к объекту, я бы начал с аккумулятора {}.

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

Ответ 7

Уменьшение карты:

Чтобы запустить что-то большое, мы можем использовать вычислительную мощность другого компьютера в нашем офисе. Сложная часть - разделить задачу между разными компьютерами. Это делается библиотекой MapReduce.

Основная идея заключается в том, что вы делите работу на две части: карту и уменьшение. Карта в основном берет на себя задачу, разбивает ее на части и отправляет части на разные машины, поэтому все части выполняются одновременно. Reduce берет результаты из частей и объединяет их вместе, чтобы получить единый ответ.

Ввод - это список записей. Результатом вычисления карты является список пар ключ/значение. Reduce принимает каждый набор значений, имеющих одинаковый ключ, и объединяет их в одно значение. Вы не можете сказать, было ли задание разбито на 100 частей или 2 части; конечный результат очень похож на результат одной карты.

Пожалуйста, посмотрите на простую карту и уменьшите программу:

Функция карты используется, чтобы применить некоторую функцию к нашему первоначальному списку, и поэтому создается новый список. Функция map() в Python принимает в качестве аргумента функцию и список. Новый список возвращается путем применения функции к каждому элементу списка.

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

Функция Reduce() в Python принимает функцию и список в качестве аргумента. Функция вызывается с лямбда-функцией и списком, и возвращается новый сокращенный результат. Это выполняет повторяющуюся операцию над парами списка.

#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