内部排序算法:归并排序

基本思想 n个记录的文件的直接选择排序可经过n-1趟直接选择排序得到有序结果: 初始状态:无序区为R[1..n],有序区为空。 第1趟排序: 在无序区R[1..n]中选出关键字最小的记录R[k],将它与无序区的第1个记录R[1] 交换,使R[1..1]和R[2..n]分别变为记录个数增加1个的新有序区和记录个数减少1个的新无序区。 …… 第i趟排序: 第i趟排序开始时,当前有序区和无序区分别为R[1..i-1]和R[i..n](1≤i≤n-1)。 该趟排序从当前无序区中选出关键字最小的记录R[k],将它与无序区的第1个记录R[i]交换,使R[1..i] 和R[i+1..n]分别变为记录个数增加1个的新有序区和记录个数减少1个的新无序区。 这样,n个记录的文件的直接选择排序可经过n-1趟直接选择排序得到有序结果。 算法实现 归并排序算法,Java实现,代码如下所示: public abstract class Sorter { public abstract void sort(int[] array); } public class MergeSorter extends Sorter { @Override public void sort(int[] array) { int[] auxArray = new int[array.length];

内部排序算法:堆排序

基本思想 堆的定义 n个关键字序列kl,k2,…,kn称为堆,当且仅当该序列满足如下性质之一(简称堆性质): ki≤k2i且ki≤k2i+1 或 ki≥k2i且ki≥k2i+1(1≤i≤FLOOR(n/2)) 若将此序列所存储的向量R[1..n]看做是一棵完全二叉树的存储结构,则堆实质上是满足如下性质的完全二叉树:树中任一非叶结点的关键字均不大于(或不小于)其左右孩子(若 存在)结点的关键字。 小根堆:根结点(亦称为堆顶)的关键字是堆里所有结点关键字中最小的。 大根堆:根结点(亦称为堆顶)的关键字是堆里所有结点关键字中最大的。 我们可以选择大根堆或者小根堆中的任意一个来进行排序。 排序思想 用大根堆排序的基本思想: 先将初始文件R[1..n]建成一个大根堆,此堆为初始的无序区。 再将关键字最大的记录R[1](即堆顶)和无序区的最后一个记录R[n]交换,由此得 到新的无序区R[1..n-1]和有序区R[n],且满足R[1..n-1].keys≤R[n].key。 由于交换后新的根R[1]可能违反堆性质,故应将当前无序区R[1..n-1]调整为堆。 然后再次将R[1..n-1]中关键字最大的记录R[1]和该区间的最后一个

内部排序算法:快速排序

基本思想 设当前待排序的数组无序区为R[low..high],利用分治法可将快速排序的基本思想描述为: 分解: 在R[low..high]中任选一个记录作为基准(Pivot),以此基准将当前无序区划分为左、右两个较小的子区间R[low..pivotpos-1)和R[pivotpos+1..high],并使左边子区间中所有记录的关键字均小于等于基准记录(不妨记为pivot)的关键字pivot.key,右边的子区间中所有记录的关键字均大于等于pivot.key,而基准记录pivot则位于正确的位置(pivotpos)上,它无需参加后续的排序。 注意:划分的关键是要求出基准记录所在的位置pivotpos,划分的结果可以简单地表示为(注意pivot=R[pivotpos]): R[low..pivotpos-1].keys ≤ R[pivotpos].key ≤ R[pivotpos+1..high].keys 其中low≤pivotpos≤high。 求解: 通过递归调用快速排序对左、右子区间R[low..pivotpos-1]和R[pivotpos+1..high] 快速排序。 组合: 因为当“求解”步骤中的两个递归调用结束时,其左、右两个子区间已有序。对快速排序而言, “组合”步骤不需要做什么,可看作是空操作。 算法实现 快速排序算法

内部排序算法:希尔排序

基本思想 先取一个小于n的整数d1作为第一个增量,把待排序的全部记录分成dx个组。所有距离为d1的倍数的记录放在同一个组中。 先在各组内进行直接插人排序。 然后,取第二个增量d2<d1重复上述的分组和排序。 直至所取的增量dt=1(dt<dt-x<…<d2<d1),即所有记录放在同一组中进行直接插入排序为止。 算法实现 希尔排序算法,Java实现,代码如下所示: public abstract class Sorter { public abstract void sort(int[] array); } public class ShellSorter extends Sorter { @Override public void sort(int[] array) { int d = array.length; do { d /= 2; shellPass(array, d); // 根据逐渐减小的间隔增量,循环调用一趟排序 } while (d > 1); } /** * 希尔一趟排序 * @param d 间隔增量 */ private void shellPass(int[] array, int d) { Integer tmp; for (int i = d; i <

内部排序算法:冒泡排序

基本思想 将被排序的记录数组R[0..n-1]垂直排列,每个记录R[i]看作是重量为R[i].key的气泡。根据轻气泡不能在重气泡之下的原则,从下往上扫描数组R:凡扫描到违反本原则的轻气泡,就使其 向上”飘浮”。如此反复进行,直到最后任何两个气泡都是轻者在上,重者在下为止。 具体过程,如下所示: 初始状态:R[0..n-1]为无序区。 第一趟扫描:从无序区底部向上依次比较相邻的两个气泡的重量,若发现轻者在下、重者 在上,则交换二者的位置,即依次比较(R[n-1], R[n-2])、(R[n-2], R[n-3])、…、(R[1], R[0]);对于每对气泡(R[j+1], R[j]),若R[j+1].key第一趟扫描完毕时,”最轻”的气泡就飘浮到该区间的顶部,即关键字最小的记录被放在最高位置R[0]上。 第二趟扫描:扫描R[1..n-1]。扫描完毕时,”次轻”的气泡飘浮到R[1]的位置上……最后,经过n-1趟扫描可得到有序区R[0..n-1]。 注意: 第i趟扫描时,R[0..i-1]和R[i..n-1]分别为当前的有序区和无序区。扫描仍是从无序区底 部向上直至该区顶部。扫描完毕时,该区中最轻气泡飘浮到顶部

内部排序算法:直接选择排序

基本思想 n个记录的文件的直接选择排序可经过n-1趟直接选择排序得到有序结果: 初始状态:无序区为R[1..n],有序区为空。 第1趟排序:在无序区R[1..n]中选出关键字最小的记录R[k],将它与无序区的第1个记录R[1] 交换,使R[1..1]和R[2..n]分别变为记录个数增加1个的新有序区和记录个数减少1个的新无序区。 …… 第i趟排序:第i趟排序开始时,当前有序区和无序区分别为R[1..i-1]和R[i..n](1≤i≤n-1)。 该趟排序从当前无序区中选出关键字最小的记录R[k],将它与无序区的第1个记录R[i]交换,使R[1..i] 和R[i+1..n]分别变为记录个数增加1个的新有序区和记录个数减少1个的新无序区。 这样,n个记录的文件的直接选择排序可经过n-1趟直接选择排序得到有序结果。 算法实现 直接选择排序算法,Java实现,代码如下所示: public abstract class Sorter { public abstract void sort(int[] array); } public class StraightSelectionSorter extends Sorter { @Override public void sort(int[] array) { int tmp; // 用于交换数据的暂存

内部排序算法:直接插入排序

基本思想 假设待排序的记录存放在数组R[0..n-1]中。初始时,R[0]自成1个有序区,无序区为R[1..n-1]。 从i=1起直至i=n-1为止,依次将R[i]插入当前的有序区R[0..i-1]中,生成含n个记录的有序区。 算法实现 直接插入排序算法,Java实现,代码如下所示: public abstract class Sorter { public abstract void sort(int[] array); } public class StraightInsertionSorter extends Sorter { @Override public void sort(int[] array) { int tmp; for (int i = 1; i < array.length; i++) { tmp = array[i]; // array[i]的拷贝 // 如果右侧无序区第一个元素array[i] < 左侧有序区最大的array[i-1], // 需要将有序区比array[i]大的元素向后移动。 if (array[i] < array[i - 1]) { int j = i - 1; while (j >= 0 && tmp < array[j]) { // 从右到左扫描有序区

Shark-0.9.0安装配置运行实践

Shark(Hive on Spark)是UC Lab为Spark设计并开源的一款数据仓库系统,提供了分布式SQL查询引擎,它能够完全兼容Hive。首先,我们通过下面的图,看一下Shark与Hive的关系(http://shark.cs.berkeley.edu/img/shark-hive-integration.png): 以前我们使用Hive分析HDFS中数据时,通过将HQL翻译成MapReduce作业(Job)在Hadoop集群上运行;而使用Shark可以像使用Hive一样容易,如HQL、Metastore、序列化格式、UDF等Shark都支持,不同的是Shark运行在Spark集群上执行计算,基于Spark系统所使用的RDD模型。官方文档给出的性能方面的数据是,使用Shark查询分析HDFS数据,能比Hive快30多倍,如图所示(http://shark.cs.berkeley.edu/img/perf.png): 下面,我们通过安装配置Shark来简单地体验一下。 准备软件包 jdk-7u25-linux-x64.tar.gz scala-2.10.3.tgz apache-maven-3.2.1-bin.tar.gz hadoop-1.2.1.tar.gz spark-0.9.0-incubating-bin-hadoop1.tgz hive-0.11-shark-0.9.0.tar.gz 环境变量配置 针对上述准备软件包,我们需要安装配置好JDK、Scala环境,保证Hado

RDD:基于内存的集群计算容错抽象

该论文来自Berkeley实验室,英文标题为:Resilient Distributed Datasets: A Fault-Tolerant Abstraction for In-Memory Cluster Computing。下面的翻译,我是基于科学网翻译基础上进行优化、修改、补充,这篇译文翻译得很不错。在此基础上,我增加了来自英文原文的图和表格数据,以及译文中缺少的未翻译的部分。如果翻译措辞或逻辑有误,欢迎批评指正。 摘要 本文提出了分布式内存抽象的概念——弹性分布式数据集(RDD,Resilient Distributed Datasets),它具备像MapReduce等数据流模型的容错特性,并且允许开发人员在大型集群上执行基于内存的计算。现有的数据流系统对两种应用的处理并不高效:一是迭代式算法,这在图应用和机器学习领域很常见;二是交互式数据挖掘工具。这两种情况下,将数据保存在内存中能够极大地提高性能。为了有效地实现容错,RDD提供了一种高度受限的共享内存,即RDD是只读的,并且只能通过其他RDD上的批量操作来创建。尽管如此,RDD仍然足以表示很多类型的计算,包括MapReduce和专用的迭代编程模型(如Pregel)等。我们实现的RDD在迭代计

使用Java编写并运行Spark应用程序

我们首先提出这样一个简单的需求: 现在要分析某网站的访问日志信息,统计来自不同IP的用户访问的次数,从而通过Geo信息来获得来访用户所在国家地区分布状况。这里我拿我网站的日志记录行示例,如下所示: 121.205.198.92 - - [21/Feb/2014:00:00:07 +0800] "GET /archives/417.html HTTP/1.1" 200 11465 "http://shiyanjun.cn/archives/417.html/" "Mozilla/5.0 (Windows NT 5.1; rv:11.0) Gecko/20100101 Firefox/11.0" 121.205.198.92 - - [21/Feb/2014:00:00:11 +0800] "POST /wp-comments-post.php HTTP/1.1" 302 26 "http://shiyanjun.cn/archives/417.html/" "Mozilla/5.0 (Windows NT 5.1; rv:23.0) Gecko/20100101 Firefox/23.0" 121.205.198.92 - - [21/Feb/2014:00:00:12 +0800] "GET /archives/417.html/ HTTP/1.1" 301 26 "http://shiyanjun.cn/archives/417.html/" "Mozilla/5.0 (Windows NT 5.1; rv:11.0) Gecko/20100101 Firefox/11.0" 121.205.1

CentOS 6.4下安装配置Spark-0.9集群

Spark是一个快速、通用的计算集群框架,它的内核使用Scala语言编写,它提供了Scala、Java和Python编程语言high-level API,使用这些API能够非常容易地开发并行处理的应用程序。 下面,我们通过搭建Spark集群计算环境,并进行简单地验证,来体验一下使用Spark计算的特点。无论从安装运行环境还是从编写处理程序(用Scala,Spark默认提供的Shell环境可以直接输入Scala代码进行数据处理),我们都会觉得比Hadoop MapReduce计算框架要简单得多,而且,Spark可以很好地与HDFS进行交互(从HDFS读取数据,以及写数据到HDFS中)。 安装配置 下载安装配置Scala wget http://www.scala-lang.org/files/archive/scala-2.10.3.tgz tar xvzf scala-2.10.3.tgz 在~/.bashrc中增加环境变量SCALA_HOME,并使之生效: export SCALA_HOME=/usr/scala/scala-2.10.3 export PATH=$PATH:$SCALA_HOME/bin 下载安装配置Spark 我们首先在主节点m1上配置Spark程序,然后将配置好的程序文件复制分发到集群的各个从结点上。下载解压缩: wget http://d3kbcqa49mib13.cloudfront

Oozie Coordinator使用及详解

Oozie所支持工作流,工作流定义通过将多个Hadoop Job的定义按照一定的顺序组织起来,然后作为一个整体按照既定的路径运行。一个工作流已经定义了,通过启动该工作流Job,就会执行该工作流中包含的多个Hadoop Job,直到完成,这就是工作流Job的生命周期。 那么,现在我们有一个工作流Job,希望每天半夜00:00启动运行,我们能够想到的就是通过写一个定时脚本来调度程序运行。如果我们有多个工作流Job,使用crontab的方式调用可能需要编写大量的脚本,还要通过脚本来控制好各个工作流Job的执行时序问题,不但脚本不好维护,而且监控也不方便。基于这样的背景,Oozie提出了Coordinator的概念,他们能够将每个工作流Job作为一个动作(Action)来运行,相当于工作流定义中的一个执行节点(我们可以理解为工作流的工作流),这样就能够将多个工作流Job组织起来,称为Coordinator Job,并指定触发时间和频率,还可以配置数据集、并发数等。一个Coordinator Job包含了在Job外部设置执行周期和频率的语义,类似于在工作流外部增加了一个协调器来管理这些工作流的工作流Job的运