Что такое карта / уменьшение?

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

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

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

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

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

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

См. Также: Википедия: MapReduce

Связанный вопрос: просто объясните mapreduce

Объяснение MapReduce .

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

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

Вот так, вероятно, написана карта на C # (она называется 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;
}

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

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

В C # Aggregateметод reduce вызывается и снова находится в стандартной библиотеке. Я сразу перейду к версии для 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); }
   }

Будем надеяться, что дженерики избавятся от слепков. Типичный эквивалент в C #:

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

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

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

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

Тогда я пошел вперед и сделал его более кратким путем перевода в 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
}

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

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

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

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

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

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

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

Основная идея состоит в том, что вы делите задание на две части: карту и сокращение. По сути, Map берет проблему, разбивает ее на части и отправляет части на разные машины, поэтому все части работают одновременно. 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