Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Write your first MapReduce program in 20 minutes

michaelnielsen.org

Post reply on HN
Print view View original

11–16 of 16 posts

Re: Write your first MapReduce program in 20 minutes

#11

Post by Dn_Ab »

wedesoft wrote: post #2

And here's the equivalent Ruby program. In Ruby it is usually 'collect' and 'inject' instead of 'map' and 'reduce'. result = Dir.glob('test?.txt').collect do |file_name| File.new(file_name, 'r').read.split(' ').collect do |word| word.downcase.tr '.,\'', '' end.inject Hash.new(0) do |hash,word| hash[word] += 1 hash end end.inject do |all,hash| (all.keys + hash.keys).uniq.inject Hash.new(0) do |acc,word| acc[word] = al…

If i understand correctly collect is more like map from functional programing languages and inject is a fold. One maps a collection of one type to a collection of another type, and the other reduces a collection of one type into something of another type (which could be a collection itself) in that case MapReduce does not quite translate to ruby's collect and inject. In fancy language the reduce in MapReduce is not merely a catamorphism nor is the map actually a collect. The types do not align. I learned of his from a hackernews post by grav1tas http://news.ycombinator.com/item?id=2477238. In there he links to a paper: http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.104....

If you look at the types implicit in his code you should see that the essence lies not with collect or inject which are incidental plumbing but the nature of the hash and in particular, the act of generating the intermediate collection for each key. What is called map is actually more a reverse reduce. The pedagogical emphasis on map and foldr actually belies the true nature and power of algorithm in parallelizing.

Re: Write your first MapReduce program in 20 minutes

#12

Post by [deleted] »

wedesoft wrote: post #2

And here's the equivalent Ruby program. In Ruby it is usually 'collect' and 'inject' instead of 'map' and 'reduce'. result = Dir.glob('test?.txt').collect do |file_name| File.new(file_name, 'r').read.split(' ').collect do |word| word.downcase.tr '.,\'', '' end.inject Hash.new(0) do |hash,word| hash[word] += 1 hash end end.inject do |all,hash| (all.keys + hash.keys).uniq.inject Hash.new(0) do |acc,word| acc[word] = al…

[deleted]

Re: Write your first MapReduce program in 20 minutes

#13

Post by [deleted] »

wedesoft wrote: post #2

And here's the equivalent Ruby program. In Ruby it is usually 'collect' and 'inject' instead of 'map' and 'reduce'. result = Dir.glob('test?.txt').collect do |file_name| File.new(file_name, 'r').read.split(' ').collect do |word| word.downcase.tr '.,\'', '' end.inject Hash.new(0) do |hash,word| hash[word] += 1 hash end end.inject do |all,hash| (all.keys + hash.keys).uniq.inject Hash.new(0) do |acc,word| acc[word] = al…

[deleted]

Re: Write your first MapReduce program in 20 minutes

#14

Post by peteretep »

wedesoft wrote: post #2

And here's the equivalent Ruby program. In Ruby it is usually 'collect' and 'inject' instead of 'map' and 'reduce'. result = Dir.glob('test?.txt').collect do |file_name| File.new(file_name, 'r').read.split(' ').collect do |word| word.downcase.tr '.,\'', '' end.inject Hash.new(0) do |hash,word| hash[word] += 1 hash end end.inject do |all,hash| (all.keys + hash.keys).uniq.inject Hash.new(0) do |acc,word| acc[word] = al…

Here's a Perl implementation:

  use strict; use warnings;
  use List::Util  qw(reduce);
  use File::Slurp qw(read_file);

  sub word_count {
  	reduce { $a->{$b}++; $a  } {},
  	map    { split(/\W+/)    }
  	map    { lc read_file $_ } @_;
  }

Re: Write your first MapReduce program in 20 minutes

#15

Post by strmpnk »

wedesoft wrote: post #2

And here's the equivalent Ruby program. In Ruby it is usually 'collect' and 'inject' instead of 'map' and 'reduce'. result = Dir.glob('test?.txt').collect do |file_name| File.new(file_name, 'r').read.split(' ').collect do |word| word.downcase.tr '.,\'', '' end.inject Hash.new(0) do |hash,word| hash[word] += 1 hash end end.inject do |all,hash| (all.keys + hash.keys).uniq.inject Hash.new(0) do |acc,word| acc[word] = al…

Kind of a odd example just to use map/reduce where each works just fine:

    result = Hash.new(0)
    Dir['test?.txt'].each do |file|
      File.read(file).split(' ').each {|word|
        result[word.downcase.tr('.,\'', '')] += 1}
    end
If you really needed map/reduce here you'd probably want to write it this way:

    Dir['test?.txt'].map do |file|
      Hash.new(0).tap {|result|
        File.read(file).split(' ').each {|word|
          result[word.downcase.tr('.,\'', '')] += 1}}
    end.reduce do |result, partial|
      result.merge(partial) {|k, v1, v2| v1 + v2}
    end

Re: Write your first MapReduce program in 20 minutes

#16

Post by wedesoft »

strmpnk wrote: post #15
wedesoft wrote: post #2

And here's the equivalent Ruby program. In Ruby it is usually 'collect' and 'inject' instead of 'map' and 'reduce'. result = Dir.glob('test?.txt').collect do |file_name| File.new(file_name, 'r').read.split(' ').collect do |word| word.downcase.tr '.,\'', '' end.inject Hash.new(0) do |hash,word| hash[word] += 1 hash end end.inject do |all,hash| (all.keys + hash.keys).uniq.inject Hash.new(0) do |acc,word| acc[word] = al…

Kind of a odd example just to use map/reduce where each works just fine: result = Hash.new(0) Dir['test?.txt'].each do |file| File.read(file).split(' ').each {|word| result[word.downcase.tr('.,\'', '')] += 1} end If you really needed map/reduce here you'd probably want to write it this way: Dir['test?.txt'].map do |file| Hash.new(0).tap {|result| File.read(file).split(' ').each {|word| result[word.downcase.tr('.,\'',…

Interesting. I didn't know that you could pass a block to merge.
Post reply on HN