S’il vous plaît expliquer MapReduce simplement

Question

Liés à ma question de CouchDB ...

Quelqu'un peut-il expliquer MapReduce en termes que pourrait comprendre un numbnuts ?

Answer 1

Aller tout le chemin vers les bases pour la Map et reduce.

---

La carte est une fonction qui "transforme" les éléments dans une sorte de liste à un autre type de point et de les replacer dans le même genre de liste.

supposons que j'ai une liste de nombres: [1,2,3] et je veux doubler chaque numéro, dans ce cas, la fonction de "double chaque nombre" est la fonction x = x * 2. Et sans mappages, je pourrais écrire une boucle simple, disons

A = [1, 2, 3]
foreach (item in A) A[item] = A[item] * 2

et j'aurais Un = [2, 4, 6] mais au lieu d'écrire des boucles, si j'ai une carte de fonction je pourrais écrire

A = [1, 2, 3].Map(x => x * 2)

x => x * 2 est une fonction qui doit être exécutée contre les éléments dans [1,2,3]. Ce qui se passe est que le programme prend chaque élément, exécuter (x => x * 2) par x est égal à chaque élément, et de produire une liste de résultats.

1 : 1 => 1 * 2 : 2  
2 : 2 => 2 * 2 : 4  
3 : 3 => 3 * 2 : 6  

ainsi, après l'exécution de la fonction map (x => x * 2), vous avez de l' [2, 4, 6].

---

Réduire est une fonction qui "rassemble" les éléments de listes et d'effectuer quelques calculs sur tous les d'eux, et donc de la réduire à une seule valeur.

Trouver une somme ou trouver les moyennes sont toutes les instances d'une fonction de réduction. Comme si vous avez une liste de nombres, de dire [7, 8, 9] et vous voulez résumer, vous devez écrire une boucle comme ceci

A = [7, 8, 9]
sum = 0
foreach (item in A) sum = sum + A[item]

Mais, si vous avez accès à une fonction de réduction, vous pouvez l'écrire comme ceci

A = [7, 8, 9]
sum = A.reduce( 0, (x, y) => x + y )

Maintenant c'est un peu déroutant pourquoi il y a 2 arguments (0 et la fonction avec x et y). Pour une fonction de réduction pour être utile, elle doit être en mesure de prendre 2 éléments, de calculer, de quelque chose et de le "réduire" que les 2 éléments à une seule valeur, ainsi que le programme pourrait réduire chaque paire jusqu'à ce que nous avons qu'une seule valeur.

l'exécution suit:

result = 0
7 : result = result + 7 = 0 + 7 = 7
8 : result = result + 8 = 7 + 8 = 15
9 : result = result + 9 = 15 + 9 = 24

Mais vous ne voulez pas commencer avec des zéros de tous les temps, de sorte que le premier argument est là pour vous permettre de spécifier une valeur de semences spécifiquement de la valeur du premier result = ligne de.

dites que vous voulez une somme de 2 listes, il pourrait ressembler à ceci:

A = [7, 8, 9]
B = [1, 2, 3]
sum = 0
sum = A.reduce( sum, (x, y) => x + y )
sum = B.reduce( sum, (x, y) => x + y )

ou une version que vous auriez plus de chances de trouver dans le monde réel:

A = [7, 8, 9]
B = [1, 2, 3]

sum_func = (x, y) => x + y
sum = A.reduce( B.reduce( 0, sum_func ), sum_func )

---

C'est une bonne chose dans une DB logiciel, parce que, avec la Carte\Réduire le soutien que vous pouvez travailler avec la base de données sans avoir besoin de savoir comment les données sont stockées dans une base de données pour l'utiliser, c'est ce qu'un moteur de base de données.

Vous avez juste besoin d'être en mesure de "dire" le moteur de ce que vous voulez, par la fourniture de avec soit une Carte ou d'une fonction de réduction et puis le moteur DB pourrait trouver son chemin autour de la data, appliquer votre fonction, et de venir avec les résultats que vous voulez sans vous savoir comment il passe en boucle sur tous les enregistrements.

