는 무엇입 맵/감소?
https://stackoverflow.com/questions/388321
-
23-08-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russian문제
나는에 대해 많이 들 맵/감소,특히의 컨텍스트에서 Google 의 방대한 병렬 컴퓨팅 시스템입니다.정확히 무엇입니까?
해결책
에서 추상적인 구글의 MapReduce 연구 출판 페이지:
MapReduce 프로그래밍 모델 관련된 구현 처리고 큰 생성 데이터 설정합니다.사용자가 지정한 지도 기능 는 프로세스를 키/값 쌍 해 생성된 중간체 키/값 쌍으로,그리고 줄어 기능 병합하는 모든 중간값 와 관련된 중급 키입니다.
의 장점 MapReduce 는 처리를 수행할 수 있습에서 동시에 여러 개의 처리 노드(여러 서버)그래서 시스템을 확장할 수 있습니다.
이후 그것의 기초에서 프로그래밍 모델 map 고 reduce 단계는 각각 없는 부작용(국가 및 결과에서는 각 하위 섹션의 map 프로세스에 의존하지 않는 다른),그렇게 데이터 세트 매핑되는 감소할 수 있는 각 분리되는 여러 가공 노드입니다.
요엘의 할 수 있는 프로그래밍 언어 이렇게 할까요? 조각는 방법에 대해 이해 기능적인 프로그래밍에 필수적인 구글 올 MapReduce,는 능력을 검색 엔진입니다.그것은 매우 좋은 읽기 당신에 익숙하지 않은 기능적인 프로그래밍 및 어떻게 허용한 확장 가능한 코드입니다.
도 참조하십시오: Wikipedia:MapReduce
관련 질문: 설명하십시오 mapreduce 단순히
다른 팁
그것은 내가 할 수있는 것보다 더 잘 설명합니다. 도움이 되나요?
맵은 목록의 모든 항목에 다른 함수를 적용하여 모든 반환 값이있는 다른 목록을 생성하는 함수입니다. ( "x에 f를 적용"하는 또 다른 방법은 "call 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 친구이고 Joel Spolsky는 엉터리 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#에서 READ는 호출됩니다 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#에서 동등한 타입 안전은 다음과 같습니다.
string commaSeparatedNames = names.Aggregate((a, b) => a + ", " + b);
이것이 왜 "쿨"인가? 더 큰 계산을 작은 조각으로 나누는 간단한 방법은 다른 방식으로 다시 모을 수 있으며 항상 시원합니다. Google 이이 아이디어를 적용하는 방식은 여러 컴퓨터를 통해 맵과 감소를 모두 공유 할 수 있기 때문에 병렬화입니다.
그러나 핵심 요구 사항은 귀하의 언어가 기능을 값으로 취급 할 수 있다는 것이 아닙니다. 모든 OO 언어는 그렇게 할 수 있습니다. 병렬화에 대한 실제 요구 사항은 작은 것입니다 func 지도에 전달하고 감소하는 기능은 상태를 사용하거나 업데이트해서는 안됩니다. 그들은 그들에게 전달 된 인수에만 의존하는 값을 반환해야합니다. 그렇지 않으면 모든 것을 병렬로 실행하려고 할 때 결과가 완전히 망가집니다.
매우 긴 Waffley 또는 매우 짧은 모호한 블로그 게시물로 가장 실망한 후 결국 이것을 발견했습니다. 아주 좋은 간결한 종이.
그런 다음 스칼라로 번역하여 더 간결하게 만들었습니다. 여기서 사용자는 단순히 단순히 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
}
MAP는 배열에 적용 할 수있는 기본 JS 메소드입니다. 원래 배열의 모든 요소에 맵핑 된 일부 기능의 결과로 새 배열을 만듭니다. 따라서 함수 (element) {return element * 2;}를 매핑하면 모든 요소가 두 배가 된 새 배열을 반환합니다. 원래 배열은 수정되지 않습니다.
https://developer.mozilla.org/en-us/docs/web/javascript/reference/global_objects/array/map
Reduce는 배열에도 적용 할 수있는 기본 JS 방법입니다. 기능을 배열에 적용하고 Accumulator라는 초기 출력 값을 갖습니다. 배열의 각 요소를 루프하고 함수를 적용하여 단일 값 (축합기로 시작)으로 줄입니다. 원하는 출력을 가질 수 있기 때문에 유용합니다. 해당 유형의 축합기부터 시작하면됩니다. 따라서 무언가를 물체로 줄이고 싶다면 축합기 {}로 시작합니다.
https://developer.mozilla.org/en-us/docs/web/javascript/reference/global_objects/array/reduce?v=a
MapReduce :
큰 것을 실행하려면 사무실에서 다른 컴퓨터의 계산 전력을 사용할 수 있습니다. 어려운 부분은 다른 컴퓨터로 작업을 분할하는 것입니다. MapReduce 라이브러리에서 수행됩니다.
기본 아이디어는 작업을 맵과 축소의 두 부분으로 나누는 것입니다. 맵은 기본적으로 문제를 해결하고 하위 부분으로 나누고 하위 부분을 다른 기계로 보냅니다. 따라서 모든 조각이 동시에 실행됩니다. 감소는 하위 파트의 결과를 가져 와서 다시 결합하여 단일 답을 얻습니다.
입력은 레코드 목록입니다. 맵 계산의 result는 키/값 쌍의 목록입니다. 감소는 동일한 키를 갖는 각 값 세트를 가져 와서 단일 값으로 결합합니다. 작업이 100 조각 또는 2 조각으로 나뉘 었는지 알 수 없습니다. 최종 결과는 단일 맵의 결과와 거의 비슷합니다.
간단한지도를보고 프로그램을 줄이십시오.
MAP 함수는 원래 목록에 일부 기능을 적용하는 데 사용되며 새 목록이 생성됩니다. Python의 map () 함수는 함수와 목록을 인수로 취합니다. 각 목록 항목에 함수를 적용하여 새 목록이 반환됩니다.
li = [5, 7, 4, 9]
final_list = list(map(lambda x: x*x , li))
print(final_list) #[25, 49, 16, 81]
Python의 Reduce () 함수는 함수와 목록을 인수로 취합니다. 함수는 Lambda 함수와 목록으로 호출되며 새로운 감소 결과가 반환됩니다. 이것은 목록의 쌍보다 반복적 인 작업을 수행합니다.
#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
