概述

总结一下常用的八大排序算法,大致的描述算法的原理和代码.以下皆假设N为待排序数组元素的个数.

插入排序(Insertion Sort)

基本思想

插入排序是最简单排序,由N-1次排序组成,从i=1至N-1次排序之后,保证序列a[0]至a[i]为已排序的状态.

即开始排序之前从a[0]至a[i-1]始终是已排序状态,每次把a[i]处的元素依次向前交换,直到a[0]至a[i]保证顺序.

代码实现

1
2
3
4
5
6
7
8
9

public void insertionSort(int[] a) {
    int j;//保存待插入的角标
    for (int i = 1; i < a.length; i++) {
        int tmp = a[i];//tmp元素保存待插入的元素
        for ( j = i; j > 0 && a[j - 1] < tmp; j--) 
            a[j] = a[j - 1];//依次将大于待排序值的元素向后移动
        a[j] = tmp;//把待排序元素插入对应的位置
    }
}

效率

如果序列是有序的,那么内层循环可以很快结束,效率很高.

• 最好情况下时间复杂度 : O(N)

• 平均情况下时间复杂度 : O(N^2).

希尔排序(Shell Sort)

基本思想

希尔排序通过比较相距一定间隔h的元素进行排序,对于每次排序后的序列来说都有a[i]<a[i+h].每一次排序的间隔h逐渐减小,直到h=1为止(即基本有序之后再对整个序列进行插入排序).

希尔排序的好处是,对于单纯的插入排序而言,在元素基本有序的情况下,会减少元素交换位置的次数,效率是很高的.

代码实现

1
2
3
4
5
6
7
8
9
10
11

public void shellSort(int[] a) {
    int j;
    for (int gap = a.length / 2; gap > 0; gap /= 2) {//元素间隔从序列的长度的一半每次减半,直到间隔为1
        for (int i = gap; i < a.length; i++) {//对每个相隔gap距离的元素进行插入排序
            int tmp = a[i];
            for (j = i; j >= gap && tmp < a[j - gap]; j -= gap) 
                a[j] = a[j - gap];
            a[j] = tmp;
        }
    }
}

效率

希尔排序编程很简单,但是分析起来却很复杂,不同的增量因子的选择会影响算法的效率.实践中证明希尔排序的性能是完全可以接受,即使是数以万计的N仍成立.

• 最坏情况下时间复杂度 : O(N^2).

归并排序

基本概念

归并算法的基本排序方法是依次比较两个已排序的子序列的头指针的元素,将更小的元素放入结果序列的头指针指向的位置,并后移结果序列的头指针.

归并排序是递归算法一个好的示例,很好的体现了”分而治之”的思想:对待排序序列分成左右两个子序列,依次分下去,直到不能再分;再对最小子序列进行前述排序,依次将排序好的子序列合并,直到待排序列的左右子序列合并完成.

代码实现

1
2

写在前面的话

最近参加了一些面试,总结了一些面试中没有回答出来,或者很有意思的问题.

1. 如果在HashMap中使用没有重写hashcode()方法的自定义对象会发生什么?

首先在回答这个问题之前要对HashMap的实现有所了解,HashMap的put()/get()/remove()方法都遵循以下原则:

1
2
3
4
5
6
7
8
9
10
11

// 只是表达插入的实现过程,与实际源码的实现有区别,查找和删除的过程也类似.
int h = hash(obj.hashcode()) //对传入对象重hash
int index = indexFor(lengh,h)//计算在桶中的位置
if  (table[index] == null ) { //如果桶中的位置为空就放入一个新节点   
     table[index] = newNode(obj);
}
else {
    ... //在链表或红黑树中查找是否存在新插入的元素
    if (obj.equals(ele)) ... //存在就替换
    else ...//否则在桶中链表中放上新节点
}

从上面伪码可以看出,需要先调用对象hashcode方法计算在数组中的位置,如果这个位置为空则需调用对象的equals方法在数组的链表中是否存在该对象.

假如没有实现该对象的hashcode方法则默认调用Object类的hashcode方法,因为默认的hashcode方法会返回内存中的位置,那么即使是相同的对象(equals返回true)的hashcode也会不同,最终造成的结果是存到HashMap中的值永远也取不出,也删不掉.

