高性能计算及大数据测试技术基础题目及解答.doc.docVIP

一、问题及要求 现有100G大小文本文件，字符串之间以空格分隔，设计一个解决方案输出文本中出现频率最高的字符串。 要求采用课程中涉及到的大数据框架，在这里我采用MapReduce分布式计算模型。并考虑解决方案的算法复杂度和时间复杂度。 二、详细思路 该方案基本的解决思路很直观，简而言之：将文本文件内容切分成字符串，将其中相同的字符串聚集在一起，统计其数量作为该字符串出现的次数输出，最后输出出现频率最高的字符串。下述详细思路： 针对MapReduce并行程序设计原则可知，解决方案中的内容切分步骤和数据不相关，可以并行化处理，每个拿到原始数据的机器只要将输入数据切分成字符串就可以。所以在map阶段完成单词切分任务。另外，相同单侧的频数并行化处理。根据此实例，不同单词的频数不相关，故可以将相同单词交给一台机器来计算频数，然后输出最终结果，这个过程是reduce阶段完成。而至于中间结果根据不同单词分组再分发给reduce机器，这是MapReduce过程中的shuffle能够完成的。 总的来说：map阶段对大量数据进行扫描，对每个数据做处理，完成由输入数据到字符串切分的工作。shuffle阶段完成相关单词的聚集和分发工作，排序和整理中间结果以利后续处理。reduce阶段完成接收所有单词并计算其频数的工作，完成最终结果输出。 三、算法流程 1.将输入的文本文件拆分成字符串。 2.用map函数处理上述拆分数据，对每个单词生成键值对。 3.shuffle：合并map函数输出的所有键值对，并根据键分组、排序。 4.将中间结果发送给reduce函数，由reduce函数产生最终输出。 下用MapReduce算法画一流程图： 测试 伪代码 Mapper实现代码如下：该类map方法调用默认的LineRecordReader，得到的value值为文本文件中的一行，key值为甘航首字符相对于文本文件首地址的偏移量，StringTokenizer类将value值拆分成一个个单词。 //继承mapper接口，设置map输入类型object,Text,输出类型Text,IntWriteable Public static class TokenizerMapper extends MapperObject,Text,Text,IntWritable { private final static IntWritable one=new IntWritable(1); Private Text word=new Text(); Public void map(Object key,Text value,Context context) throws IOException,InterruptedException { Stringtokenizer itr=new StringTokenizer(value.toString()); While(itr,hasMoreTokens()) { Word.set(itr.nextToken());//word存储被切割出来的单词 Context.write(word,one); } } } Reducer实现代码如下：Reducer函数从Map端得到形如word,{1,1,...}的输出，根据这些value值累加得到该单词出现次数并输出。 //继承Reducer接口，设置reducer输入类型Text,IntWriteable,输出类型Text,IntWriteable Public static class IntSumReducer extends ReducerText,IntWritable,Text,IntWritable { private IntWriteable result=new IntWriteable(); public void reduce(Text key,IterableIntWriteable values,Context context) throws IOException,interruptedExption { Int sum=0; //根据得到的key,list{value}计算value的和值，即字符串出现的次数 For(IntWritable val:values) { sum +=va