Okay last time we talked about map 
reduce, and gave the abstraction and went 
through some examples and we ended up on 
this slide which is, maybe the first time 
we've seen pseudo-code or any kind of 
code that actually implements these map 
and reduce functions, and so I asked you 
to just sort of take a look at this. 
actually the end of the last segment 
there are a couple of changes, mistakes 
that I fixed in this slide so you can 
compare the two to see if you can figure 
out what the mistakes are and why I 
changed them. 
So, let's walk through this. 
So what is this code? 
Do well as I sort of gave away last time, 
this implements this word count 
application that we went through 
schematically you know with cartoons and 
you know this is the psuedo code that 
actually implements that. 
Or you know an example of pseudo code 
that could be that could implement that. 
You can't execute this code since it is 
just Pseudo-code. 
So, what are we looking at here? 
Well, the input, as we said, the data 
model of MapReduce is key value pairs and 
so, the input is going to be a big set of 
key value pairs. 
And the Map function is going to operate 
on one of these key value pairs. 
And in this case, the key is the document 
name and the value is the document 
contents. 
So it could be a big string. 
Right it's maybe it comes from PDF file 
or a text file, or a webpage or whatever. 
Okay, and so this code is pretty simple. 
It says well for each word w in the input 
value, so this sort of assumes some how 
you can iterate over all the words in 
the, in the input value in the text of 
the document, without really specifying 
how. 
Then emit a key value pair where the key 
is this first element. 
Which is the word and the value is the 
number one. 
Okay, then, the majic shuffle phase takes 
over. 
And groups all the key value pairs that 
have, that share the same key into a 
single group. 
And so all the occurrences of a 
particular word will show up as a group. 
And how that group is represented is as a 
key along with. 
What we've called here an iterator, over 
the intermediate values. 
And if you're not familiar with the term 
iterator, you can think of it as just a 
collection of values. 
Okay. 
So as an example here we have the word. 
You know, the map function will produce, 
pairs like this. 
Every time it sees the word history in 
any document it'll produce this. 
And then finally, on the reduced side 
you'll have the word history here. 
And a sequence of, number ones. 
Okay. 
And so what is this code do? 
Well, it initializes the final result to 
zero. 
And it says, for each value in this list 
of intermediate values, add that value to 
the result. 
And so here we just add them all up. 
And then finally, we admit a final key 
value pair which is the intermediate key, 
the word itself. 
In the final result. 
And so maybe the output here is, you 
know, history 25. 
And we walk through this a couple 
different times. 
I hope this is pretty clear by now. 
Now, I calim that without changing this 
reduce function at all You could make a 
change to this map function and get a 
significantly faster algorithm for 
computing this. 
So I want you to think for a second how 
that might be done. 
So the thing to look at here is that, oh 
goodness We're emitting a key value pair. 
Let me stop resting my hand on this. 
We're emitting a key value pair 1s for 
every occurrence of a particular word. 
And each one of these key value pairs has 
to be shuffled across the network. 
And sent to the, sent to the reducer. 
So if we see the word, history, 25 times 
in a single document. 
We're going to emit 25 key value pairs 
for that word. 
And they're all going to be grouped up by 
the shuffle phase. 
But we have access to the entire document 
here in the map. 
In the, in this map function. 
So why not precount all the occurrences 
of those words. 
And produce a different key value pair. 
Right? 
Which means the word history appeared 25 
times in this particular document on 
processing. 
And so now actually I meant to say 25. 
Sorry, that's confusing. 
That's confusing, I didn't mean to make 
this the same number as this. 
this is, you know, in our previous 
formulation of this problem, it turned 
out that we, we are, we said that the 
word history appeared 25 times across all 
documents, and I shouldn't use the same 
number up here, because that's, that's 
That's pretty confusing so let me change 
so here we say that the word history 
appears 5 times in this particular 
document, and it appears other times in 
other documents. 
Okay. 
So now we have only one key value pair 
emerging from this document. 
For the word history as opposed to five 
different ones. 
And overall, across all the documents, 
across all the computers being applied to 
this problem, that's a significant 
savings. 
Okay. 
And then, you know double check to make 
sure you don't have to change this code 
here, but you, know, you, hopefully it's 
clear that you don't because you're 
adding the total value into the result. 
And so here, instead of adding the number 
one, 25, or sorry, five times. 
Well sorry 25 times I guess in the, in 
the reduced side. 
Your adding it some number fewer times. 
Right, you're adding 5 plus 10 plus plus 
3 plus 4 and so on to get 25. 
Okay, so this loop it is valuated fewer 
times. 
Okay, So the reason I want to go through 
that example is To demonstrate that, you 
know. 
There, there's two things. 
One is to try to think in terms of map 
reduce and think about how you can cast a 
problem as operating on a bunch of 
chunks. 
Emitting keys to, to define groups and 
then operating on those groups. 
But also that you know, you actually have 
a lot of control over the performance of 
these algorithms by just modifying the 
map and reduced functions. 
Alright, so even though you aren't 
working on the system internals you only 
have these two points of control. 
You can actually get very different 
algorithms, very different behavior and 
different amount of intermediate results 
being created and so on. 
Just when these two, two functions. 
And so you want to get a feel for not 
just how to express it in map reduce 
naively, but also get a feel for how to 
do things reasonably efficiently. 
And in fact, this example sort of 
demonstrates one of the things you're 
going to be looking for is the bottleneck 
often, not always, is the amount of data 
going across the network. 
And so if you can reduce the. 
amount of output produced by the mappers, 
especially in terms of number of key 
value pairs. 
You'll tend to improve performance, again 
not always. 
And we'll see some more examples of this. 
Okay. 
So I'm going to s, stop there, and in the 
next segment we'll go through a variation 
of this problem. 
That cha, that has similar 
characteristics. 
But really just to drive home how to 
design these ma, ma, map produced 
algorithms on slightly variant problems.