hadoop-common-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From szets...@apache.org
Subject svn commit: r711472 - in /hadoop/core/trunk: CHANGES.txt src/examples/org/apache/hadoop/examples/PiEstimator.java
Date Tue, 04 Nov 2008 23:37:39 GMT
Author: szetszwo
Date: Tue Nov  4 15:37:39 2008
New Revision: 711472

URL: http://svn.apache.org/viewvc?rev=711472&view=rev
Log:
HADOOP-4437. Use Halton sequence instead of java.util.Random in PiEstimator.  (szetszwo)

Modified:
    hadoop/core/trunk/CHANGES.txt
    hadoop/core/trunk/src/examples/org/apache/hadoop/examples/PiEstimator.java

Modified: hadoop/core/trunk/CHANGES.txt
URL: http://svn.apache.org/viewvc/hadoop/core/trunk/CHANGES.txt?rev=711472&r1=711471&r2=711472&view=diff
==============================================================================
--- hadoop/core/trunk/CHANGES.txt (original)
+++ hadoop/core/trunk/CHANGES.txt Tue Nov  4 15:37:39 2008
@@ -55,6 +55,9 @@
 
     HADOOP-3461. Remove hdfs.StringBytesWritable. (szetszwo)
 
+    HADOOP-4437. Use Halton sequence instead of java.util.Random in PiEstimator.
+    (szetszwo)
+
   OPTIMIZATIONS
 
   BUG FIXES

Modified: hadoop/core/trunk/src/examples/org/apache/hadoop/examples/PiEstimator.java
URL: http://svn.apache.org/viewvc/hadoop/core/trunk/src/examples/org/apache/hadoop/examples/PiEstimator.java?rev=711472&r1=711471&r2=711472&view=diff
==============================================================================
--- hadoop/core/trunk/src/examples/org/apache/hadoop/examples/PiEstimator.java (original)
+++ hadoop/core/trunk/src/examples/org/apache/hadoop/examples/PiEstimator.java Tue Nov  4
15:37:39 2008
@@ -19,8 +19,8 @@
 package org.apache.hadoop.examples;
 
 import java.io.IOException;
+import java.math.BigDecimal;
 import java.util.Iterator;
-import java.util.Random;
 
 import org.apache.hadoop.conf.Configuration;
 import org.apache.hadoop.conf.Configured;