2. 待续

二叉树查找树

二叉查找树的性质是,对于树中的每个节点X,它的左子树中的所有项都小于右节点中的所有项.

二叉树节点的定义

1
2
3
4
5
6
7

// AnyType extends Comparable
private static class BinaryNode<AnyType> {
    AnyType element;
    BinaryNode left;
    BinartNode right;
    ...
}

二叉查找树架构

1
2
3
4

class BinarySearchTree<AnyType extends Comparable<? super AnyType>> {
   BinaryNode<AnyType> root;  // 根节点
   //  insert/remove/contains/findXXX... 等方法
}

contains方法

1
2
3
4
5
6
7

boolean contains(AnyType x, BinaryNode<AnyType> t) {
    if ( t == null ) renturn false;
    int cmp = t.compareTo( t.element );
    if ( cmp > 0 ) return contains( x, t.right );
    if ( cmp < 0 ) return contains( x, t.left );
    if ( cmp == 0 ) return ture;
}

findMin和findMax

min就是查找最左的节点,max就是查找最右的节点.

insert方法

基本思路与contains方法相同,查找出节点应该存在的地方,如果存在就什么事情也不做或者覆盖.

1
2
3
4
5
6
7
8
9
10
11
12
13
14

BinaryNode insert(AnyType x ,BinaryNode t) {
    if (t == null) 
       return new BinaryNode(x) ...// 把插入的元素作为新的root节点并返回
    int cmp = x compareTo t.element
    if cmp>0
        ...// 向右节点递归插入
    if cmp<0
        ...// 向左节点递归插入
    else
        ;// 重复元素
    return t;
}

remove方法

相对来说,删除元素的方法比较复杂一些,再删除一个节点的时候会有以下几种情况:

1. 是叶子节点

   因为没有子节点,那么可以直接删除.

2. 有一个子节点

   调整父节点的链接直接指向子节点,以绕过该节点.

