Re: [Boost-users] [mapreduce] Prim Calculator

Subject: Re: [Boost-users] [mapreduce] Prim Calculator
From: Craig Henderson (cdm.henderson_at_[hidden])
Date: 2009-08-20 18:09:23

> Hi Craig, I did my best in translating the is_prime problem into a
> map_reduce solution. The problem is simple: Find all prime numbers for
> a given range of numbers, for instance, 0...1,000. Below is the source
> code that I came up with. I cannot attach files from my work, so,
> please excuse the bad formatting.
> 
> The map function takes a number and emits a key/value pair of (
> size_t, number ). The size_t key basically states weather or not a the
> number is prime. I don't quite understand how do the reduce function?
> I can see that in your word count example you accumulate the same
> words to calculate the count. What I want is to pushing back the prime
> numbers into a vector that I can print out at the end of program.

The generic form of Map/Reduce maps a key/value pair k1,v1 to a list of
key/value pairs k2,v2. The reduce then takes a group of v2 values for each
unique key k2 and produces a final list of v2

map    (k1, v1)       --> list(k2,v2)
reduce (k2, list(v2)) --> list(v2)

Your input is a list of unique integers, k1, and v1 is unused. Map emits
intermediates where k2 is 0 or 1, indicating prime or not prime and v2 is
the number (copied from k1). The Reduce function should then emit v2 if k2
is 1 and do nothing if k2 is 0. This will result in the final dataset
containing prime numbers.

i.e.
map(1,2,3,4,5,6) --> ((1,1), (1,2), (1,3), (0,4), (1,5), (0,6))
reduce(1, (1,2,3,5)) --> (1,2,3,5)
reduce(0, (4,6)) --> null

I'll take a look at your code tomorrow and try and supply you a working
example. If you get it working in the meantime, let me know.

Regards
-- Craig