10 ways to improve your programming productivity

I worked in google, and now have my own company. Over the years of work experience told me that if there is a good working habits, you can greatly improve the efficiency. The following is my suggestion, if you insist on for a long time to do so, one year to two years, you find that you can complete the work faster than you imagine.


1. Don't read the news more than twice a day


Nowadays there is so much news everyday. Don't read too much. I tend to read news twice a day, morning and afternoon opening google reader. Reading more news will be severely reduced efficiency.

2.Making a good start point of work for yourself carefully.


Once programming in your good condition, there is no doubt the efficiency is very high, inside each brain cells seem to be struggling.But how can we come into the perfect working condition quickly? My experience is that every time I leave work, such as at lunch time or before the end of the day's work, I will deliberately left a small unfinished task in my program there. When I returned to work, I know where to start quickly, dedicated to solve this small task End, my brain has nearly completed the warm-up, and immediately have access to real work.

3.Do a good job by doing pre-research on paper


Drawing you thought on paper that can help you visualize the graphics in your mind, help you sum up thinking.
Do the pre-research work for a complex job, for example, a very difficult algorithm process, I will begin to write code after I get to know the most difficult technical problems.

4.To build a perfect working environment


Mostly We are working company, the working environment is not decided by us, but at least we can do at home a perfect working environment. I have a good working environment in mind include:

a) a big computer monitor, a large table
b) a comfortable computer chair
c) the beneficial background music for work, which varies from person to person
d) a good computer sound
e) sunny window
f) The large open space
g) quiet, very few people passing by
h) a well-ventilated world
i) room is decorated in modern style

5.turn off IM tool in working hours


Whatever the reason, we must turn off all the IM tools resolutely.

6.Only reply and deal with an emergency email in working hours


Do not let your e-mail to interrupt the rhythm of work. Only reply and deal with an emergency email in working hours

7.Reducing meeting, a meeting a week or less


Keep high-performance communication, but not more meetings.

8.Participate in social activities once every two weeks



The programmers' life is relatively monotonous. I am talking about social activities are not with colleagues, the work of the exchanges between the partners, nor is you are still sitting at the table playing computer games. But out of your office, and you communicate with people out of your work, you tailor your own emotional needs.

9.Relaxing night

Nothing worse than working 7 × 24-hour. For a long time in a state of excitement and anxiety will greatly affect your long-term work efficiency. A day of rest for a period of time, walking, reading, enjoying life, you will find your creativity increased.

10. 3 times a week, every 20 minutes in sports




Sports is not a waste of time, the regular sports activities will bring you more abundant focus, more flexible and good reflecting mind. Keep at least 3 times a week, every 20 minutes in sports.

用 Hadoop 进行分布式并行编程, 第 2 部分

网址：http://www.ibm.com/developerworks/cn/opensource/os-cn-hadoop2/index.html

用 Hadoop 进行分布式并行编程（二）程序实例与分析2008年06月27日 星期五 下午 02:29Hadoop 是一个实现了 MapReduce 计算模型的开源分布式并行编程框架，借助于 Hadoop, 程序员可以轻松地编写分布式并行程序，将其运行于计算机集群上，完成海量数据的计算。在本文中，详细介绍了如何针对一个具体的并行计算任务，基于 Hadoop 编写程序，如何使用 IBM MapReduce Tools 在 Eclipse 环境中编译并运行 Hadoop 程序。
前言

在上一篇文章：“用 Hadoop 进行分布式并行编程 第一部分 基本概念与安装部署”中，介绍了 MapReduce 计算模型，分布式文件系统 HDFS，分布式并行计算等的基本原理, 并且详细介绍了如何安装 Hadoop，如何运行基于 Hadoop 的并行程序。在本文中，将针对一个具体的计算任务，介绍如何基于 Hadoop 编写并行程序，如何使用 IBM 开发的 Hadoop Eclipse plugin 在 Eclipse 环境中编译并运行程序。


回页首




分析 WordCount 程序

我们先来看看 Hadoop 自带的示例程序 WordCount，这个程序用于统计一批文本文件中单词出现的频率，完整的代码可在下载的 Hadoop 安装包中得到(在 src/examples 目录中)。

1.实现Map类

见代码清单1。这个类实现 Mapper 接口中的 map 方法，输入参数中的 value 是文本文件中的一行，利用 StringTokenizer 将这个字符串拆成单词，然后将输出结果 <单词,1> 写入到 org.apache.hadoop.mapred.OutputCollector 中。OutputCollector 由 Hadoop 框架提供, 负责收集 Mapper 和 Reducer 的输出数据，实现 map 函数和 reduce 函数时，只需要简单地将其输出的 对往 OutputCollector 中一丢即可，剩余的事框架自会帮你处理好。

代码中 LongWritable, IntWritable, Text 均是 Hadoop 中实现的用于封装 Java 数据类型的类，这些类都能够被串行化从而便于在分布式环境中进行数据交换，你可以将它们分别视为 long, int, String 的替代品。Reporter 则可用于报告整个应用的运行进度，本例中未使用。


代码清单1
public static class MapClass extends MapReduceBase
implements Mapper{

private final static IntWritable one = new IntWritable(1);
private Text word = new Text();

public void map(LongWritable key, Text value,
OutputCollector output,
Reporter reporter) throws IOException {
String line = value.toString();
StringTokenizer itr = new StringTokenizer(line);
while (itr.hasMoreTokens()) {
word.set(itr.nextToken());
output.collect(word, one);
}
}
}



2.实现 Reduce 类

见代码清单 2。这个类实现 Reducer 接口中的 reduce 方法, 输入参数中的 key, values 是由 Map 任务输出的中间结果，values 是一个 Iterator, 遍历这个 Iterator, 就可以得到属于同一个 key 的所有 value. 此处，key 是一个单词，value 是词频。只需要将所有的 value 相加，就可以得到这个单词的总的出现次数。


代码清单 2
public static class Reduce extends MapReduceBase
implements Reducer {

public void reduce(Text key, Iterator values,
OutputCollector output,
Reporter reporter) throws IOException {
int sum = 0;
while (values.hasNext()) {
sum += values.next().get();
}
output.collect(key, new IntWritable(sum));
}
}



3.运行 Job

在 Hadoop 中一次计算任务称之为一个 job, 可以通过一个 JobConf 对象设置如何运行这个 job。此处定义了输出的 key 的类型是 Text, value 的类型是 IntWritable, 指定使用代码清单1中实现的 MapClass 作为 Mapper 类,　使用代码清单2中实现的 Reduce 作为 Reducer 类和 Combiner 类, 任务的输入路径和输出路径由命令行参数指定，这样 job 运行时会处理输入路径下的所有文件，并将计算结果写到输出路径下。