Il existe des index et clés et les jointures et les points de vue et beaucoup de choses d'une base de données unique pourrait tenir, donc, par le blindage contre la façon dont les données sont stockées, votre code plus facile à écrire et à maintenir.

En va de même pour la programmation parallèle, si vous ne spécifiez ce que vous voulez faire avec les données au lieu de réellement mettre en œuvre le code de boucle, puis de l'infrastructure sous-jacente pourrait "paralléliser" et l'exécution de votre fonction dans un parallèle simultanée boucle pour vous.

Answer 2

MapReduce est une méthode pour traiter des sommes énormes de données en parallèle, sans obliger le développeur à écrire aucun code autre que le mappeur et de réduire les fonctions.

La carte en fonction des données et produit un résultat. qui est détenu dans une barrière. Cette fonction peut s'exécuter en parallèle avec un grand nombre de la même carte de la tâche. Le jeu de données peut alors être réduite à une valeur scalaire.

Donc, si vous pensez à elle comme une instruction SQL

SELECT SUM(salary)
FROM employees
WHERE salary > 1000
GROUP by deptname

Nous pouvons utiliser la carte pour obtenir notre sous-ensemble d'employés avec un salaire > 1000 la carte émet de la barrière de la taille du groupe des seaux.

Réduire fera le bilan de chacun de ces groupes. Vous donner vos résultats.

juste pincées cela à partir de mon université, l'étude des notes de google de papier

Answer 3

Joel Spolsky a une bonne explication pour les débutants - http://www.joelonsoftware.com/items/2006/08/01.html

Answer 4

1. Prenez un tas de données
2. Effectuer une sorte de transformation qui convertit chaque donnée à un autre type de donnée
3. Combiner ces nouvelles données dans encore plus simple de données

L'étape 2 est de la Carte. L'étape 3 est de Réduire.

Par exemple,

1. Le temps entre deux impulsions sur une paire de pression de mètres sur la route
2. La carte de ces moments dans la vitesse en fonction de la distance des compteurs
3. Réduire les vitesses à la vitesse moyenne

La raison MapReduce est divisé entre la Carte et de Réduire la raison en est que les différentes parties peuvent facilement être réalisés en parallèle. (Surtout si Réduire a certaines propriétés mathématiques.)

Pour un complexe, mais une bonne description de MapReduce, voir: Google du Modèle de Programmation MapReduce -- Revisité (PDF).

Answer 5

CARTE et RÉDUIRE sont anciennes fonctions Lisp.

Imaginez que vous avez une liste de villes avec des informations sur le nom, le nombre de personnes qui y vivent et la taille de la ville:

(defparameter *cities*
  '((a :people 100000 :size 200)
    (b :people 200000 :size 300)
    (c :people 150000 :size 210)))

Maintenant, vous pouvez trouver la ville avec la plus forte densité de population.

Nous avons d'abord créer une liste de noms de ville et de la densité de la population à l'aide de la CARTE:

(map 'list
     (lambda (city)
         (list (first city)
               (/ (getf (rest city) :people)
                  (getf (rest city) :size))))
     *cities*)

=>   ((A 500) (B 2000/3) (C 5000/7))

Aide à RÉDUIRE nous pouvons maintenant trouver de la ville avec la plus forte densité de population.

(reduce (lambda (a b)
          (if (> (second a) (second b))
             a
             b))
        '((A 500) (B 2000/3) (C 5000/7)))

 =>   (C 5000/7)

En combinant les deux parties nous obtenons le code suivant:

(reduce (lambda (a b)
          (if (> (second a) (second b))
             a
             b))
        (map 'list
             (lambda (city)
                (list (first city)
                   (/ (getf (rest city) :people)
                      (getf (rest city) :size))))
             *cities*))

Nous allons introduire des fonctions:

(defun density (city)
   (list (first city)
         (/ (getf (rest city) :people)
            (getf (rest city) :size))))

(defun max-density (a b)
   (if (> (second a) (second b))
          a
          b))

Ensuite, nous pouvons écrire notre CARTE de RÉDUIRE le code comme:

(reduce 'max-density
        (map 'list 'density *cities*))

 =>   (C 5000/7)