3. 有两个子节点

   一种删除策略是用右子树中的最小节点的data替代该节点,并递归的删除那个最小节点(或者以同样的方法处理左子树中的最大节点).

   1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18

   BinaryNode remove(AnyType x,BinaryNode t){ if (t==null) // 没找到不做任何事 int cmp = x companreTo t.element; if cmp>0 ... //递归remove右子树 if cmp<0 ... //递归remove左子树 if t.left notNull && t.reght notNull // 两个子节点 t.data = findMin (t.right) // 找到右子树中最小项,并返回该项的data t.right = remove(t.data,t.right) //从右子树中删除节点,并更新右子树的root else //一个子节点 t = t.left != null ? t.left :t.right //将父节点直接指向改节点的唯一子节点 return t }

HDFS数据流

读取数据

读取数据的过程

1. 客户端调用FileSystem对象的open()方法,此对象是 DistributedFileSystem的一个示例.
2. DistributedFileSystem通过RPC到namenode获取文件第一个block的地址.并且对于每一个bkock,namenode都会返回具有该block”最近”的地址.
3. DistributedFileSystem返回一个FSDataInputStream对象,client通过调用此对象的read方法从指定地址的datanode获取第一个block.当第一个block获取后,将会关闭连接并从最近的datanode获取下一个block.这些对客户端来说都是透明的.

Hadoop如何选择’最近’的block

通过正确配置网络拓扑结构,Hadoop会依照以下优先级选取block地址:

1. 同一节点(本机)
2. 同一机架
3. 同一数据中心
4. 不同数据中心

写入数据

写入数据的过程

1. 客户端调用DFS对象的create()方法向namenode发送一个写请求,namenode在执行完一些检查,保证文件不存在并且客户端有权限创建文件之后返回一个DFSOutputStream对象.
2. DFSOutputStream将要写入的HDFS的文件分割成一些包,并将其写入到外置的data queue队列中.DataStrem消费这个队列,从namenode获取一些合适的datanode去存储这些包的副本.
3. 假定副本级别为3,那么将有3个datanode在流水线中,DataStream线程将包发送给流水线中的第一个datanode存储完成后,依次转发给流水线后面的datanode进行此操作.
4. 同时DFSOutputStream维护一个ack queue队列,等待流水线里所有datanode存储完成一个包之后,这个包从队列中移除.
   假如有datanode写入失败,流水线将关闭,ack queue中的包将添加到data queue的前端以保证失败的节点下游的datanode不会丢失包.正常的节点会联系namenode,保证失败节点在恢复后删除掉这些包.余下的包将会写入正常节点,并会在另外的节点上复制,保证分片的数量.

DFSOutputStream内部原理示意图

hadoop分布式文件系统

设计目的

1. 是为了大文件（大到一台机器无法存储）所设计。
2. 流式数据读取，一般会在批处理中使用HDFS。
3. 节点故障是常态，能在机器故障后恢复。

Blocks

HDFS中最小的存储单位，默认最小为128M。小于128M并不会占用一个单独的block。

设计成这么大是为了减少寻址的时间，但是也不应该太大，
大的block从硬盘转换的时间也会相应变慢。一般map任务会工作在一个单独的block上，如果block很少，map任务也会很慢。

Namenodes and Datanodes

HDFS集群两种节点

1. 一个 namenode（master）：

   管理文件系统的命名空间，维护了所有文件和目录的文件系统的文件树与元数据。

   namenode知道一个文件的所有block在哪个datanode上，但并不会存储这些信息。

2. 数个datanode（worker）：

   datanode是文件系统的实际工作者，它们在工作的时候存储或取回block，给namenode报告自己存储了那些block。

如果没有namenode文件系统将不可用。实际上，如果namenode消失了文件系统中的所有文件都会丢失，因为这样会不知道如何由block重建为一个文件。

保证namenode的可用性

1. 定期向硬盘上写入文件系统的元数据，一般是同步的，原子性的。

2. 运行secondary namenode,持续从主拷贝文件系统的更改日志并合并（这将消耗大量的系统资源）。当主namenode不可用时，由于同步会有延迟，数据可能会丢失，此时secondary成为主。

Block Caching

通常bkock会从硬盘中读取，但是重复使用的block会缓存在内存中。默认情况下一个block只会缓存在一个namenode中，但是这个是可以控制的。

最近在读《 Hadoop The Definitive Guide》一书，为了运行书上的示例程序，在虚拟机上搭建了Hadoop伪分布式环境，于是记下其过程。

Hadoop伪分布式环境搭建

1. 安装JDK配置环境变量，安装ssh配置免密登录。

2. 安装Hadoop：

   1 2	cd ~/download tar -zxvf ./hadoop-2.7.3.tar.gz -C /usr/local

3. 伪分布式配置
   修改配置文件 : ./etc/hadoop/core-site.xml

   1 2 3 4 5 6 7 8 9 10 11

   <configuration> <property> <name>hadoop.tmp.dir</name> <value>file:/usr/local/hadoop/tmp</value> <description>Abase for other temporary directories.</description> </property> <property> <name>fs.defaultFS</name> <value>hdfs://localhost:9000</value> </property> </configuration>

4. 修改配置文件 : ./etc/hadoop/hdfs-site.xml

   1 2 3 4 5 6 7 8 9 10 11 12 13 14

   <configuration> <property> <name>dfs.replication</name> <value>1</value> </property> <property> <name>dfs.namenode.name.dir</name> <value>file:/usr/local/hadoop/tmp/dfs/name</value> </property> <property> <name>dfs.datanode.data.dir</name> <value>file:/usr/local/hadoop/tmp/dfs/data</value> </property> </configuration>

Hadoop配置文件说明

Hadoop 的运行方式是由配置文件决定的（运行 Hadoop 时会读取配置文件），因此如果需要从伪分布式模式切换回非分布式模式，需要删除 core-site.xml 中的配置项。

此外，伪分布式虽然只需要配置 fs.defaultFS 和 dfs.replication 就可以运行（官方教程如此），不过若没有配置 hadoop.tmp.dir 参数，则默认使用的临时目录为 /tmp/hadoo-hadoop，而这个目录在重启时有可能被系统清理掉，导致必须重新执行 format 才行。所以我们进行了设置，同时也指定 dfs.namenode.name.dir 和dfs.datanode.data.dir，否则在接下来的步骤中可能会出错。

1. 启动Hadoop

   1 2 3

   cd ${HADOOP_HOME} ./bin/hdfs namenode -format ./sbin/start-dfs.sh

2. 运行WordCount示例:

   1 2 3 4 5

   ./bin/hdfs dfs -mkdir -p /user/hadoop # 创建HDFS目录 ./bin/hdfs dfs -mkdir input ./bin/hdfs dfs -put etc/hadoop/*.xml input # 将配置文件作为输入 ./bin/hadoop jar share/hadoop/mapreduce/hadoop-mapreduce-examples-*.jar grep input output 'dfs[a-z.]+' ./bin/hdfs dfs -cat output/* # 查看输出结果

运行Hadoop程序时output目录不能存在,否则会报错。这是为了防止数据丢，比如新的任务结果覆盖了耗时很长的久任务结果，这往往是人们不愿意看到的。

1. 启动YARN
   修改重命名配置文件 ./etc/hadoop/mapred-site.xml.template ：

   1	mv ./etc/hadoop/mapred-site.xml.template ./etc/hadoop/mapred-site.xml

增加以下配置:

1
2
3
4
5
6

<configuration>
        <property>
             <name>mapreduce.framework.name</name>
             <value>yarn</value>
        </property>
</configuration>

修改./etc/hadoop/yarn-site.xml ：

1
2
3
4
5
6

<configuration>
        <property>
             <name>yarn.nodemanager.aux-services</name>
             <value>mapreduce_shuffle</value>
            </property>
</configuration>

启动YARN，需要先执行./sbin/start-dfs.sh

1

./sbin/start-yarn.sh

至此,Hadoop伪分布式环境已经搭建完毕了~

Map and Reduce相关重点概念

MapReduce

MapReduce works by breaking the processing into two phases: the map phase and thereduce phase.

MapReduce把程序分成两个阶段:一个map阶段和一个reduce阶段.

The output from the map function is processed by the MapReduce framework beforebeing sent to the reduce function.
This processing sorts and groups the key-value pairsby key.

经过map之后的结果键值对,MapReduce框架会在reduce之前进行排序和分组.

数据流

任务拆分

Hadoop divides the input to a MapReduce job into fixed-size pieces called input splits,or just splits. Hadoop creates one map task for each split, which runs the user-definedmap function for each record in the split.

Hadoop将输入输入的任务拆分成固定大小的片段,并为每一个片段执行map函数.

任务拆分是为了在多台机器上面并行处理,任务如果拆分的足够小,那么更容易进行负载均衡.
但是另一方面,如果分块拆分的太小了,那么花在分块调度上面的时间可能会超过执行任务的时间.
对于大多数任务,分块的大小为128M,这也是HDFS默认的分块大小.

Map

Map tasks write their output to the local disk, not to HDFS.

Map会将输出存在本地,而不是HDFS.
因为Map产生的结果是中间结果,job完成后这些中间结果是可以丢弃的.

Reduce

Map的输出结果在传递给Reduce之前会在本地进行排序,然后通过网络发送的要进行Reduce的节点上合并数据,再将合并后的数据传入用户定义的Reduce.
Reduce的结果为了保持可靠性,输出结果会存到HDFS中.

shuffle

在Map和Reduce之间的操作.

整个数据流示意图

Conbiner Fuctions

解决了什么问题

Mapreduce作业的会被集群之间的带宽限制性能,Conbiner被用来优化map和reduce作业之间的数据交换
hadoop允许用户在map和reduce作业之间自定义conbiner function,因为这是一个优化性能的操作,
hadoop并能保证会在map作业输出时候执行几次.

用处

比如求最大值的时候,可以在各节点计算出最大值之后,在reduce作业中计算各节点最大值中的最大值.

新的开始

鸡年是一个新的开始,之前的工作和学习中也积累了不少,但是都只是记录到我的OneNote中了.
趁着新年休息把自己的Blog搭建好,准备逐步把自己之前积累的东西与别人分享一下.

新年目标

1. 每个月更新一篇有价值的文章.
2. 能抽出时间学习Scala
3. 学习更多大数据技能