然后将 JobConf 对象作为参数，调用 JobClient 的 runJob, 开始执行这个计算任务。至于 main 方法中使用的 ToolRunner 是一个运行 MapReduce 任务的辅助工具类，依样画葫芦用之即可。


代码清单 3
public int run(String[] args) throws Exception {
JobConf conf = new JobConf(getConf(), WordCount.class);
conf.setJobName("wordcount");

conf.setOutputKeyClass(Text.class);
conf.setOutputValueClass(IntWritable.class);

conf.setMapperClass(MapClass.class);
conf.setCombinerClass(Reduce.class);
conf.setReducerClass(Reduce.class);

conf.setInputPath(new Path(args[0]));
conf.setOutputPath(new Path(args[1]));

JobClient.runJob(conf);
return 0;
}

public static void main(String[] args) throws Exception {
if(args.length != 2){
System.err.println("Usage: WordCount

");
System.exit(-1);
}
int res = ToolRunner.run(new Configuration(), new WordCount(), args);
System.exit(res);
}
}



以上就是 WordCount 程序的全部细节，简单到让人吃惊，您都不敢相信就这么几行代码就可以分布式运行于大规模集群上，并行处理海量数据集。

4. 通过 JobConf 定制计算任务

通过上文所述的 JobConf 对象，程序员可以设定各种参数，定制如何完成一个计算任务。这些参数很多情况下就是一个 java 接口，通过注入这些接口的特定实现，可以定义一个计算任务( job )的全部细节。了解这些参数及其缺省设置，您才能在编写自己的并行计算程序时做到轻车熟路，游刃有余，明白哪些类是需要自己实现的，哪些类用 Hadoop 的缺省实现即可。表一是对 JobConf 对象中可以设置的一些重要参数的总结和说明，表中第一列中的参数在 JobConf 中均会有相应的 get/set 方法，对程序员来说，只有在表中第三列中的缺省值无法满足您的需求时，才需要调用这些 set 方法，设定合适的参数值，实现自己的计算目的。针对表格中第一列中的接口，除了第三列的缺省实现之外，Hadoop 通常还会有一些其它的实现，我在表格第四列中列出了部分，您可以查阅 Hadoop 的 API 文档或源代码获得更详细的信息，在很多的情况下，您都不用实现自己的 Mapper 和 Reducer, 直接使用 Hadoop 自带的一些实现即可。


表一 JobConf 常用可定制参数
参数 作用 缺省值 其它实现
InputFormat 将输入的数据集切割成小数据集 InputSplits, 每一个 InputSplit 将由一个 Mapper 负责处理。此外 InputFormat 中还提供一个 RecordReader 的实现, 将一个 InputSplit 解析成 对提供给 map 函数。 TextInputFormat
(针对文本文件，按行将文本文件切割成 InputSplits, 并用 LineRecordReader 将 InputSplit 解析成 对，key 是行在文件中的位置，value 是文件中的一行) SequenceFileInputFormat
OutputFormat 提供一个 RecordWriter 的实现，负责输出最终结果 TextOutputFormat
(用 LineRecordWriter 将最终结果写成纯文件文件,每个 对一行，key 和 value 之间用 tab 分隔) SequenceFileOutputFormat
OutputKeyClass 输出的最终结果中 key 的类型 LongWritable
OutputValueClass 输出的最终结果中 value 的类型 Text
MapperClass Mapper 类，实现 map 函数，完成输入的 到中间结果的映射 IdentityMapper
(将输入的 原封不动的输出为中间结果) LongSumReducer,
LogRegexMapper,
InverseMapper
CombinerClass 实现 combine 函数，将中间结果中的重复 key 做合并 null
(不对中间结果中的重复 key 做合并)
ReducerClass Reducer 类，实现 reduce 函数，对中间结果做合并，形成最终结果 IdentityReducer
(将中间结果直接输出为最终结果) AccumulatingReducer, LongSumReducer
InputPath 设定 job 的输入目录, job 运行时会处理输入目录下的所有文件 null
OutputPath 设定 job 的输出目录，job 的最终结果会写入输出目录下 null
MapOutputKeyClass 设定 map 函数输出的中间结果中 key 的类型 如果用户没有设定的话，使用 OutputKeyClass
MapOutputValueClass 设定 map 函数输出的中间结果中 value 的类型 如果用户没有设定的话，使用 OutputValuesClass
OutputKeyComparator 对结果中的 key 进行排序时的使用的比较器 WritableComparable
PartitionerClass 对中间结果的 key 排序后，用此 Partition 函数将其划分为R份,每份由一个 Reducer 负责处理。 HashPartitioner
(使用 Hash 函数做 partition) KeyFieldBasedPartitioner PipesPartitioner




回页首




改进的 WordCount 程序

现在你对 Hadoop 并行程序的细节已经有了比较深入的了解，我们来把 WordCount 程序改进一下，目标: (1)原 WordCount 程序仅按空格切分单词，导致各类标点符号与单词混杂在一起，改进后的程序应该能够正确的切出单词,并且单词不要区分大小写。(2)在最终结果中，按单词出现频率的降序进行排序。

1.修改 Mapper 类，实现目标(1)

实现很简单，见代码清单4中的注释。


代码清单 4
public static class MapClass extends MapReduceBase
implements Mapper {

private final static IntWritable one = new IntWritable(1);
private Text word = new Text();
private String pattern="[^\\w]"; //正则表达式，代表不是0-9, a-z, A-Z的所有其它字符

public void map(LongWritable key, Text value,
OutputCollector output,
Reporter reporter) throws IOException {
String line = value.toString().toLowerCase(); //全部转为小写字母
line = line.replaceAll(pattern, " "); //将非0-9, a-z, A-Z的字符替换为空格
StringTokenizer itr = new StringTokenizer(line);
while (itr.hasMoreTokens()) {
word.set(itr.nextToken());
output.collect(word, one);
}
}
}



2.实现目标(2)

用一个并行计算任务显然是无法同时完成单词词频统计和排序的，这时我们可以利用 Hadoop 的任务管道能力，用上一个任务(词频统计)的输出做为下一个任务(排序)的输入，顺序执行两个并行计算任务。主要工作是修改代码清单3中的 run 函数，在其中定义一个排序任务并运行之。

