Je pense que Trouver des Amis via la carte de réduire peut être un puissant exemple pour comprendre le concept, et
un bien utilisé de cas d'utilisation.
Personnellement, trouvé ce lien très utile.
http://stevekrenzel.com/finding-friends-with-mapreduce
EDIT:
Aussi, wikipédia a un article intéressant expliquant ce qu' map-reduce est
La copie de l'explication fournie dans le blog (Dans le cas où le lien est périmé)
Trouver Des Amis
MapReduce est un framework développé à l'origine par Google qui permet de faire facilement à grande échelle de calcul distribué à travers un certain nombre de domaines. Apache Hadoop est une implémentation open source.
Je vais brillant sur les détails, mais il revient à la définition de deux fonctions: une fonction de mappage et d'une fonction de réduction. La fonction map prend une valeur et sorties de la clé:des paires de valeurs. Par exemple, si nous définissons une carte de fonction qui prend une chaîne et sorties de la longueur de la parole comme la clé et le mot lui-même que la valeur de la carte(steve) serait de retour 5:steve et carte de savannah) serait de retour 8:savannah. Vous avez peut-être remarqué que la fonction map est apatride et ne requiert que la valeur d'entrée pour calculer la valeur de sortie. Cela nous permet d'exécuter la fonction map contre des valeurs en parallèle et offre un énorme avantage. Avant d'arriver à la fonction de réduction, le mapreduce cadre des groupes de toutes les valeurs par clé, donc si des fonctions de la carte de sortie de la clé suivante:valeur de paires:
3 : the
3 : and
3 : you
4 : then
4 : what
4 : when
5 : steve
5 : where
8 : savannah
8 : research
Ils obtiennent regroupées comme:
3 : [the, and, you]
4 : [then, what, when]
5 : [steve, where]
8 : [savannah, research]
Chacune de ces lignes serait alors passé comme argument à la fonction de réduction, qui accepte une clé et d'une liste de valeurs. Dans ce cas, nous avons peut-être essayer de comprendre comment beaucoup de paroles de certaines longueurs existent, de sorte que notre fonction de réduction sera juste de compter le nombre d'éléments dans la liste et de sortie de la clé avec la taille de la liste, comme:
3 : 3
4 : 3
5 : 2
8 : 2
Les réductions peuvent également être réalisés en parallèle, et encore fournir un énorme avantage. On peut alors observer ces résultats définitifs et de voir qu'il n'y avait que deux mots de longueur 5 dans notre corpus, etc...
L'exemple le plus commun de mapreduce est pour compter le nombre de fois où les mots se produire dans un corpus. Supposons que vous ayez une copie de l'internet (j'ai eu la chance de travailler dans une telle situation), et que vous voulez une liste de tous les mots sur l'internet ainsi que combien de fois elle s'est produite.
La façon dont vous le feriez pour cela serait de marquer les documents que vous avez (pause en mots), et de passer chaque mot à un mappeur. Le mappeur serait alors cracher le mot de retour avec une valeur de 1. Le regroupement de la phase prendra toutes les touches (dans ce cas les mots), et de faire une liste de 1. L'réduire la phase prend alors une clé (mot) et une liste (une liste de 1 à chaque fois que la touche est apparu sur l'internet), ainsi que des sommes à la liste. Le réducteur ensuite les sorties de la parole, ainsi que le comte. Quand tout est dit et fait, vous aurez une liste de tous les mots sur l'internet, ainsi que le nombre de fois qu'elle est apparue.
Facile, droit? Si vous avez jamais lu sur mapreduce, le scénario ci-dessus n'est pas quelque chose de nouveau... c'est le "Hello, World" de mapreduce. Voici donc un monde réel de cas d'utilisation (Facebook peut faire ou ne pas faire, c'est juste un exemple):
Facebook a une liste d'amis (notez que les amis sont un bi-directionnelle chose sur Facebook. Si je suis votre ami, vous êtes mine). Ils ont aussi beaucoup d'espace disque et ils servent des centaines de millions de requêtes quotidiennes. Ils ont décidé de pré-calculer les calculs quand ils le peuvent afin de réduire le temps de traitement des demandes. Une commune d'une demande de traitement est le "Vous et Joe ont 230 amis en commun". Lorsque vous consultez le profil d'un participant, vous pouvez voir une liste d'amis que vous avez en commun. Cette liste ne change pas souvent de sorte qu'il serait fastidieux de les recalculer à chaque fois que vous avez visité le profil (bien sûr, vous pourriez utiliser un décent stratégie de mise en cache, mais alors je ne serais pas en mesure de continuer à écrire sur mapreduce pour ce problème). Nous allons utiliser mapreduce afin que nous puissions calculer tous les amis en commun une fois par jour, et de stocker ces résultats. Plus tard, c'est juste une recherche rapide. Nous avons beaucoup d'espace disque, c'est pas cher.
Assumer les amis sont stockés en tant que Personne->[Liste d'Amis], notre liste d'amis est alors:
A -> B C D
B -> A C D E
C -> A B D E
D -> A B C E
E -> B C D
Chaque ligne sera un argument pour un mappeur. Pour chaque ami dans la liste d'amis, le mappeur va sortir une paire clé-valeur. La clé sera d'un ami avec la personne. La valeur de la liste d'amis. Les clés seront triés afin que les amis sont dans l'ordre, à l'origine de toutes les paires d'amis pour aller à la même réducteur. C'est difficile à expliquer avec le texte, il faut juste laisser faire et voir si vous pouvez voir le modèle. Après tout, les cartographes sont faites en cours d'exécution, vous aurez une liste comme ceci:
For map(A -> B C D) :
(A B) -> B C D
(A C) -> B C D
(A D) -> B C D
For map(B -> A C D E) : (Note that A comes before B in the key)
(A B) -> A C D E
(B C) -> A C D E
(B D) -> A C D E
(B E) -> A C D E
For map(C -> A B D E) :
(A C) -> A B D E
(B C) -> A B D E
(C D) -> A B D E
(C E) -> A B D E
For map(D -> A B C E) :
(A D) -> A B C E
(B D) -> A B C E
(C D) -> A B C E
(D E) -> A B C E
And finally for map(E -> B C D):
(B E) -> B C D
(C E) -> B C D
(D E) -> B C D
Before we send these key-value pairs to the reducers, we group them by their keys and get:
(A B) -> (A C D E) (B C D)
(A C) -> (A B D E) (B C D)
(A D) -> (A B C E) (B C D)
(B C) -> (A B D E) (A C D E)
(B D) -> (A B C E) (A C D E)
(B E) -> (A C D E) (B C D)
(C D) -> (A B C E) (A B D E)
(C E) -> (A B D E) (B C D)
(D E) -> (A B C E) (B C D)
Chaque ligne sera passé comme argument à un réducteur. La fonction de réduction sera tout simplement se croisent les listes de valeurs et de sortie de la même clé avec le résultat de l'intersection. Par exemple, réduire((A B) -> (C D E) (B C D)) sortie (B) : (C D) et signifie que les amis de A et de B, C et D comme des amis communs.
Le résultat après réduction est:
(A B) -> (C D)
(A C) -> (B D)
(A D) -> (B C)
(B C) -> (A D E)
(B D) -> (A C E)
(B E) -> (C D)
(C D) -> (A B E)
(C E) -> (B D)
(D E) -> (B C)
Maintenant, lors D visite B du profil, nous pouvons trouver rapidement (B D) et de voir qu'ils ont trois amis en commun, (A C E).
