MapReduce Reducer Assignment

From CSE231 Wiki
Jump to navigation Jump to search

credit for this assignment: Finn Voichick and Dennis Cosgrove

Motivation

interface AccumulatorCombinerReducer<V,A,R> is fundamental to the MapReduce assignments, providing four of the five methods which allow clients to well use interface MapReduceFramework<E,K,V,A,R>.

First, we will implement abstract class ClassicReducer<V,R> which will provide the basic MapReduce functionality used by the PageRank algorithm which made Google's original search engine so effective.

Then, we will implement two AccumulatorCombinerReducers which can serve to sum mutable containers of Integers. Thus, they will pair well with the previous Mappers exercise.

Background

The Java streams framework uses interface Collector<T,A,R> to allow clients to customize the four methods to create, accumulate, combine, and reduce. interface Collector<T,A,R> chose to add an extra level of indirection to allow a hyper-lambdafication style. While there is nothing fundamentally wrong with this approach, it was eventually deemed more trouble than it was worth for CSE 231s. To learn more about Collector and its connection to AccumulatorCombinerReducer, check out this Rosetta Stone.

interface AccumulatorCombinerReducer<V,A,R>

AccumulatorCombinerReducer<V, A, R>  
public interface AccumulatorCombinerReducer<V, A, R> {
	A createMutableContainer();

	void accumulate(A container, V item);

	void combine(A containerA, A containerB);

	R reduce(A container);
}

createMutableContainer()

We use createMutableContainer() to create a new mutable container. For classic map reduce this would be a List<V>.

accumulate(container,item)

We use accumulate(container,item) to accumulate a value. For classic map reduce this would add an item to a list.

combine(containerA,containerB)

We use combine(containerA,containerB) to combine two accumulated mutable containers. You must combine containerB into containerA.

reduce(container)

We use reduce(container) to produce the distilled value of the container.

Code To Use

List<E>

class ArrayList<E>
class LinkedList<E>

class MutableInt

Code To Implement

ListAccumulatingReducer

The classic MapReduce Collector will collect all of the emitted values in a List.

class: ListAccumulatingReducer.java Java.png
methods: createMutableContainer
accumulate
combine
package: mapreduce.apps.reducer.listaccumulating.exercise
source folder: student/src/main/java

method: List<V> createMutableContainer() Sequential.svg (sequential implementation only)

method: void accumulate(List<V> container, V item) Sequential.svg (sequential implementation only)

method: List<V> combine(List<V> containerA, List<V> containerB) Sequential.svg (sequential implementation only)

IntSumListAccumulatingReducer

class: IntSumListAccumulatingReducer.java Java.png
methods: reduce
package: mapreduce.apps.reducer.listaccumulating.intsum.exercise
source folder: student/src/main/java

method: public Integer reduce(List<Integer> container) Sequential.svg (sequential implementation only)

The reduce method is passed a list of integers which it should simply sum up and return.

Efficient Summing Int

MapReduce Apps like Word Count offer glaring opportunities to optimize the classic MapReduce append all of the 1s in a List and add them up later. SummingIntEfficientAccumulatorCombinerReducer will use MutableInt to simply add the values as they come in.

class: SummingIntEfficientAccumulatorCombinerReducer.java Java.png
methods: createMutableContainer
accumulate
accumulate
reduce
package: mapreduce.apps.reducer.summingint.efficient.exercise
source folder: student/src/main/java

method: MutableInt createMutableContainer() Sequential.svg (sequential implementation only)

method: void accumulate(MutableInt container, Integer item) Sequential.svg (sequential implementation only)

method: void combine(MutableInt containerA, MutableInt containerB) Sequential.svg (sequential implementation only)

method: reduce(MutableInt container) Sequential.svg (sequential implementation only)

Testing Your Solution

Note: in order to effectively assess this assignment, the testing leverages the WordCountMapper. Be sure to correctly complete that assignment first.

class: _AccumulatorCombinerReducerTestSuite.java Junit.png
package: mapreduce.apps
source folder: testing/src/test/java