@@ -46,17 +46,78 @@
 import org.apache.hadoop.util.ToolRunner;
 
 /**
- * A Map-reduce program to estimaate the valu eof Pi using monte-carlo
- * method.
+ * A Map-reduce program to estimate the value of Pi
+ * using quasi-Monte Carlo method.
  */
 public class PiEstimator extends Configured implements Tool {
   
+  /** 2-dimensional Halton sequence {H(i)},
+   * where H(i) is a 2-dimensional point and i >= 1 is the index. 
+   */
+  private static class HaltonSequence {
+    /** Bases */
+    static final int[] P = {2, 3}; 
+    /** Maximum number of digits allowed */
+    static final int[] K = {63, 40}; 
+
+    private long index;
+    private double[] x;
+    private double[][] q;
+    private int[][] d;
+
+    /** Initialize to H(startindex),
+     * so the sequence begins with H(startindex+1).
+     */
+    HaltonSequence(long startindex) {
+      index = startindex;
+      x = new double[K.length];
+      q = new double[K.length][];
+      d = new int[K.length][];
+      for(int i = 0; i < K.length; i++) {
+        q[i] = new double[K[i]];
+        d[i] = new int[K[i]];
+      }
+
+      for(int i = 0; i < K.length; i++) {
+        long k = index;
+        x[i] = 0;
+        
+        for(int j = 0; j < K[i]; j++) {
+          q[i][j] = (j == 0? 1.0: q[i][j-1])/P[i];
+          d[i][j] = (int)(k % P[i]);
+          k = (k - d[i][j])/P[i];
+          x[i] += d[i][j] * q[i][j];
+        }
+      }
+    }
+
+    /** Compute next point.
+     * Assume the current point is H(index).
+     * Compute H(index+1).
+     */
+    double[] nextPoint() {
+      index++;
+      for(int i = 0; i < K.length; i++) {
+        for(int j = 0; j < K[i]; j++) {
+          d[i][j]++;
+          x[i] += q[i][j];
+          if (d[i][j] < P[i]) {
+            break;
+          }
+          d[i][j] = 0;
+          x[i] -= (j == 0? 1.0: q[i][j-1]);
+        }
+      }
+      return x;
+    }
+  }
+
   /**
    * Mappper class for Pi estimation.
    */
   
   public static class PiMapper extends MapReduceBase
-    implements Mapper<LongWritable, Writable, LongWritable, LongWritable> {
+    implements Mapper<LongWritable, LongWritable, LongWritable, LongWritable> {
     
     /** Mapper configuration.
      *
@@ -65,8 +126,6 @@
     public void configure(JobConf job) {
     }
     
-    static Random r = new Random();
-    
     long numInside = 0L;
     long numOutside = 0L;
     
@@ -77,15 +136,17 @@
      * @param reporter
      */
     public void map(LongWritable key,
-                    Writable val,
+                    LongWritable val,
                     OutputCollector<LongWritable, LongWritable> out,
                     Reporter reporter) throws IOException {
-      long nSamples = key.get();
+      final HaltonSequence haltonsequence = new HaltonSequence(key.get());
+      final long nSamples = val.get();
+
       for(long idx = 0; idx < nSamples; idx++) {
-        double x = r.nextDouble();
-        double y = r.nextDouble();
-        double d = (x-0.5)*(x-0.5)+(y-0.5)*(y-0.5);
-        if (d > 0.25) {
+        final double[] point = haltonsequence.nextPoint();
+        final double x = point[0] - 0.5;
+        final double y = point[1] - 0.5;
+        if (x*x + y*y > 0.25) {
           numOutside++;
         } else {
           numInside++;
@@ -105,7 +166,7 @@
   }
   
   public static class PiReducer extends MapReduceBase
-    implements Reducer<LongWritable, LongWritable, WritableComparable, Writable> {
+    implements Reducer<LongWritable, LongWritable, WritableComparable<?>, Writable>
{
     
     long numInside = 0;
     long numOutside = 0;
@@ -126,7 +187,7 @@
      */
     public void reduce(LongWritable key,
                        Iterator<LongWritable> values,
-                       OutputCollector<WritableComparable, Writable> output,
+                       OutputCollector<WritableComparable<?>, Writable> output,
                        Reporter reporter) throws IOException {
       if (key.get() == 1) {
         while (values.hasNext()) {
@@ -159,7 +220,7 @@
    * This is the main driver for computing the value of Pi using
    * monte-carlo method.
    */
-  double launch(int numMaps, long numPoints, String jt, String dfs)
+  BigDecimal launch(int numMaps, long numPoints, String jt, String dfs)
     throws IOException {
 
     JobConf jobConf = new JobConf(getConf(), PiEstimator.class);
@@ -199,13 +260,12 @@
       Path file = new Path(inDir, "part"+idx);
       SequenceFile.Writer writer = SequenceFile.createWriter(fileSys, jobConf, 
                                                              file, LongWritable.class, LongWritable.class,
CompressionType.NONE);
-      writer.append(new LongWritable(numPoints), new LongWritable(0));
+      writer.append(new LongWritable(idx * numPoints), new LongWritable(numPoints));
       writer.close();
       System.out.println("Wrote input for Map #"+idx);
     }
     
-    double estimate = 0.0;
-    
+    BigDecimal estimate = BigDecimal.ZERO;
     try {
       System.out.println("Starting Job");
       long startTime = System.currentTimeMillis();
@@ -219,7 +279,11 @@
       LongWritable numOutside = new LongWritable();
       reader.next(numInside, numOutside);
       reader.close();
-      estimate = (numInside.get()*4.0)/(numMaps*numPoints);
+
+      estimate = BigDecimal.valueOf(4).setScale(20)
+          .multiply(BigDecimal.valueOf(numInside.get()))
+          .divide(BigDecimal.valueOf(numMaps))
+          .divide(BigDecimal.valueOf(numPoints));
     } finally {
       fileSys.delete(tmpDir, true);
     }



Mime
View raw message