DistributedPentomino.java
上传用户:quxuerui
上传日期:2018-01-08
资源大小:41811k
文件大小:7k
源码类别:

网格计算

开发平台:

Java

  1. /**
  2.  * Licensed to the Apache Software Foundation (ASF) under one
  3.  * or more contributor license agreements.  See the NOTICE file
  4.  * distributed with this work for additional information
  5.  * regarding copyright ownership.  The ASF licenses this file
  6.  * to you under the Apache License, Version 2.0 (the
  7.  * "License"); you may not use this file except in compliance
  8.  * with the License.  You may obtain a copy of the License at
  9.  *
  10.  *     http://www.apache.org/licenses/LICENSE-2.0
  11.  *
  12.  * Unless required by applicable law or agreed to in writing, software
  13.  * distributed under the License is distributed on an "AS IS" BASIS,
  14.  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  15.  * See the License for the specific language governing permissions and
  16.  * limitations under the License.
  17.  */
  18. package org.apache.hadoop.examples.dancing;
  19. import java.io.*;
  20. import java.util.List;
  21. import java.util.StringTokenizer;
  22. import org.apache.hadoop.conf.Configuration;
  23. import org.apache.hadoop.conf.Configured;
  24. import org.apache.hadoop.fs.FileSystem;
  25. import org.apache.hadoop.fs.Path;
  26. import org.apache.hadoop.io.Text;
  27. import org.apache.hadoop.io.WritableComparable;
  28. import org.apache.hadoop.mapred.*;
  29. import org.apache.hadoop.mapred.lib.IdentityReducer;
  30. import org.apache.hadoop.util.*;
  31. /**
  32.  * Launch a distributed pentomino solver.
  33.  * It generates a complete list of prefixes of length N with each unique prefix
  34.  * as a separate line. A prefix is a sequence of N integers that denote the 
  35.  * index of the row that is choosen for each column in order. Note that the
  36.  * next column is heuristically choosen by the solver, so it is dependant on
  37.  * the previous choice. That file is given as the input to
  38.  * map/reduce. The output key/value are the move prefix/solution as Text/Text.
  39.  */
  40. public class DistributedPentomino extends Configured implements Tool {
  41.   /**
  42.    * Each map takes a line, which represents a prefix move and finds all of 
  43.    * the solutions that start with that prefix. The output is the prefix as
  44.    * the key and the solution as the value.
  45.    */
  46.   public static class PentMap extends MapReduceBase
  47.     implements Mapper<WritableComparable, Text, Text, Text> {
  48.     
  49.     private int width;
  50.     private int height;
  51.     private int depth;
  52.     private Pentomino pent;
  53.     private Text prefixString;
  54.     private OutputCollector<Text, Text> output;
  55.     private Reporter reporter;
  56.     
  57.     /**
  58.      * For each solution, generate the prefix and a string representation
  59.      * of the solution. The solution starts with a newline, so that the output
  60.      * looks like:
  61.      * <prefix>,
  62.      * <solution>
  63.      * 
  64.      */
  65.     class SolutionCatcher 
  66.     implements DancingLinks.SolutionAcceptor<Pentomino.ColumnName> {
  67.       public void solution(List<List<Pentomino.ColumnName>> answer) {
  68.         String board = Pentomino.stringifySolution(width, height, answer);
  69.         try {
  70.           output.collect(prefixString, new Text("n" + board));
  71.           reporter.incrCounter(pent.getCategory(answer), 1);
  72.         } catch (IOException e) {
  73.           System.err.println(StringUtils.stringifyException(e));
  74.         }
  75.       }
  76.     }
  77.     
  78.     /**
  79.      * Break the prefix string into moves (a sequence of integer row ids that 
  80.      * will be selected for each column in order). Find all solutions with
  81.      * that prefix.
  82.      */
  83.     public void map(WritableComparable key, Text value,
  84.                     OutputCollector<Text, Text> output, Reporter reporter
  85.                     ) throws IOException {
  86.       this.output = output;
  87.       this.reporter = reporter;
  88.       prefixString = value;
  89.       StringTokenizer itr = new StringTokenizer(prefixString.toString(), ",");
  90.       int[] prefix = new int[depth];
  91.       int idx = 0;
  92.       while (itr.hasMoreTokens()) {
  93.         String num = itr.nextToken();
  94.         prefix[idx++] = Integer.parseInt(num);
  95.       }
  96.       pent.solve(prefix);
  97.     }
  98.     
  99.     @Override
  100.     public void configure(JobConf conf) {
  101.       depth = conf.getInt("pent.depth", -1);
  102.       width = conf.getInt("pent.width", -1);
  103.       height = conf.getInt("pent.height", -1);
  104.       pent = (Pentomino) 
  105.         ReflectionUtils.newInstance(conf.getClass("pent.class", 
  106.                                                   OneSidedPentomino.class), 
  107.                                     conf);
  108.       pent.initialize(width, height);
  109.       pent.setPrinter(new SolutionCatcher());
  110.     }
  111.   }
  112.   
  113.   /**
  114.    * Create the input file with all of the possible combinations of the 
  115.    * given depth.
  116.    * @param fs the filesystem to write into
  117.    * @param dir the directory to write the input file into
  118.    * @param pent the puzzle 
  119.    * @param depth the depth to explore when generating prefixes
  120.    */
  121.   private static void createInputDirectory(FileSystem fs, 
  122.                                            Path dir,
  123.                                            Pentomino pent,
  124.                                            int depth
  125.                                            ) throws IOException {
  126.     fs.mkdirs(dir);
  127.     List<int[]> splits = pent.getSplits(depth);
  128.     PrintStream file = 
  129.       new PrintStream(new BufferedOutputStream
  130.                       (fs.create(new Path(dir, "part1")), 64*1024));
  131.     for(int[] prefix: splits) {
  132.       for(int i=0; i < prefix.length; ++i) {
  133.         if (i != 0) {
  134.           file.print(',');          
  135.         }
  136.         file.print(prefix[i]);
  137.       }
  138.       file.print('n');
  139.     }
  140.     file.close();
  141.   }
  142.   
  143.   /**
  144.    * Launch the solver on 9x10 board and the one sided pentominos.
  145.    * This takes about 2.5 hours on 20 nodes with 2 cpus/node.
  146.    * Splits the job into 2000 maps and 1 reduce.
  147.    */
  148.   public static void main(String[] args) throws Exception {
  149.     int res = ToolRunner.run(new Configuration(), new DistributedPentomino(), args);
  150.     System.exit(res);
  151.   }
  152.   public int run(String[] args) throws Exception {
  153.     JobConf conf;
  154.     int depth = 5;
  155.     int width = 9;
  156.     int height = 10;
  157.     Class<? extends Pentomino> pentClass;
  158.     if (args.length == 0) {
  159.       System.out.println("pentomino <output>");
  160.       ToolRunner.printGenericCommandUsage(System.out);
  161.       return -1;
  162.     }
  163.     
  164.     conf = new JobConf(getConf());
  165.     width = conf.getInt("pent.width", width);
  166.     height = conf.getInt("pent.height", height);
  167.     depth = conf.getInt("pent.depth", depth);
  168.     pentClass = conf.getClass("pent.class", OneSidedPentomino.class, Pentomino.class);
  169.     
  170.     Path output = new Path(args[0]);
  171.     Path input = new Path(output + "_input");
  172.     FileSystem fileSys = FileSystem.get(conf);
  173.     try {
  174.       FileInputFormat.setInputPaths(conf, input);
  175.       FileOutputFormat.setOutputPath(conf, output);
  176.       conf.setJarByClass(PentMap.class);
  177.       
  178.       conf.setJobName("dancingElephant");
  179.       Pentomino pent = ReflectionUtils.newInstance(pentClass, conf);
  180.       pent.initialize(width, height);
  181.       createInputDirectory(fileSys, input, pent, depth);
  182.    
  183.       // the keys are the prefix strings
  184.       conf.setOutputKeyClass(Text.class);
  185.       // the values are puzzle solutions
  186.       conf.setOutputValueClass(Text.class);
  187.       
  188.       conf.setMapperClass(PentMap.class);        
  189.       conf.setReducerClass(IdentityReducer.class);
  190.       
  191.       conf.setNumMapTasks(2000);
  192.       conf.setNumReduceTasks(1);
  193.       
  194.       JobClient.runJob(conf);
  195.       } finally {
  196.       fileSys.delete(input, true);
  197.     }
  198.     return 0;
  199.   }
  200. }