在 Hadoop 中要实现排序是很简单的，因为在 MapReduce 的过程中，会把中间结果根据 key 排序并按 key 切成 R 份交给 R 个 Reduce 函数，而 Reduce 函数在处理中间结果之前也会有一个按 key 进行排序的过程，故 MapReduce 输出的最终结果实际上已经按 key 排好序。词频统计任务输出的 key 是单词，value 是词频，为了实现按词频排序，我们指定使用 InverseMapper 类作为排序任务的 Mapper 类( sortJob.setMapperClass(InverseMapper.class );)，这个类的 map 函数简单地将输入的 key 和 value 互换后作为中间结果输出，在本例中即是将词频作为 key,单词作为 value 输出, 这样自然就能得到按词频排好序的最终结果。我们无需指定 Reduce 类，Hadoop 会使用缺省的 IdentityReducer 类，将中间结果原样输出。

还有一个问题需要解决: 排序任务中的 Key 的类型是 IntWritable, (sortJob.setOutputKeyClass(IntWritable.class)), Hadoop 默认对 IntWritable 按升序排序，而我们需要的是按降序排列。因此我们实现了一个 IntWritableDecreasingComparator 类,　并指定使用这个自定义的 Comparator 类对输出结果中的 key (词频)进行排序：sortJob.setOutputKeyComparatorClass(IntWritableDecreasingComparator.class)

详见代码清单 5 及其中的注释。


代码清单 5
public int run(String[] args) throws Exception {
Path tempDir = new Path("wordcount-temp-" + Integer.toString(
new Random().nextInt(Integer.MAX_VALUE))); //定义一个临时目录

JobConf conf = new JobConf(getConf(), WordCount.class);
try {
conf.setJobName("wordcount");

conf.setOutputKeyClass(Text.class);
conf.setOutputValueClass(IntWritable.class);

conf.setMapperClass(MapClass.class);
conf.setCombinerClass(Reduce.class);
conf.setReducerClass(Reduce.class);

conf.setInputPath(new Path(args[0]));
conf.setOutputPath(tempDir); //先将词频统计任务的输出结果写到临时目
//录中, 下一个排序任务以临时目录为输入目录。

conf.setOutputFormat(SequenceFileOutputFormat.class);

JobClient.runJob(conf);

JobConf sortJob = new JobConf(getConf(), WordCount.class);
sortJob.setJobName("sort");

sortJob.setInputPath(tempDir);
sortJob.setInputFormat(SequenceFileInputFormat.class);

sortJob.setMapperClass(InverseMapper.class);

sortJob.setNumReduceTasks(1); //将 Reducer 的个数限定为1, 最终输出的结果
　　　　　　　　　　 //文件就是一个。
sortJob.setOutputPath(new Path(args[1]));
sortJob.setOutputKeyClass(IntWritable.class);
sortJob.setOutputValueClass(Text.class);

sortJob.setOutputKeyComparatorClass(IntWritableDecreasingComparator.class);

JobClient.runJob(sortJob);
} finally {
FileSystem.get(conf).delete(tempDir);　//删除临时目录
}
return 0;
}

private static class IntWritableDecreasingComparator extends IntWritable.Comparator {
public int compare(WritableComparable a, WritableComparable b) {
return -super.compare(a, b);
}

public int compare(byte[] b1, int s1, int l1, byte[] b2, int s2, int l2) {
return -super.compare(b1, s1, l1, b2, s2, l2);
}
}






回页首




在 Eclipse 环境下进行开发和调试

在 Eclipse 环境下可以方便地进行 Hadoop 并行程序的开发和调试。推荐使用 IBM MapReduce Tools for Eclipse, 使用这个 Eclipse plugin 可以简化开发和部署 Hadoop 并行程序的过程。基于这个 plugin, 可以在 Eclipse 中创建一个 Hadoop MapReduce 应用程序，并且提供了一些基于 MapReduce 框架的类开发的向导，可以打包成 JAR 文件，部署一个 Hadoop MapReduce 应用程序到一个 Hadoop 服务器(本地和远程均可)，可以通过一个专门的视图 ( perspective ) 查看 Hadoop 服务器、Hadoop 分布式文件系统（ DFS ）和当前运行的任务的状态。

可在 IBM alphaWorks 网站下载这个 MapReduce Tool, 或在本文的下载清单中下载。将下载后的压缩包解压到你 Eclipse 安装目录，重新启动 Eclipse 即可使用了。

设置 Hadoop 主目录

点击 Eclipse 主菜单上 Windows->Preferences, 然后在左侧选择 Hadoop Home Directory,设定你的 Hadoop 主目录,如图一所示：


图 1


创立一个 MapReduce Project

点击 Eclipse 主菜单上 File->New->Project, 在弹出的对话框中选择 MapReduce Project, 输入 project name 如 wordcount,　然后点击 Finish 即可。,如图 2 所示：


图 2


此后，你就可以象一个普通的 Eclipse Java project 那样，添加入 Java 类，比如你可以定义一个 WordCount 类，然后将本文代码清单1,2,3中的代码写到此类中，添加入必要的 import 语句 ( Eclipse 快捷键 ctrl+shift+o 可以帮你)，即可形成一个完整的 wordcount 程序。

在我们这个简单的 wordcount 程序中，我们把全部的内容都放在一个 WordCount 类中。实际上 IBM MapReduce tools 还提供了几个实用的向导 ( wizard ) 工具，帮你创建单独的 Mapper 类，Reducer 类，MapReduce Driver 类(就是代码清单3中那部分内容)，在编写比较复杂的 MapReduce 程序时，将这些类独立出来是非常有必要的，也有利于在不同的计算任务中重用你编写的各种 Mapper 类和 Reducer 类。

在 Eclipse 中运行

如图三所示，设定程序的运行参数:输入目录和输出目录之后，你就可以在 Eclipse 中运行 wordcount 程序了，当然，你也可以设定断点，调试程序。


图 3

主题：Skynet --- ruby的类Google Map/Reduce框架

Skynet是一个很响亮的名字，因为它是阿诺施瓦辛格主演的经典系列电影《终结者》里面的统治人类的超级计算机网络。不过本文的Skynet没这么恐怖，它是一个ruby版本的Google Map/Reduce框架的名字而已。

Google的Map/Reduce框架实在太有名气了，他可以把一个任务切分为很多份，交给n台计算机并行执行，返回的结果再并行的归并，最后得到运算的结果。据说Google一个搜索结果会Map到7000台服务器并行执行，这么多么可怕的分布式运算能力阿！有了Map/Reduce，程序员就可以在无需关注分布式框架的情况下，用简单的代码写出来健壮、并行的分布式应用程序，并且可以充分发挥计算机群集运算的能力。

如今能够实现Map/Reduce算法的框架已经有好几个了，其中最有名气的可能就是Yahoo发起的开源项目Hadoop，不过Hadoop并不是用ruby编写的，但在ruby的世界，Adam Pisoni已经开发出来了ruby版本的Map/Reduce框架，这就是Skynet。

