hadoop处女秀之蒙特卡洛算法

序，

   《Hadoop In Action》里开始就推荐从观摩hadoop自带的example起步，于是走马观花的看一遍sample，里面竟然有个Dancing Link的分布式版本。当看到有一个MonteCarlo求Pi的源文件时，觉得有必要去复习一下MonteCarlo的原理。于是跑去看了一下这个随机算法的思路，看完觉着学习还是自己动手来的好，于是先不去看sample自己试着实现一下，因为这个算法很简单。不过，由于不熟悉Hadoop编程模型和IO套路甚至数据类型，又是自己操刀的第一个hadoop程序，就这样摸黑上路了，中间走了很多弯路，摘记如下。

一 原理

    MonteCarlo算法是通过特定区域的随机样本点和总的样本点的比率来求一些值的，最经典的应用就是求Pi，单位圆的面积公式S1 = π，单位正方形面积 S2 = 1。二者的关系是，单位圆的1/4正好落在单位正方形内，利用面积比率可以求出π值。

二 实现

    实现很简单，用随机数模拟抛点，然后求得落在扇形和正方形内点的比率即可。具体实现可以给用户提供2个选项，一个是指定模拟点数，另一个是指定精度。点数越大，精度越大，程序花费的时间也随着增加，他们是彼此正相关。显然，蒙特卡洛是计算密集型的算法，适合分布到集群上来并行模拟抛点过程（当然，集群越大越好，否则体现不出集群的优势）。
    实现过程碰到很多坑，其实是自己对hadoop不够熟练的缘故。首先是参数读入的方式，采用了最传统的文件读入。其实hadoop也可以支持参数读入；其次是指定map的输入类型，刚开始文件格式是只有一列输出，结果总也读不成功。经过多次试错的愚蠢方式，最后文件格式采用了多余列，第二列纯粹是占坑用的，map里没用到这列。同时map的中间输出格式也采用了多余列，文件的键统一采用了同一个名字，而把正方形内的点M和落在扇形内的点N拼成一个M-N形式的字符串整体作为值（为什么采用这么疼的方式，因为自定义hadoop的中间输出格式还不会，另一个是如果总点数M和扇形内点数N分别作为键和值，那么reduce是不能正确工作的），然后到reduce里再对拼接的字符串进行解析，因为键是统一的，这时候就可以分别拿出总点数M和N进行汇总计算，然后输出模拟计算出来的π值。思路还是比较清晰的，最掣肘的地方还是hadoop不熟，否则代码就不会丑到爆了。
no code I say a bird：

import java.util.Random;
import java.lang.Math;
import java.lang.Number;
import java.lang.String;
import java.io.IOException;
import java.util.Iterator;

import org.apache.hadoop.conf.Configuration;
import org.apache.hadoop.conf.Configured;
import org.apache.hadoop.io.LongWritable;
import org.apache.hadoop.io.NullWritable;
import org.apache.hadoop.io.DoubleWritable;
import org.apache.hadoop.io.Text;
import org.apache.hadoop.fs.Path;
import org.apache.hadoop.mapred.FileInputFormat;
import org.apache.hadoop.mapred.FileOutputFormat;
import org.apache.hadoop.mapred.JobClient;
import org.apache.hadoop.mapred.JobConf;
import org.apache.hadoop.mapred.MapReduceBase;
import org.apache.hadoop.mapred.Mapper;
import org.apache.hadoop.mapred.Reducer;
import org.apache.hadoop.mapred.SequenceFileInputFormat;
import org.apache.hadoop.mapred.TextInputFormat;
import org.apache.hadoop.mapred.KeyValueTextInputFormat;
import org.apache.hadoop.mapred.OutputCollector;
import org.apache.hadoop.mapred.Reporter;
import org.apache.hadoop.util.Tool;
import org.apache.hadoop.util.ToolRunner;

/*
 * take file as input, the second column in the input file is unused.
 * MonteCarlo V1.0
 */
public class MonteCarlo extends Configured implements Tool {
    public static boolean inCircle(double x, double y) {
        if (x * x + y * y <= 1.0) {
            return true;
        }
        return false;
    }

    public static class MapC extends MapReduceBase
            implements Mapper {
            final static long RAND_MAX = (1L << 63) - 1;
            public void map(Text val, Text ignore, OutputCollector output, Reporter rep) throws IOException {
                double x, y;
                long sum = Long.parseLong(val.toString());
                long in_circle_dot = 0;
                Random rand = new Random();
                for (long i = 0; i < sum; ++ i) {
                    x = Math.abs((double)(rand.nextLong() * 1.0 / RAND_MAX));
                    y = Math.abs((double)(rand.nextLong() * 1.0 / RAND_MAX));
                    if (inCircle(x, y)) {
                        ++ in_circle_dot;
                    }
                }
                String res = String.valueOf(sum);
                res += "-";
                res += String.valueOf(in_circle_dot);
                //output.collect(new LongWritable(Long.parseLong(val.toString())), new LongWritable(in_circle_dot));
                output.collect(new Text("arvinpeng"), new Text(res));
            }
    }

    public static class ReduceC extends MapReduceBase
            implements Reducer {
            public void reduce(Text key, Iterator itr, OutputCollector output, Reporter rep) throws IOException {
                double total = 0.0;
                double in_circle = 0.0;
                while(itr.hasNext()) {
                    String tmp = String.valueOf(itr.next());
                    String[] tmp2 = tmp.split("-");
                    total += Double.parseDouble(tmp2[0]);
                    in_circle += Double.parseDouble(tmp2[1]);
                }
                double pi = in_circle * 4.0;
                if (total == 0.0) {
                    pi = -1;
                } else {
                    pi /= total;
                }
                output.collect(new Text("Pi"), new DoubleWritable(pi));
            }
    }

    static int printUsage() {
        System.out.println("MonteCarlo [-m ] [-r ]  
");
        ToolRunner.printGenericCommandUsage(System.out);
        return -1;
    }
    public int run(String[] args) throws Exception {
        if (args.length != 2) {
            return printUsage();
        }
        Configuration conf = getConf();
        JobConf job = new JobConf(conf, MonteCarlo.class);
        Path in = new Path(args[0]);
        Path out = new Path(args[1]);
        FileInputFormat.setInputPaths(job, in);
        FileOutputFormat.setOutputPath(job, out);
        job.setJobName("MonteCarLo Get Pi");
        job.setMapperClass(MapC.class);
        job.setReducerClass(ReduceC.class);
        //job.setInputFormat(TextInputFormat.class);
        job.setInputFormat(KeyValueTextInputFormat.class);
        job.setMapOutputKeyClass(Text.class);
        job.setMapOutputValueClass(Text.class);
        job.setOutputKeyClass(Text.class);
        job.setOutputValueClass(DoubleWritable.class);
        job.set("key.value.separator.in.input.line", ",");
        //job.setNumReduceTasks(0);

        JobClient.runJob(job);
        return 0;
    }

    public static void main(String[] args) throws Exception {
        int ret = ToolRunner.run(new Configuration(), new MonteCarlo(), args);
        System.exit(ret);
    }
}

输入数据【无脑乱写，-1列无用】：
100000000,-1
4000000,-1
100000000,-1

中间输出格式[没有对中间文件输出，所以这里N为YY出来的，你认真我就输了]：
arvinpeng 100000000-43423242
arvinpeng 4000000-832212
arvinpeng 100000000-653424

输出数据【不太理想啊老师】：
Pi      3.1415851764705884

三，总结

   Hadoop使用熟练的话，还是很好的呢。

（啊咧，结尾也太牵强了点吧魂淡）