?

Log in

No account? Create an account
Map, Filter, Reduce: the Cliff Notes version. - Adventures in Engineering — LiveJournal
The wanderings of a modern ronin.

Ben Cantrick
  Date: 2007-02-05 18:14
  Subject:   Map, Filter, Reduce: the Cliff Notes version.
Public

A vast number computer algorithms can be expressed in terms of map, filter, and reduce operations.

* Map takes a list and a function and transforms each value by applying the function to each value.

* Filter takes a list and a predicate function (i.e. a function which returns a boolean value) and returns a new list containing only values for which the predicate returns false.

* Reduce takes a list and an associative function which combines two elements to produce a new value. The function is applied consecutively to values in the list pairwise until a single value is reached.

All three functions can be easily implemented in parallel. This observation forms the basis of the Google map-reduce project.


http://cdiggins.com/2007/01/14/the-map-filter-reduce-paradigm/


Previously.
Post A Comment | 7 Comments | | Link






Ben Cantrick
  User: mackys
  Date: 2007-02-06 04:18 (UTC)
  Subject:   (no subject)
The "map" operator in Perl (and I'm fairly sure in Ruby) originally came from Lisp. Which is, in fact, where a lot of this ""map filter reduce" stuff came from.

Turing complete, easily parallelizing... sounds like someone could write a compiler to transform nearly anything into very fast code using MFR operations at runtime.

Yeah! Guess what LISPers have know since the 60s!
Reply | Parent | Thread | Link



  User: nickhalfasleep
  Date: 2007-02-06 04:31 (UTC)
  Subject:   (no subject)
So will the LISP be the language of the future for massively parallel processors?

I better stock up on parenthesis.
Reply | Parent | Thread | Link



Ben Cantrick
  User: mackys
  Date: 2007-02-06 06:01 (UTC)
  Subject:   (no subject)
So will the LISP be the language of the future for massively parallel processors?


AHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHH!!!!!


AHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHH!!!!!!!!!!!!


RUUUUUNNNNNNNNNNNNN!!!!
Reply | Parent | Thread | Link



  User: nickhalfasleep
  Date: 2007-02-06 04:30 (UTC)
  Subject:   (no subject)
I think reduce is a method of summation that can be broken down.
Reply | Parent | Thread | Link



  User: nickhalfasleep
  Date: 2007-02-06 06:06 (UTC)
  Subject:   (no subject)
I wonder at what level this should get attacked at, e.g. if you have massively parallel processors sitting in a rack of likewise, and you want to use them all, does this dictate a different sort of Operating System? Computer language? In short, what is the best way to write one "program" and have parts of it executing across multiple systems? I need to read the fraking google paper one of these days...
Reply | Thread | Link



Ben Cantrick
  User: mackys
  Date: 2007-02-06 07:35 (UTC)
  Subject:   (no subject)
Distributed Systems is a huge topic, and I doubt the single Google paper will be able to give you a good grounding in all of it. FWIW, both teapot and I tend to favor the use of lightweight serialization and simple message passing to implement parallelism. However, this method is often overkill, and though the overhead incurred is not large, it is often more than what's strictly necessary for single program and/or simple applications. (Java has some rather nice built-in serialization facillities, BTW. If you want to know why Java RMI is so much easier and cleaner than >gag< CORBA, that's one reason why.)
Reply | Parent | Thread | Link



browse
May 2015