2011-04-10 31 views
8

Quiero simular en ruby ​​mi implementación de las funciones map y reduce para un sistema como hadoop para verificar que la idea funcione al menos.resolver un problema con el mapa reducir

Tengo el siguiente problema. Tengo dos listas de elementos:

List1 
3 - A 
4 - B 
5 - C 
7 - D 
8 - F 

List2 
2 - A 
8 - B 
6 - C 
9 - D 
4 - E 

Tengo que construir una lista común que incluye la suma de los números asociados con los alfabetos comunes en las dos listas:

commonList 
5 - A 
12 - B 
11 - C 
16 - D 

Quiero hacer una ruby script con las operaciones map y reduce para resolver este problema. No estoy seguro de cómo abordar este problema o qué procedimiento seguir para simular esto en un script de ruby.

Cualquier ayuda apreciada.

Respuesta

2

usted podría tratar teniendo en cuenta los elementos que figuran en el artículo MapReduce Wikipedia:

  • un lector de entrada - en su caso esto sería probablemente una llamada de método en [key, value] par de sus valores hash de entrada.
  • una función Mapa - que ya tiene teclas que debe estar procesando los datos mediante, por lo que su trabajador map simplemente devolvería el par [key, value] se puso como una entrada
  • una función de partición - un método que asignar un trabajador reducir basadas en la llave En su caso, podría ser simplemente key.hash % REDUCER_COUNT.
  • a compare function - No creo que esto sea aplicable en su caso, ya que no necesita valores para ser procesados ​​en un orden en particular.
  • a Reducir función - se le daría [key, list] par, lista que es una lista de valores asociados con la clave. Devolvería la suma de list si la lista tiene más de un elemento de longitud (ya que solo desea que se procesen los elementos que aparecen en los dos hashes de entrada).
  • una grabadora de salida: podría ser Hash simple en su ejemplo.

Y here's my (over) implementación simplificada de lo anterior.

+0

Estoy intentando su solución, pero obtengo un error con esta línea: [key, list.inject (&: +)]. Aparece el siguiente error: "TypeError: tipo de argumento incorrecto Symbol (Proc esperado)" – Flethuseo

+0

Probablemente estés usando Ruby antiguo. Use 'list.inject {| acc, i | acc + i} 'en su lugar. –

2

Suponiendo que tenemos todas las otras funciones relacionadas MapReduce-implementadas (lector de entrada, de salida escritor, más o menos global, ...), estos serían los map y los reduce:

def map(input) 
    input.each do |count, letter| 
    yield [letter, count] 
    end 
end 

def reduce(letter, partial_counts) 
    result = if partial_counts.size == 2 
    partial_counts[0] + partial_counts[1] 
    end 

    yield result 
end 

El map función será yield un par (letter, count), que se agruparán más tarde. Luego, por cada letter recibido de map s reduce recibirá una matriz que contiene cada cuenta producida por un map para ese letter. Como desea ceder solo si la letra aparece en ambos hash, necesitamos count s para que aparezca en partial_counts dos veces para usarla para calcular la suma al final. La función reduce podría implementarse de varias maneras. Intenté que sea lo más simple posible de entender, aunque su implementación está muy ajustada a este problema.

El uso de estos map y reduce devolverá el último hash con las teclas y el valor invertido, lo que tiene más sentido, ya que puede haber varias letras con el mismo recuento. La entrada sería mejor si también invirtiera claves y valores. De esta manera, map sería tan simple como dando cada par de (letter, count):

def map(input) 
    input.each do |letter, count| 
    yield [letter, count] 
    end 
end 

o

def map(input) 
    input.each do |i| 
    yield i 
    end 
end 
2
list_1 = ["3 - A", "4 - B", "5 - C", "7 - D", "8 - F"] 

list_2 = ["2 - A", "8 - B", "6 - C", "9 - D", "4 - E"] 

(list_1 + list_2).map do |str| 
    # change array of strings to array in the form of [[name, value], ...] 
    str =~ /(\d+) - (.*)/ && [$2, $1.to_i] 
end.reduce({}) do |memo, obj| 
    # use a temporary Hash to sum up the values; 
    # the value is an array in the form of [value_counter, iteration_counter] 
    prev = memo[obj.first] || [0, 0] 
    memo[obj.first] = [prev.first + obj.last, prev.last + 1] 
    memo 
end.map do |key, value| 
    # convert to array in original format or 
    # nil, if occurred only once 
    value.last > 1 ? "#{key} - #{value.first}" : nil 
end.compact 

=> ["A - 5", "B - 12", "C - 11", "D - 16"] 

Este código utiliza el map y reduce métodos de Ruby, pero haciendo todo esto directamente en un Hash sería mucho más elegante.

2

Uso de IRB (rubí-1.9.2-p180):

list = [ {a:2, b:1, d:3}, {a:3, b:2, c:3}, {a:4, b:1, c:3} ] 
=> [{:a=>2, :b=>1, :d=>3}, {:a=>3, :b=>2, :c=>3}, {:a=>4, :b=>1, :c=>3}] 

Hash[list.map(&:keys).inject(&:&).map{|key| [key,list.map{|arr| arr[key]}.inject(&:+)]}] 
=> {:a=>9, :b=>4} 

esta solución funciona con múltiples matrices (2 +) se encuentra claves comunes y los resume devolver un hash de los resultados

a encontrar las claves comunes (recoger las llaves y encontrar parte común):

list.map(&:keys).inject(&:&) 

para encontrar la suma para la clave (seleccione los valores de las teclas y la suma de ellos):

list.map{|arr| arr[key]}.inject(&:+)] 

para construir Hash de matriz de pares [[:a,9], [:b,4]]:

results = [[:a,9], [:b,4]] 
Hash[ results ] 

Me encanta rubí para este forros uno!

Cuestiones relacionadas