Map / Reduce 란 무엇입니까?

Map / Reduce 란 무엇입니까?

---

특히 Google의 대규모 병렬 컴퓨팅 시스템에서 map / reduce에 대해 많이 듣습니다. 정확히 무엇입니까?

---

Google의 MapReduce 연구 간행물 페이지 요약에서 발췌 :

MapReduce는 대규모 데이터 세트를 처리하고 생성하기위한 프로그래밍 모델 및 관련 구현입니다. 사용자는 키 / 값 쌍을 처리하여 일련의 중간 키 / 값 쌍을 생성하는 맵 함수와 동일한 중간 키와 관련된 모든 중간 값을 병합하는 축소 함수를 지정합니다.

MapReduce의 장점은 처리가 여러 처리 노드 (여러 서버)에서 병렬로 수행 될 수 있으므로 매우 잘 확장 할 수있는 시스템이라는 것입니다.

함수형 프로그래밍 모델을 기반으로하기 때문에 map및 reduce단계는 각각 부작용 map이 없으므로 (프로세스 의 각 하위 섹션의 상태와 결과는 서로 의존하지 않음) 매핑 및 축소되는 데이터 세트를 각각 분리 할 수 ​​있습니다. 여러 처리 노드를 통해.

Joel의 프로그래밍 언어로이 작업을 수행 할 수 있습니까? piece에서는 검색 엔진을 지원하는 MapReduce를 만들기 위해 Google에서 함수형 프로그래밍을 이해하는 것이 얼마나 필수적인지 설명합니다. 함수형 프로그래밍과 확장 가능한 코드를 허용하는 방법에 익숙하지 않은 경우 매우 좋은 읽기입니다.

참고 : Wikipedia : MapReduce

관련 질문 : mapreduce를 간단하게 설명하십시오 .

---

MapReduce 설명 .

내가 할 수있는 것보다 더 잘 설명합니다. 도움이 되나요?

---

Map은 목록의 모든 항목에 다른 함수를 적용하여 모든 반환 값이있는 다른 목록을 생성하는 함수입니다. ( "apply f to x"의 또 다른 표현은 "call f, pass it x"입니다. 따라서 "call"대신 "apply"라고 말하는 것이 더 좋을 때도 있습니다.)

이것은 아마도지도가 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 친구이고 Joel Spolsky는 GROSSLY UNFAIR LIES에게 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 #에서는 reduce가 호출 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); }
   }

제네릭이 캐스트를 제거하기를 바랍니다. C #의 typesafe는 다음과 같습니다.

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

Why is this "cool"? Simple ways of breaking up larger calculations into smaller pieces, so they can be put back together in different ways, are always cool. The way Google applies this idea is to parallelization, because both map and reduce can be shared out over several computers.

But the key requirement is NOT that your language can treat functions as values. Any OO language can do that. The actual requirement for parallelization is that the little func functions you pass to map and reduce must not use or update any state. They must return a value that is dependent only on the argument(s) passed to them. Otherwise, the results will be completely screwed up when you try to run the whole thing in parallel.

---

After getting most frustrated with either very long waffley or very short vague blog posts I eventually discovered this very good rigorous concise paper.

Then I went ahead and made it more concise by translating into Scala, where I've provided the simplest case where a user simply just specifies the map and reduce parts of the application. In Hadoop/Spark, strictly speaking, a more complex model of programming is employed that require the user to explicitly specify 4 more functions outlined here: 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 and/or SQL:

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

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

criticism of MapReduce

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

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

---

Map is a native JS method that can be applied to an array. It creates a new array as a result of some function mapped to every element in the original array. So if you mapped a function(element) { return element * 2;}, it would return a new array with every element doubled. The original array would go unmodified.

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

Reduce is a native JS method that can also be applied to an array. It applies a function to an array and has an initial output value called an accumulator. It loops through each element in the array, applies a function, and reduces them to a single value (which begins as the accumulator). It is useful because you can have any output you want, you just have to start with that type of accumulator. So if I wanted to reduce something into an object, I would start with an accumulator {}.

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

---

MapReduce:

To run something large, we can use computation power of different computer in our office. Difficult part is to split task among different computers.It is done by MapReduce library.

The basic idea is that you divide the job into two parts: a Map, and a Reduce. Map basically takes the problem, splits it into sub-parts, and sends the sub-parts to different machines – so all the pieces run at the same time. Reduce takes the results from the sub-parts and combines them back together to get a single answer.

Input is a list of records.Result of the map computation is a list of key/value pairs. Reduce takes each set of values that has the same key, and combines them into a single value.You can’t tell whether the job was split into 100 pieces or 2 pieces; the end result looks pretty much like the result of a single map.

Please looks at simple map and reduce program:

Map function is used to apply some function on our original list and a new list is hence generated. The map() function in Python takes in a function and a list as argument. A new list is returned by applying function to each item of list.

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

The reduce() function in Python takes in a function and a list as argument. The function is called with a lambda function and a list and a new reduced result is returned. This performs a repetitive operation over the pairs of the list.

#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

참고URL : https://stackoverflow.com/questions/388321/what-is-map-reduce