решение проблемы с уменьшением карты

Question

Я хочу смоделировать в ruby ​​мою реализацию функций map и reduce для системы, подобной hadoop, чтобы убедиться, что идея работает по крайней мере.

У меня следующая проблема.У меня есть два списка элементов:

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

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

Мне нужно создать общий список, который включает в себя сумму чисел, связанных с алфавитами, общими в двух списках:

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

Iчтобы решить эту проблему, нужно создать скрипт ruby ​​с операциями map и reduce.Я не уверен, как решить эту проблему или какую процедуру выполнить, чтобы смоделировать это в скрипте ruby.

Любая помощь приветствуется.

Answer 1

Использование irb (ruby-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} 

это решение работает с несколькими массивами (2+), находит общие ключи и суммирует их, возвращая хэш результатов

найти общие ключи (собрать ключи и найти общую часть):

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

найти сумму для ключа (выбрать значения по ключам и суммировать их):

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

для построенияХеш из массива пар [[:a,9], [:b,4]]:

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

Мне нравится рубин для этого лайнера!

Answer 2

Предполагая, что у нас реализованы все другие функции, связанные с уменьшением карты (считыватель ввода, запись вывода, глобальная сортировка, ...), это будут map и 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

Функция map создаст yield пару (letter, count), которая будет сгруппирована позже. Тогда для каждого letter, полученного от map s reduce, будет получен массив, содержащий каждое число, полученное map для этого letter. Поскольку вы хотите уступить только в том случае, если буква встречается в обоих хешах, нам нужно, чтобы count s дважды появлялся в partial_counts, чтобы использовать ее для вычисления суммы в конце. Функция reduce может быть реализована несколькими способами. Я попытался сделать его как можно более простым для понимания, хотя его реализация очень приспособлена к этой проблеме.

Использование этих реализаций map и reduce вернет последний хеш с инвертированными ключами и значением, что более логично, так как может быть несколько букв с одинаковым количеством. Ввод будет лучше, если он перевернет ключи и значения тоже. Таким образом, map будет так же просто, как получить каждую пару (letter, count):

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

или

def map(input)
  input.each do |i|
    yield i
  end
end

Answer 3

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"]

В этом коде используются методы map и reduce Ruby, но делать все это непосредственно с помощью Hash было бы намного элегантнее.

Answer 4

Вы можете попробовать, учитывая элементы, приведенные в MapReduce Статья в Википедии:

• считыватель ввода - в вашем случае это, вероятно, вызов метода для пары [key, value] из ваших входных хэшей.
• функция Map - у вас уже есть ключи, с помощью которых вы должны обрабатывать свои данные, поэтому ваш map работник просто вернет пару [key, value], которую он получил в качестве ввода
• функция разбиения - метод, который назначает сокращающий рабочий на основе ключа. В вашем случае это может быть просто key.hash % REDUCER_COUNT.
• функция сравнения - я не думаю, что это применимо в вашем случае, так как вам не нужно обрабатывать значения в каком-то конкретном порядке.
• a Функция уменьшения - будет дана пара [key, list], список представляет собой список значений, связанных с ключом. Она будет возвращать сумму list, если список имеет длину более одного элемента (поскольку вы хотите, чтобы в обоих входных хешах обрабатывались только элементы).
• выходной писатель - может быть простой Hash в вашем примере.

И вот моя (более) упрощенная реализация вышеприведенного.