与前面章节的过滤器相比，本章是关于数据重组。个别记录的价值通常靠分区，分片，排序成倍增加。特别是在分布式系统中，因为这能提高性能。
在很多组织结构方面，Hadoop和其它MapReduce使用案例仅仅是大数据分析平台上一片数据的处理。数据通常被转换成跟其它系统有良好接口的形式，同样，数据也可能从原来状态转成一种新的状态，从而使MapReduce分析更容易。
本章包括下面几个子模式：
·分层结构模式
·分区和装箱模式
·全局排序和混洗模式
·生成数据模式
本章的模式通常一起使用来解决数据的组织问题。例如，你可能想调整数据分层，装箱，然后对箱进行排序。第六章的“Job Chaining“详细介绍了怎用把各种模式组合起来解决复杂的问题。
Structured to Hierarchical Pattern Description结构分层模式会根据数据创建新的不同结构的记录。由于这种模式的重要性，在本章很多地方独立存在。
Intent把基于行的数据转换成有层次的格式，例如，json xml。
Motivation当从RDBMS向Hadoop系统迁移数据时，首先考虑的一件事就是重组数据成为一种有意义的结构。因为hadoop不会关心数据格式，你应该充分利用分层次数据的优势避免做join。例如：我们的stackOverflow数据包含一张评论表，一张发帖表。很明显这是存储在标准的sql数据库的。当你访问发帖表时，所有数据库中的数据块要整合成一个视图来展现。这使得想分析个别发帖时变得更复杂。设想用发帖的长度跟评论的长度相关联，这需要首先做一次代价较高的join操作，然后抽取有用的数据。如果换成根据发帖分组数据，使发帖跟相关联的评论，编辑，修改数据紧挨着（例如反规范化表数据），这样分析起来会更容易和直观。这种情况下保存结构化数据完全达不到目的。
不幸的是，数据不总是分组在一块。当某人回复了stackOverflow的某个问题，hadoop不能够把这条记录立刻插到层次数据中。因此，用MapReduce创建非结构化记录只适用于周期性的批处理形式的业务逻辑。
另一种能平稳更新数据的方式是用Hbase。Hbase能存储半结构化和层次样式的数据。MongoDB也能很好的处理这种数据的排序。
Applicability这种模式适合的场景：
·你的数据靠很多外键相联系
·你的数据是结构化的基于行的
Structure图4-1展示了这种模式的结构，每部分组件描述如下：
·如果你想合并多个数据源成为一个有层次的数据结构，hadoop中有个类：org.apache.hadoop.mapreduce.lib.input.MultipleInputs很适合使用（貌似很老的包）。Mutipleinputs允许你对不同的input使用不同的input path和不同的mapper。Driver里完成配置。如果只有一个来源，则不需要这一步。
·mapper加载数据并解析成紧凑的格式从而使reducer更容易。输出key应该是你想要标识的每一条层次记录的根。例如，在stackOverflow例子里，根是发帖id。也需要给没片数据标注来源信息。也需要标识输出记录是发帖还是评论。这样的话，就能简单连接这些标签并输出值。
·通常，这里用combiner起不了多大作用。可以用相同的key对条目分组，一起发送，但这样没有压缩所起到的好处，因为要做的知识连接字符串，所以输出大小不变。
·reducer按key从不同的源接收数据。所有的数据对指定的分组，每组都会产生一个迭代器，剩下你需要做的就是用数据条目构建有层次的数据结构。使用xml或json，可以构建一个简单的对象并输出。这部分的例子使用xml，提供了几个方便的方法处理结构化数据。如果使用其他格式，例如自定义的格式，也要使用合适的构建对象的方法和序列化方法。
Figure 4-1. The structure of the structured to hierarchical pattern
Consequences输出是一种有层次的形式，根据指定的key分组的。
注意很多格式例如xml json都有某种顶层根元素包在所有记录外面。如果想让文档从根到底部都有良好的格式，也比较容易在特定的处理阶段加上头部或尾部。
Known usesPre-joining data
数据是杂乱的结构化数据集，为了分析，也很容易把数据组合成更复杂的对象。通过这样，你设置好数据来充分利用分析nosql模型的优势。
Preparing data for HBase or MongoDB
Hbase是很自然的存储这类数据的方式。所以可以用这种方法把数据搞到一起，作为加载到hbase或mongoDB的准备工作。创建hbase表，然后通过MapReduce执行大量导入是很高效的。另一种方案是分几次导入，可能效率较低。
ResemblancesSql
RDB中这样的事情是很少见的，因为这样存储用sql分析不是很方便。然而，这种方式可以解决RDBMS中的类似问题，比如做join然后在结果上做分析。
Pig
Pig对层次数据有适当的支持，可以取到层次的包和元组，然后就能容易的展现出层次结构和列出单条记录的对象。Pig中的cogroup方法
但是由于IBM产品中所附带的脚本中对接收命令行的参数没有进行有效的处理，以致于想通过命令行进行传递定制的参数无法顺利进行。
对于AIX、Linux、Solaris可以通过在 ikeyman.sh 中的 -classpath $CP 前增加 $* 来接收命令行参数
而在Windows下则可以通过在 ikeyman.bat（WAS 4.0版本）、ikeyman_old.bat（WAS 5.1及以上版本） 文件中的 -classpath %CP% 前加上 %* 来接收命令行参数
当然，也可以直接将参数写死在脚本里面，比如，想启动英文界面，则
1、对于 WAS 8.0/8.5 打开 WAS_HOME\bin 目录下的 ikeyman_old.bat 文件，在第 18 行
start "iKeyMan" "%JAVA_HOME%\jre\bin\javaw" -Djava.endorsed.dirs="%WAS_ENDORSED_DIRS%" -classpath %CP% com.ibm.gsk.ikeyman.Ikeyman
加上 -Duser.language=en
start "iKeyMan" "%JAVA_HOME%\jre\bin\javaw" -Djava.endorsed.dirs="%WAS_ENDORSED_DIRS%" -Duser.language=en -classpath %CP% com.ibm.gsk.ikeyman.Ikeyman
2、对于 WAS 6.1/7.0 打开 WAS_HOME\bin 目录下的 ikeyman_old.bat 文件，在第 18 行
start "iKeyMan" "%JAVA_HOME%\jre\bin\javaw" -classpath %CP% com.ibm.gsk.ikeyman.Ikeyman
加上 -Duser.language=en
start "iKeyMan" "%JAVA_HOME%\jre\bin\javaw" -Duser.language=en -classpath %CP% com.ibm.gsk.ikeyman.Ikeyman
3、对于 WAS 5.1/6.0 打开 WAS_HOME\bin 目录下的 ikeyman_old.bat 文件，在第 11 行
start "iKeyMan" "%JAVA_HOME%\bin\javaw" -classpath %CP% com.ibm.gsk.ikeyman.Ikeyman
加上 -Duser.language=en
start "iKeyMan" "%JAVA_HOME%\bin\javaw" -Duser.language=en -Duser.language=en -classpath %CP% com.ibm.gsk.ikeyman.Ikeyman
4、对于 WAS 4.0 打开 WAS_HOME\bin 目录下的 ikeyman.bat 文件，在第 12 行
start %JAVA_HOME%\bin\javaw -classpath %CP% com.ibm.gsk.ikeyman.Ikeyman
加上 -Duser.language=en
start %JAVA_HOME%\bin\javaw -classpath %CP% -Duser.language=en com.ibm.gsk.ikeyman.Ikeyman
修改保存后，再启动之就可以显示英文界面了。
已有 0 人发表留言，猛击->>这里<<-参与讨论
ITeye推荐
- —软件人才免语言低担保 赴美带薪读研！—
DFS实现回路拓扑排序，每一次选一个顶点进行访问，先递归访问其相邻的所有顶点，然后再访问该顶点，便可实现拓扑排序，比如A->B,A->C, A->D, B->E访问A的时候先访问BCD，那么最后的顺序肯定是AB(递归)CD， B递归之后为BE,最终的顺序为ABECD
下面举一个具体的例子，见下图
算法从V1~V5依次进行，初始的时候栈中元素为空
1.u = 1,说明当前递归V1,V1的邻居为V5,先访问V5,然后再访问V1,栈中的元素的顺序为V5 V1
2.u = 2,说明当前递归V2,V2的邻居为V1,但是V1已经访问过，所以访问V2,栈中的元素为V2 V5 V1
3.u = 3,说明当前递归V3,V3的邻居为V2, V4,V2已经访问过，故先访问V4，再访问V3,栈中的元素为V3 V4 V2 V5 V1
4.u = 4,说明当前递归V4,但是V4已经访问过了，故忽略本次递归
5.u = 5, 同u = 4
最后，栈中的元素顺序就是拓扑排序的顺序
/**
*
*/
#include <iostream>
using namespace std;
void print_arr(int a[], int n) {
for (int i = 0; i < n; i++)
cout << a[i] << " ";
cout << endl;
}
int c[6];
int topo[6], t;
int G[6][6];
bool dfs(int u) {
c[u] = -1;//表示正在访问该结点
for (int v = 1; v < 6; v++) {
if (G[u][v]) { //访问u的所有邻结点
if (c[v] < 0) return false; //说明该结点正在被访问，失败退出
else if (!c[v] && !dfs(v)) return false;//说明存在从u->v的边,但是访问该结点失败，那么就退出
}
}
c[u] = 1;// 表示该结点访问过了
topo[--t] = u;
cout << "t = " << t << ", u = " << u << endl;
return true;
}
bool topsort() {
t = 6;
memset(c, 0, sizeof(c));
for (int u = 1; u <= 5; u--) {
if (!c[u]) //如果u没有访问过就递归访问该结点
if (!dfs(u)) return false; //如果访问u不成功
}
return false;
}
int main() {
G[3][2] = G[3][4] = G[2][1] = G[4][1] = G[1][5] = 1;
topsort();
print_arr(topo, 6);
return 0;
}