Adam Pisoni开发Skynet的初衷是因为Adam Pisoni的公司Geni.com是一家定位于家族SNS的互联网网站。网站提供的新闻推送功能要求能够从大量的用户产生的信息当中提取特定用户感兴趣的内容，推送给用户。这实际上是一个分布式运算模型，要能够把任务分布到多台服务器上面执行，最后把任务归并回来。Adam Pisoni没有找到合适的框架，最终自己开发了Skynet，运用Map/Reduce算法来提供这个分布式运算平台。

用Skynet开发Map/Reduce的分布式应用程序非常简单，让我们举一个简单的例子看看吧：假设有一个1GB的文本文件，我们的任务是要统计该文件当中每个单词出现的次数统计。传统的做法当然很简单，顺序读入文件内容，进行单词统计就行了，但是毫无疑问，执行速度会很慢。如果我们有一个1000台服务器的运算群集，我们可以如何利用Skeynet来并发执行这个程序，从而缩短统计时间呢？

Map/Reduce算法的过程是：

1、Partition(划分数据)
把数据划分为1000份，这个过程由Skynet自动完成

2、Map
除了划分数据，还需要把运算该数据的代码也Map到每个运算节点上面去并发执行。这1000个节点各自执行自己的任务，执行完毕以后把执行结果返回

3、Partition
这1000分执行结果需要归并，于是我们再次划分数据，比方说划分为10份，这个过程也是Skynet自动完成的

4、Reduce
把Reduce代码和Reduce数据分发到10个节点执行，每个节点执行完毕返回数据。如果需要再次Reduce可以再次执行。最终Reduce为一个总共的结果。

其实Map/Reduce算法的原理是很简单的，好了，看看Skynet下面，我们怎么实现呢？其实我们需要编写的代码只有两个方法：一个map方法，告诉skynet如何执行每份数据，一个reduce方法，告诉skynet如何归并每份数据，所以这个并行算法最终用Skynet来写的话，也非常简单：

Ruby代码
class MapreduceTest
include SkynetDebugger

def self.map(datas)
results = {}
datas.each do |data|
results[data] ||= 0
results[data] += 1
end
[results]
end

def self.reduce(datas)
results = {}
datas.each do |hashes|
hashes.each do |key,value|
results[key] ||= 0
results[key] += value
end
end
results
end
end

class MapreduceTest
include SkynetDebugger

def self.map(datas)
results = {}
datas.each do |data|
results[data] ||= 0
results[data] += 1
end
[results]
end

def self.reduce(datas)
results = {}
datas.each do |hashes|
hashes.each do |key,value|
results[key] ||= 0
results[key] += value
end
end
results
end
end


这个就是一个最简单、但是完整ruby版本的Map/Reduce代码了。我们需要编写一个map方法，告诉skynet去统计每个单词的出现次数，我们还需要编写一个reduce方法告诉skynet去归并每个map的统计结果。好了，剩下所有的工作都归Skeynet接管了，是不是很简单！

当然要让这个Map/Reduce跑起来我们还需要做一些工作，比方说安装skynet，配置skynet的并行节点等等，这些琐碎的工作可以看看skynet自己的文档：http://skynet.rubyforge.org/doc/index.html，就不详述了。

值得一提的是Skynet可以和Rails框架良好的整合起来工作，你可以把Rails当中一些非常耗时、可以Map/Reduce的工作丢给Skynet去异步后台执行，比方说：

