MapReduce
- Algorithms course
- Expert
- Lesson 35/41
- 4 min
Distributed computing with MapReduce.
MapReduce
MapReduce is a programming model for processing large data on distributed clusters. It has three stages: map, shuffle and reduce.
The map stage transforms each input piece into (key, value) pairs. The shuffle stage groups pairs with the same key to the same worker. The reduce stage aggregates each group.
This model is widely used for word count, inverted index and log analysis tasks.
Shuffle and reduce
The shuffle stage groups all (key, value) pairs from the map output by key. All values with the same key are sent to the same reduce worker.
The reduce stage aggregates each group; for example, in word count it sums the values. This separation enables parallel execution in a distributed setting.
Page ranking, inverted index and statistical computation fit this structure easily.
Practice mapreduce_count function
Write mapreduce_count(documents). Map each document's words to (word, 1) pairs and count them. Return a sorted list of (word, count) pairs. Print [('armut', 1), ('elma', 3), ('muz', 1)] with print(mapreduce_count(['elma elma armut', 'elma muz'])).
Starter code
def mapreduce_count(documents):
# Word count with MapReduceSample solution
def mapreduce_count(documents):
# Word count with MapReduce
mapped = []
for doc in documents:
for word in doc.split():
mapped.append((word, 1))
counts = {}
for word, one in mapped:
counts[word] = counts.get(word, 0) + one
return sorted(counts.items())
print(mapreduce_count(['elma elma armut', 'elma muz']))Expected output
[('armut', 1), ('elma', 3), ('muz', 1)]
Questions and answers
Review the lesson questions together with their answers. To test yourself, solve the lesson interactively.
1 map output
for word in doc.____():
mapped.append((word, 1))for word in doc.split():
mapped.append((word, 1))Explanation: split() breaks the string into words.
2 MapReduce concepts
| Term | Meaning |
|---|---|
map |
Produces (key, value) |
shuffle |
Groups same keys |
reduce |
Aggregates |
big data |
Distributed cluster |
3 What does the reduce stage do?
for word, one in mapped:
counts[word] = counts.get(word, 0) + one- It sorts the data
- It splits the data
- It aggregates values with the same key Correct answer
- It filters the data
Explanation: Reduce aggregates values with the same key.