+/EE360P
distributed systems
git clone https://git.julia.blue/+/EE360P
07ca65d
master
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 19package org .apache .hadoop .examples .dancing ; 20 21import java .io .*; 22import java .util .List ; 23import java .util .StringTokenizer ; 24 25import org .apache .hadoop .conf .Configuration ; 26import org .apache .hadoop .conf .Configured ; 27import org .apache .hadoop .fs .FileSystem ; 28import org .apache .hadoop .fs .Path ; 29import org .apache .hadoop .io .Text ; 30import org .apache .hadoop .io .WritableComparable ; 31import org .apache .hadoop .mapreduce .*; 32import org .apache .hadoop .mapreduce .lib .input .FileInputFormat ; 33import org .apache .hadoop .mapreduce .lib .output .FileOutputFormat ; 34import org .apache .hadoop .util .*; 35 36import com .common .base .Charsets ; 37 38/** 39* Launch a distributed pentomino solver. 40* It generates a complete list of prefixes of length N with each unique prefix 41* as a separate line. A prefix is a sequence of N integers that denote the 42* index of the row that is choosen for each column in order. Note that the 43* next column is heuristically choosen by the solver, so it is dependant on 44* the previous choice. That file is given as the input to 45* map/reduce. The output key/value are the move prefix/solution as Text/Text. 46*/ 47public class DistributedPentomino extends Configured implements Tool { 48 49private static final int PENT_DEPTH =5 ; 50private static final int PENT_WIDTH =9 ; 51private static final int PENT_HEIGHT =10 ; 52private static final int DEFAULT_MAPS =2000 ; 53 54/** 55* Each map takes a line, which represents a prefix move and finds all of 56* the solutions that start with that prefix. The output is the prefix as 57* the key and the solution as the value. 58*/ 59public static class PentMap extends 60Mapper <WritableComparable <?>,Text ,Text ,Text > { 61 62private int width ; 63private int height ; 64private int depth ; 65private Pentomino pent ; 66private Text prefixString ; 67private Context context ; 68 69/** 70* For each solution, generate the prefix and a string representation 71* of the solution. The solution starts with a newline, so that the output 72* looks like: 73* <prefix>, 74* <solution> 75* 76*/ 77class SolutionCatcher 78implements DancingLinks .SolutionAcceptor <Pentomino .ColumnName > { 79public void solution (List <List <Pentomino .ColumnName >>answer ) { 80String board =Pentomino .stringifySolution (width ,height ,answer ); 81try { 82context .write (prefixString ,new Text ("\n" +board )); 83context .getCounter (pent .getCategory (answer )).increment (1 ); 84 }catch (IOException e ) { 85System .err .println (StringUtils .stringifyException (e )); 86 }catch (InterruptedException ie ) { 87System .err .println (StringUtils .stringifyException (ie )); 88 } 89 } 90 } 91 92/** 93* Break the prefix string into moves (a sequence of integer row ids that 94* will be selected for each column in order). Find all solutions with 95* that prefix. 96*/ 97public void map (WritableComparable <?>key ,Text value ,Context context ) 98throws IOException { 99prefixString =value ; 100StringTokenizer itr =new StringTokenizer (prefixString .toString (),"," ); 101int []prefix =new int [depth ]; 102int idx =0 ; 103while (itr .hasMoreTokens ()) { 104String num =itr .nextToken (); 105prefix [idx ++] =Integer .parseInt (num ); 106 } 107pent .solve (prefix ); 108 } 109 110@ Override 111public void setup (Context context ) { 112this .context =context ; 113Configuration conf =context .getConfiguration (); 114depth =conf .getInt (Pentomino .DEPTH ,PENT_DEPTH ); 115width =conf .getInt (Pentomino .WIDTH ,PENT_WIDTH ); 116height =conf .getInt (Pentomino .HEIGHT ,PENT_HEIGHT ); 117pent = (Pentomino ) 118ReflectionUtils .newInstance (conf .getClass (Pentomino .CLASS , 119OneSidedPentomino .class ), 120conf ); 121pent .initialize (width ,height ); 122pent .setPrinter (new SolutionCatcher ()); 123 } 124 } 125 126/** 127* Create the input file with all of the possible combinations of the 128* given depth. 129* @param fs the filesystem to write into 130* @param dir the directory to write the input file into 131* @param pent the puzzle 132* @param depth the depth to explore when generating prefixes 133*/ 134private static long createInputDirectory (FileSystem fs , 135Path dir , 136Pentomino pent , 137int depth 138 )throws IOException { 139fs .mkdirs (dir ); 140List <int []>splits =pent .getSplits (depth ); 141Path input =new Path (dir ,"part1" ); 142PrintWriter file = 143new PrintWriter (new OutputStreamWriter (new BufferedOutputStream 144 (fs .create (input ),64 *1024 ),Charsets .UTF_8 )); 145for (int []prefix :splits ) { 146for (int i =0 ;i <prefix .length ; ++i ) { 147if (i !=0 ) { 148file .',' ); 149 } 150file .prefix [i ]); 151 } 152file .'\n' ); 153 } 154file .close (); 155return fs .getFileStatus (input ).getLen (); 156 } 157 158/** 159* Launch the solver on 9x10 board and the one sided pentominos. 160* This takes about 2.5 hours on 20 nodes with 2 cpus/node. 161* Splits the job into 2000 maps and 1 reduce. 162*/ 163public static void main (String []args )throws Exception { 164int res =ToolRunner .run (new Configuration (), 165new DistributedPentomino (),args ); 166System .exit (res ); 167 } 168 169public int run (String []args )throws Exception { 170Configuration conf =getConf (); 171if (args .length ==0 ) { 172System .out .println ("Usage: pentomino <output> [-depth #] [-height #] [-width #]" ); 173ToolRunner .printGenericCommandUsage (System .out ); 174return 2 ; 175 } 176// check for passed parameters, otherwise use defaults 177int width =conf .getInt (Pentomino .WIDTH ,PENT_WIDTH ); 178int height =conf .getInt (Pentomino .HEIGHT ,PENT_HEIGHT ); 179int depth =conf .getInt (Pentomino .DEPTH ,PENT_DEPTH ); 180for (int i =0 ;i <args .length ;i ++) { 181if (args [i ].equalsIgnoreCase ("-depth" )) { 182depth =Integer .parseInt (args [++i ].trim ()); 183 }else if (args [i ].equalsIgnoreCase ("-height" )) { 184height =Integer .parseInt (args [++i ].trim ()); 185 }else if (args [i ].equalsIgnoreCase ("-width" ) ) { 186width =Integer .parseInt (args [++i ].trim ()); 187 } 188 } 189// now set the values within conf for M/R tasks to read, this 190// will ensure values are set preventing MAPREDUCE-4678 191conf .setInt (Pentomino .WIDTH ,width ); 192conf .setInt (Pentomino .HEIGHT ,height ); 193conf .setInt (Pentomino .DEPTH ,depth ); 194Class <?extends Pentomino >pentClass =conf .getClass (Pentomino .CLASS , 195OneSidedPentomino .class ,Pentomino .class ); 196int numMaps =conf .getInt (MRJobConfig .NUM_MAPS ,DEFAULT_MAPS ); 197Path output =new Path (args [0 ]); 198Path input =new Path (output +"_input" ); 199FileSystem fileSys =FileSystem .get (conf ); 200try { 201Job job =Job .getInstance (conf ); 202FileInputFormat .setInputPaths (job ,input ); 203FileOutputFormat .setOutputPath (job ,output ); 204job .setJarByClass (PentMap .class ); 205 206job .setJobName ("dancingElephant" ); 207Pentomino pent =ReflectionUtils .newInstance (pentClass ,conf ); 208pent .initialize (width ,height ); 209long inputSize =createInputDirectory (fileSys ,input ,pent ,depth ); 210// for forcing the number of maps 211FileInputFormat .setMaxInputSplitSize (job , (inputSize /numMaps )); 212 213// the keys are the prefix strings 214job .setOutputKeyClass (Text .class ); 215// the values are puzzle solutions 216job .setOutputValueClass (Text .class ); 217 218job .setMapperClass (PentMap .class ); 219job .setReducerClass (Reducer .class ); 220 221job .setNumReduceTasks (1 ); 222 223return (job .waitForCompletion (true ) ?0 :1 ); 224 }finally { 225fileSys .delete (input ,true ); 226 } 227 } 228}