Ruby代码
MyModel.distributed_find(:all, :conditions => “created_on < ’#{3.days.ago}’”).each(:some_method)

MyModel.distributed_find(:all, :conditions => “created_on < ’#{3.days.ago}’”).each(:some_method)

把最近3天以来所有的model查询处理以后要执行的耗时操作some_method交给Skynet，让Skynet动用他强大的运算网络去执行。

还可以异步执行：
Ruby代码
model_object.send_later(:method, options, :save)

model_object.send_later(:method, options, :save)
把耗时的任务交给Skynet去异步执行。

对于拥有强大运算网络、并且需要进行大量耗时运算的web2.0网站来说，Skynet真是一个很棒的工具，他可以让程序员很简单的编写处理健壮而高效的分布式应用程序！

主题：基于Hadoop的Map reduce编程(一)

翻译的一篇国外的关于hadoop mapreduce的文章，文章比较长，先翻译第一部分吧

翻译者：pconlin900
博客：http://pconline900.javaeye.com

Hadoop是apache的一个开源的map-reduce框架，MapReduce是一个并行计算模型，用来处理海量数据。模型

思想来源于google的Jeffrey Dean 和 Sanjay Ghemawat，包括map() reduce()两个主要的功能。

这是一个很简单的类似于Hadoop的MapReduce应用例子，应用了mapreduce的基本思想，可以帮助理解hadoop

的处理思想和技术，但注意，它没有使用hadoop框架。
例子的功能是创建一些字符串，然后统计这些字符串里面每个字符出现的次数，最后汇总得到总的字符出现

次数。

Listing 1. 主程序
public class Main
{

public static void main(String[] args)
{

MyMapReduce my = new MyMapReduce();
my.init();

}
}


Listing 2. MyMapReduce.java

import java.util.*;

public class MyMapReduce
{
List buckets = new ArrayList();
List intermediateresults = new ArrayList();
List values = new ArrayList();

public void init()
{
for(int i = 1; i<=30; i++)
{
values.add("http://pconline900.javaeye.com" + new Integer(i).toString());
}



System.out.println("**STEP 1 START**-> Running Conversion into Buckets**");
System.out.println();
List b = step1ConvertIntoBuckets(values,5);
System.out.println("************STEP 1 COMPLETE*************");
System.out.println();
System.out.println();

System.out.println("**STEP 2 START**->Running **Map Function** concurrently for all

Buckets");
System.out.println();
List res = step2RunMapFunctionForAllBuckets(b);
System.out.println("************STEP 2 COMPLETE*************");

System.out.println();
System.out.println();
System.out.println("**STEP 3 START**->Running **Reduce Function** for collating Intermediate

Results and Printing Results");
System.out.println();
step3RunReduceFunctionForAllBuckets(res);
System.out.println("************STEP 3 COMPLETE*************");
System.out.println("************pconline900 翻译*************");
System.out.println("***********博客：

http://pconline900.javaeye.com*************");


}
public List step1ConvertIntoBuckets(List list,int numberofbuckets)
{
int n = list.size();
int m = n / numberofbuckets;
int rem = n% numberofbuckets;

int count = 0;
System.out.println("BUCKETS");
for(int j =1; j<= numberofbuckets; j++)
{
List temp = new ArrayList();
for(int i=1; i<= m; i++)
{

temp.add((String)values.get(count));
count++;


}
buckets.add(temp);
temp = new ArrayList();
}
if(rem != 0)
{
List temp = new ArrayList();
for(int i =1; i<=rem;i++)
{

temp.add((String)values.get(count));
count++;
}
buckets.add(temp);
}
System.out.println();
System.out.println(buckets);
System.out.println();
return buckets;

}

public List step2RunMapFunctionForAllBuckets(List list)
{
for(int i=0; i< list.size(); i++)
{
List elementList = (ArrayList)list.get(i);
new StartThread(elementList).start();
}

try
{
Thread.currentThread().sleep(1000);
}catch(Exception e)
{
}
return intermediateresults;
}

public void step3RunReduceFunctionForAllBuckets(List list)
{
int sum =0;
for(int i=0; i< list.size(); i++)
{
//you can do some processing here, like finding max of all results etc
int t = Integer.parseInt((String)list.get(i));
sum += t;
}


System.out.println();
System.out.println("Total Count is "+ sum);
System.out.println();

}

class StartThread extends Thread
{
private List tempList = new ArrayList();
public StartThread(List list)
{
tempList = list;
}
public void run()
{

for(int i=0; i< tempList.size();i++)
{
String str = (String)tempList.get(i);

synchronized(this)
{
intermediateresults.add(new Integer(str.length()).toString());
}


}
}

}

}


 init()方法创建了一些测试数据，作为测试数据。实际应用中会是海量数据处理。

 step1ConvertIntoBuckets()方法将测试数据拆分到5个 bucket中，每个bucket是一个ArrayList(包含6

个String数据)。bucket可以保存在内存，磁盘，或者集群中的其他节点；

 step2RunMapFunctionForAllBuckets()方法创建了5个线程(每个bucket一个)，每个线程StartThread处

理每个bucket并把处理结果放在intermediateresults这个arraylist中。

 如果bucket分配给不同的节点处理，必须有一个master主控节点监控各个节点的计算，汇总各个节点的

处理结果，若有节点失败，master必须能够分配计算任务给其他节点计算。\

 step3RunReduceFunctionForAllBuckets()方法加载intermediateresults中间处理结果，并进行汇总处

理，最后得到最终的计算结果。

20世纪10最好的算法

一、算法一词的来源

　　Algos是希腊字，意思是“疼”，A1gor是拉丁字，意思是“冷却”。这两个字都不是Algorithm(算法)一词的词根，a1gorithm一词却与9世纪的阿拉伯学者al-Khwarizmi有关，他写的书《al-jabr w’al muqabalah》(代数学)演变成为现在中学的代数教科书。Ad-Khwarizmi强调求解问题的有条理的步骤。如果他能活到今天的话，他一定会被以他的名字而得名的方法的进展所感动。

二、20世纪10最好的算法

　　20世纪最好的算法，计算机时代的挑选标准是对科学和工程的研究和实践影响最大。下面就是按年代次序排列的20世纪最好的10个算法。

1. Monte Carlo方法

1946年，在洛斯阿拉莫斯科学实验室工作的John von Neumann，Stan Ulam和Nick Metropolis编制了Metropolis算法，也称为Monte Carlo方法。Metropolis算法旨在通过模仿随机过程，来得到具有难以控制的大量的自由度的数值问题和具有阶乘规模的组合问题的近似解法。数字计算机是确定性问题的计算的强有力工具，但是对于随机性（不确定性）问题如何当时并不知晓，Metropolis算法可以说是最早的用来生成随机数，解决不确定性问题的算法之一。

2. 线性规划的单纯形方法

1947年，兰德公司的Grorge Dantzig创造了线性规划的单纯形方法。就其广泛的应用而言，Dantzig算法一直是最成功的算法之一。线性规划对于那些要想在经济上站住脚，同时又有赖于是否具有在预算和其他约束条件下达到最优化的能力的工业界，有着决定性的影响(当然，工业中的“实际”问题往往是非线性的；使用线性规划有时候是由于估计的预算，从而简化了模型而促成的)。单纯形法是一种能达到最优解的精细的方法。尽管理论上讲其效果是指数衰减的，但在实践中该算法是高度有效的——它本身说明了有关计算的本质的一些有趣的事情。

3. Krylov子空间叠代法

1950年，来自美国国家标准局的数值分析研究所的Magnus Hestenes, Eduard Stiefel和Cornelius Lanczos开创了Krylov子空间叠代法的研制。这些算法处理看似简单的求解形为

Ax=b

的方程的问题。当然隐藏的困难在于A是一个巨型的n*n 矩阵，致使代数解

x=b/A

是不容易计算的(确实，矩阵的“相除”不是一个实际上有用的概念)。叠代法——诸如求解形为

Kx(k+1)=Kx(k)+b-Ax(k)

的方程，其中K 是一个理想地“接近”A 的较为简单的矩阵——导致了Krylov子空间的研究。以俄罗斯数学家Nikolai Krylov命名的Krylov子空间由作用在初始“余量”向量

r(0)=b-Ax(0)

上的矩阵幂张成的。当 A是对称矩阵时，Lanczos找到了一种生成这种子空间的正交基的极好的方法。对于对称正定的方程组，Hestenes 和Stiefel提出了称为共轭梯度法的甚至更妙的方法。过去的50年中，许多研究人员改进并扩展了这些算法。当前的一套方法包括非对称方程组的求解技巧，像字首缩拼词为GMRES和Bi-CGSTAB那样的算法。(GMRES和Bi-CGSTAB分别首次出现于1986和1992 SIAM journal on Scientific and Statistical computing(美国工业与应用数学学会的科学和统计计算杂志)。

4. 矩阵计算的分解方法

1951年，橡树岭国家实验室的A1ston Householder系统阐述了矩阵计算的分解方法。研究证明能把矩阵因子分解为三角、对角、正交和其他特殊形式的矩阵是极其有用的。这种分解方法使软件研究人员能生产出灵活有效的矩阵软件包。这也促进了数值线性代数中反复出现的大问题之一的舍入误差分析问题。 (1961年伦敦国家物理实验室的James Wilkinson基于把矩阵分解为下和上三角矩阵因子的积的LU分解，在美国计算机协会(ACM)的杂志上发表了一篇题为“矩阵逆的直接方法的误差分析”的重要文章。)

5. Fortran最优编译程序

1957年，John Backus在IBM领导一个小组研制Fortran最优编译程序。Fortran的创造可能是计算机编程历史上独一无二的最重要的事件：科学家(和其他人)终于可以无需依靠像地狱那样可怕的机器代码，就可告诉计算机他们想要做什么。虽然现代编译程序的标准并不过分――Fortran I只包含23，500条汇编语言指令――早期的编译程序仍然能完成令人吃惊的复杂计算。就像Backus本人在1998年在IEEE annals of the History of computing 发表的有关Fortran I，II, III的近代历史的文章中回忆道：编译程序“所产生的如此有效的代码，使得其输出令研究它的编程人员都感到吓了一跳。”

6. 矩阵本征值计算的QR算法

1959—61年，伦敦Ferranti Ltd.的J.G. F. Francis找到了一种称为QR算法的计算本征值的稳定的方法。本征值大概是和矩阵相连在—起的最重要的数了，而且计算它们可能是最需要技巧的。把—个方阵变换为一个“几乎是”上三角的矩阵――意即在紧挨着矩阵主对角线下面的一斜列上可能有非零元素――是相对容易的，但要想不产生大量的误差就把这些非零元素消去，就不是平凡的事了。QR 算法正好是能达到这一目的的方法，基于QR 分解， A可以写成正交矩阵Q 和一个三角矩阵R 的乘积，这种方法叠代地把 A=Q(k)R(k) 变成 A(k+1)==Q(k)R(k) 就加速收敛到上三角矩阵而言多少有点不能指望。20世纪60年代中期QR 算法把一度难以对付的本征值问题变成了例行程序的计算。

7. 快速分类法

1962：伦敦Elliott Brothers, Ltd.的Tony Hoare提出了快速(按大小)分类法.把n个事物按数或字母的次序排列起来，在心智上是不会有什么触动的单调平凡的事。智力的挑战在于发明一种快速完成排序的方法。Hoare的算法利用了古老的分割开和控制的递归策略来解决问题：挑一个元素作为“主元”、把其余的元素分成“大的”和“小的”两堆(当和主元比较时)、再在每一堆中重复这一过程。尽管可能要做受到严厉责备的做完全部N(N-1)/2 次的比较(特别是，如果你把主元作为早已按大小分类好的表列的第一个元素的话！)，快速分类法运行的平均次数具有O(Nlog(N)) 的有效性，其优美的简洁性使之成为计算复杂性的著名的例子。

8. 快速Fourier变换

1965年，IBM的T. J. Watson研究中心的James Cooley以及普林斯顿大学和AT＆T贝尔实验室的John Tukey向公众透露了快速Fourier变换(方法)(FFT)。应用数学中意义最深远的算法，无疑是使信号处理实现突破性进展的FFT。其基本思想要追溯到Gauss(他需要计算小行星的轨道)，但是Cooley—Tukey的论文弄清楚了Fourier变换计算起来有多容易。就像快速分类法一样，FFT有赖于用分割开和控制的策略，把表面上令人讨厌的O(N*N) 降到令人欢乐的O(Nlog(N)) 。但是不像快速分类法，其执行(初一看)是非直观的而且不那么直接。其本身就给计算机科学一种推动力去研究计算问题和算法的固有复杂性。

9. 整数关系侦查算法

1977年，BrighamYoung大学的Helaman Ferguson 和Rodney Forcade提出了整数关系侦查算法。这是一个古老的问题：给定—组实数，例如说x(1),x(2),...,x(n) ，是否存在整数a(1),a(2),..,a(n) （不全为零），使得

a(1)x(1)+a(2)x(2)+...+a(n)x(n)=0

对于n=2 ，历史悠久的欧几里得算法能做这项工作、计算x(1)/x(2) 的连分数展开中的各项。如果x(1)/x(2) 是有理数，展开会终止，在适当展开后就给出了“最小的”整数a(1)和a(2) 。欧几里得算法不终止——或者如果你只是简单地由于厌倦计算——那么展开的过程至少提供了最小整数关系的大小的下界。Ferguson和Forcade的推广更有威力，尽管这种推广更难于执行(和理解)。例如，他们的侦查算法被用来求得逻辑斯谛(logistic)映射的第三和第四个分歧点，b(3)=3.544090 和 b(4)=3.564407所满足的多项式的精确系数。(后者是120 阶的多项式；它的最大的系数是257^30 。)已证明该算法在简化量子场论中的Feynman图的计算中是有用的。

10. 快速多极算法

1987年，耶鲁大学的Leslie Greengard 和Vladimir Rokhlin发明了快速多极算法。该算法克服了N体模拟中最令人头疼的困难之一：经由引力或静电力相互作用的N个粒子运动的精确计算(想象一下银河系中的星体，或者蛋白质中的原于)看来需要O(N*N) 的计算量——比较每一对质点需要一次计算。该算法利用多极展开(净电荷或质量、偶极矩、四矩，等等)来近似遥远的一组质点对当地一组质点的影响。空间的层次分解用来确定当距离增大时，比以往任何时候都更大的质点组。快速多极算法的一个明显优点是具有严格的误差估计，这是许多算法所缺少的性质。

三、结束语

　　2l世纪将会带来什么样的新的洞察和算法？对于又一个一百年完整的回答显然是不知道的。然而，有一点似乎是肯定的。正如20世纪能够产生最好的l0个算法一样，新世纪对我们来说既不会是很宁静的，也不会是弱智的。

基本的搜索算法

响应李老师的号召，抽空写了一下基本的搜索算法。我的搜索技术很有限，写的东西很难足够充实与深刻，但结合了具体的POJ 的题目，相信对于初学的队员多少还是有一点用处的。我主要说了四个部分：
1． 二分搜索 （Binary Search）
2． 记忆化搜索 (Dynamic Programming)
3． 广度优先搜索(BFS)
4． 深度优先搜索（DFS）

另外，有一点我觉得初学的人要理解，搜索就是穷举，当在做题的时候你发现一个题目需要枚举所有的情况的时候，你在做的就是搜索，当然，搜索也有很多策略和技巧可以优化你的搜索，这就是经常听说的剪枝。惭愧，我的搜索基本没剪枝。根据不同的具体题目剪枝策略很不相同，该怎么剪枝我也就不再多说了，但是在搜索的时候要时刻考虑有哪些剪枝条件可以加上以优化搜索，否则就跟我一样只能平庸的搜索了。

1． 二分搜索 （Binary Search）

二分也是搜索，因为解空间具有单调性，所以可以利用二分的思想去掉一大部分解空间，也即做了一个强有力的剪枝。同时二分也是一种基本的算法思想，当在思考一个问题的时候如果不能灵光一闪可以尝试用一些算法思想来考虑，比如对于一个问题你可以这样思考，这题贪心是否可以呢如果贪心的话该怎样贪呢，找不出合理的贪心方法的时候再想，这题动态规划是否可以呢，有没有第推关系呢，还找不出来再想用图论模型是否可以呢，该用哪种图论模型呢最短路径，最小生成树还是网络流呢，如果还不行还可以想那用二分可不可行呢，该怎样二分，为什么是可行的呢。
什么时候二分是可行的呢？下面简单的探讨一下。
先来看这样的一个小问题，给一个函数 F(x) 在闭区间 [A，B]上单调递增（假设F(x)的定义域均为整数），要求找出在区间[A，B]上最小的一个满足 F(n)>=0 的整数n。对于这个小问题最直观的想法就是从A开始穷举，这样写出来的程序可能会是这个样子。

For (int n=A; n<=B; n++)
{
If (F(n) >= 0)
Break;
}
这就是传说中的纯暴力，但是这个问题是可以用二分优化的，它之所以可以二分是因为 函数 F(n) 满足单调性，这点十分重要，这是一个问题可否二分的先决条件。那为什么满足单调性就可以二分呢，这是因为如果n满足F(n)>=０的话，所有　Ｂ＞＝ｘ＞＝ｎ　的数肯定也满足。所以所要求的目标解肯定在区间　［Ａ，ｎ］中。二分程序我一般都这样写。

Int min = A; // 解空间的最小值
Int max = B;//解空间的最大值
Int ans; //存储目标解
While (min <= max) //当解空间非空
{
Int mid = (min +max) / 2; // 取当前解空间的中值

If（ok(mid) ）// 如果mid 满足要求
{ //继续在 [min, mid-1] 中寻找更优的解
Max = mid-1;
Ans = mid; //记录下当前找到的解
}
Else //否则在区间 [mid+1,max]中寻找最优解
{
Min = mid + 1;
}

}
Ans 即为想要的答案，实际应用时注意在区间里找不到最优值得情况，注意看题目说明这个时候应该输出什么值。

下面结合一道具体的POJ 的题目来说下二分的应用


POJ 3273 Monthly Expense

题意不再多说，说得抽象一点，这个题可以这样思考。
设函数 f(x) 表示 如果要使每个月的钱都没有超过 x ，则划分出来的月的个数，设题目的解空间为[min, max] （相信理解了题意很容易确定）则，题目的要求可以描述为在区间 [min, max]中寻找最小的值ans 使得 f(ans) == M; 当然如果找到最小的ans 使得 f(ans)=m < M 的话肯定也满足要求，很显然，因为用m月来划分尚且没有使得每个月的钱超过 ans 那用 M个月划分就更不会超过ans，于是题目要求更新为在区间[min,max]中寻找最小值 ans 使得 f(ans) <= M； 上面说过要是可以二分必然满足函数 f(x) 在区间上单调， 这个函数 f(x)显然单调，理由，对于解空间的两个值 x1 < x2 ，如果用x1作为每个月钱的上限划分出来的月数为 y1，则用更多的钱 x2作为每个月钱的上限划分出来的月数 y2没有理由比y1会小，所以原函数满足单调性，所以可以用二分来解决。现在只剩下一个问题了，对于一个任意值x判断它的可行性，也即函数f(x)的值该如何求。方法就是尽量往一个月中加入尽量多的连续的天数使得当前月的钱数总合没有超过 x，如果加入一天的钱超出了x则函数值++，置当前月的钱数为该天的钱数，继续进行下去。
具体实现不再多说了。

推荐的题目：

3122：分析方法与上面类似，推荐。
3179：二分+枚举区间，有点难度，有兴趣的队员可以做下。
2922：综合题有一定的难度，BFS+二分+枚举区间，有兴趣的队员可以做下。
2． 记忆化搜索 （Dynamic Programming）

动态规划其实也是搜索，只不过，在搜索过程中它把一些已经搜索到的结果记录下来，当再次需要时如果发现当前状态的结果已经记录下来的时候，没有必要再次搜索，直接取出值来就可以。
来看一道POJ 的例题
POJ 3186


注意到题目的描述，FJ是按照时间顺序，也即天来卖treat的，每一天FJ手中的treat都有一个特定的状态。设为d[i,j]，表示为当前FJ手中的treat 标号为从i到j ，即 i,i+1, i+2,…,j，初始时状态为d[1,n]，每一天FJ都要做一个决策，选择卖出一个treat，对于状态为d[i,j]时他只有两种选择，要么卖标号为i的treat要么卖标号为j的treat，所以如果让dp[i,j]表示当FJ面对的状态为d[i,j]时他所能得到的最大值，则他所能得到的最大值是他所做的两种决策的最大值，则
dp[i,j] = max(dp[i+1,j]+wt(i,j,i), dp[i,j-1]+wt(i,j,j))；由此得到了第推关系，其中wt(i,j,i)表示当状态是d[i,j]时，卖标号为i的treat，标号为i的treat能贡献的值，具体是什么样子的可以看题意。
有两种方式可以实现，一种是第规的方式，一种是非第规，如果用第规的方式的话，更能体会为什么会叫作记忆化搜索，实现的时候，用一个数组dp[i，j]记录下搜索得到的当前状态的最优值，可以赋初值为-1，设函数 f(i,j) 表示寻找dp[i,j]的最优值，可以在进入函数的时候检查dp[i,j]是否为-1，如果不为-1则表示它的值已经计算出来了，直接返回dp[i,j]的值即可，如果为-1则表示它还没有被计算，返回f(i+1,j)+wt(i,j,i)和
f(i,j-1) + wt(i,j,j)的最大值；

这种第规形式的动态规划，我印象中几乎没做过，有我也是改成了非第规的形式。如果谁知道的话可以共享一下。
3． 广度优先搜索 （BFS）

这种题太多了，从易到难，数不过来，所以如果学会了广搜的话你会感觉你可以AC掉很多很多的题目。如果没学会的话，赶紧着学吧，我就推荐几个题目吧。

如果你刚学会BFS，或者不太会的话，可以做一下这几个题目。
POJ 1562，2386，3194，1915，1979
如果你觉得基本的BFS题可以顺利的AC了可以做下这几个题目。
这些题就是考得耐心和细心，其实都不难。
POJ 1101 传说中的连连看
POJ 2935 简单的题目但要求输出路径
POJ 2046 记录状态判重比较麻烦
POJ 2049 不是很容易，数据比较阴险，我做了好长时间。


4． 深度优先搜索 （DFS）

深搜是在万不得已，不得不枚举所有状态的时候才会用到，而且往往要用到比较巧妙的剪枝。我就推荐几个题目吧 （不用剪枝）
BFS推荐题中的1562，2386，1979都可以用DFS做，可以体会一下。
POJ 2676 数独问题，硬搞就行不难，
POJ 1011 很难的题目，要求有精妙的剪枝，推荐早晚把它做了。
POJ 2362 类似POJ 1011 但比那个要简单一些，推荐先做2362再作1011。

基于多项式快速傅立叶变换的大整数乘法

【关键字】

多项式乘法 快速傅立叶变换(FFT) 离散傅立叶变换(DFT) 大整数乘法 分治策略 ACM 高精度算法库
【摘要】

大整数的高精度运算是一个很重要的算法课题。这篇文章讨论了如何实现大整数的快速四则运算问题。目的是为了建立一个大整数算法库。主要讨论了如何实现 乘法。
【正文】

一：引言

大整数的四则运算中，加法和减法没有太多的优化余地；对于除法，则应充分用到乘法的优势，这要通过巧妙的运用牛顿迭代算法。因而乘法运算是大整数四则运算中的核心内容。进行乘法运算时，如果我们模拟平时进行整数乘法的步骤复杂度将达到O(n^2)，应用快速傅立叶变换可以将复杂度降到O(n*lg(n)) ，从而大大提高程序的运行效率并扩大了使用范围。本文先从理论角度介绍了大整数乘法运算的FFT(Fast Fourier Transforms)算法。并从编程角度讨论了一些实现时应注意的边界和精度问题。（针对ACM/ICPC程序设计比赛设计，因而某些地方为了提高效率而牺牲了一部分其它性能）

二：大整数的表示方法

一个N进制的整数可以表示成SUM(ai*(N^i))。也就是说整数运算问题可以转换为多项式的运算问题。例如：对N进制的整数X=P(N)和Y=Q(N)有XY＝R(N)。（其中P(N)和Q(N)是以N为变量的n-1次多项式X和Y的各位是其系数，且P(N)*Q(N)=R(N)）

所以下面的讨论就针对多项式的乘法运算展开。

我们都比较熟悉多项式的这种以系数ai来表示的形式。但我们今天更敢兴趣的是它的另一种表示形式——点值表示法。由n个不同的变量x及其对应的多项式取值y所构成的n点可以唯一确定一个n－1次多项式。这也就形成了在这种联系基础上的另一种多项式表示方法：用这些点(x,y)表示多项式的形式。

三：在多项式系数表示法的基础上做乘法运算

如果我们要把两个多项式乘起来。用系数表示法如右图：我们需要进行O(n^2)次基本乘法运算。这也是我们所手工计算是经常采用的方法。这种方法看上去已经没有什么可以优化的了。因为它看似没有做任何多余的事情。其中的每一组乘法运算都会对最终的结果产生影响。而且我们不能通过调整计算顺序或使用什么技巧降低算法的时间复杂度。最多只能通过一些语法和其它编程技巧使得其常数因子稍微小一些。

四：在点值表示法的基础上做乘法运算

对于两个多项式Y1(x),Y2(x).他们的一组点值表示法形式分别为(x[0],y1[0]),(x[1],y1[1])...(x[n-1], y1[n-1])和(x[0],y2[0]),(x[1],y2[1])...(x[n-1], y2[n-1]) 在这种形式的基础上做乘法运算就可以用O(n*lg(n))的复杂度得到多项式的成绩。因为Y(x)=Y1(x)*Y2(x)在x[i]处的值是y1[i]*y2[i] 。同理可求出其它点的值。

要把n－1次多项式和m－1次多项式做成绩，我们只需要在n＋m－1个不同的的x点分别求处对应的y1，y2值。该点所对应的y值就为y1×y2。只需做 这样的运算就可以得到乘积多项式的点值表示形式。

现在，速度瓶颈已经转移到如何在点值表示和系数表示之间进行快速转换。如果任给n个x值算y值从而得到n个点的话时间复杂度为 。把这n个点值表示法的点对应成为n－1次多项式也得花费相同复杂度的时间。那么我们的努力也就徒劳。怎么找到更好的转换算法就成了解决大整数乘法的关键所在。

五：用快速傅立叶变换和傅氏逆变换对多项式的两种形式进行 的转换

我们利用单位虚根之间的内部联系通过在这些特殊点上进行抽样(取值)以降低采样的时间复杂度。为了后面使用分治策略解决这个问题我们不失一般性的假设多项式的次数为n－1且n为2的幂(低次多项式可以看作高次系数为0的高次多项式)

六：利用FFT的大整数乘法

只要将多项式中的变量看成一个固定的常数N。那么各项系数就对应着N进制各位的数字。所以我们进行大整数相乘的方法如下：

1：把一个乘数(整数)的个,十,百,千。。。位分别放入a数组中的第0,1,2,3…项

2：把另一个乘数按同样的方法对应到b数组中。

3：对于a，b数组分别求FFT得到虚数数组A，B。（按n位处理，n为2的幂，不够的话高位补0）

4：虚数数组C中C[i]=A[i]*B[i]。（该乘法为虚数相乘需要自己实现运算符重载）

5：对C做傅立叶逆变换得到c。

（本来是虚数组，但由于整数乘法这个实际问题的解一定是整数故最终c是整数数组，虚部舍掉，实部四舍五入）

6：这个c即对应着大整数成绩的结果

七：复杂度问题

每次运算时a被分为两个和原来相同大小的数组，经FFT后在以O(n)的速度进行重组得到A，整个傅立叶变换（FFT）和傅立叶逆变换的时间复杂度如为:O(n*lg(n)).

八：实现过程中应该考虑的问题

1：整数溢出问题

由于傅立叶变换法类似于先做不进位乘法，然后处理进位问题。故当两个数位数最大(出于现有计算机计算速度等方面的原因，这里考虑1,000,000以内的数 )且都为N－1时，中间结果最有可能溢出。在C＋＋语言中，N<=43时中间结果不超出int型，N<=61时中间结果不会超过unsigned型。

2：精度问题

由于只进行log(n)次迭代，而double型有18位有效数字，因而误差远远小于0.5。因而不会对运算结果产生影响。

3：空间问题

由于处理位数比较大，并且存储效率比较低（每一位占4个字节）占用内存间比较大。因而当位数接近处理上限（这里考虑1,000,000）时，局部变量已经不能使用了。只能用new去申请空间。否则会在运行时出错。

注：源码可在http://victorcheng.wy8.net下载

【参考文献】
[1]:Thomas H.Cormen, Charles E.Leiserson, Ronald L.Rivest and Clifford Stein. Introduction to Algorithm. The MIT Press, second edition.

[2]:李庆阳，王能超，易大义，《数值分析》