摘要: 两阶段归并排序算法是数据库查询的一个基础技术，在数据库应用中，常常采用“两阶段多路归并排序算法”来解决对海量数据的排序问题（这里的海量数据是指数据大小远远超过了数据库可用的主存的大小，无法将所有数据一次性的载入主存进行排序）。 前言 基于斯坦福大学的《数据库系统实现》，实现两阶段多路归并排序算法，通过merge-sort算法的实现，理解外存算法所基于的I/O模型与内存算法基于的RAM模型的区别；理解不同的磁盘访问优化方法是如何提高数据访问性能的。 首先生成一个具有10,000,000个记录的文本文件，其中每个记录由100个字节组成。实验只考虑记录的一个属性A，假定A为整数类型。记录在block上封装时，采用non-spanned方式，即块上小于一个记录的空间不使用。Block的大小可在自己的操作系统上查看，xp一般为4096 bytes。在内存分配50M字节的空间用于外部merge-sort。要求设计和实现程序完成下列功能： 生成文本文件，其中属性A的值随机产生。 对文本文件中的记录，按照属性A进行排序，其中在第二阶段的排序中每个子列表使用一

环境 系统： Ubuntu 14.04 64bit Hadoop版本： Hadoop 2.6.0 (stable) JDK版本： oracle jdk7 操作 在Ubuntu下创建hadoop用户组和用户 创建hadoop用户组 sudo addgroup hadoop 创建hadoop用户 sudo adduser -ingroup hadoop hadoop ３. 给hadoop用户添加权限，打开/etc/sudoers文件 sudo gedit /etc/sudoers 在root ALL=(ALL:ALL) ALL下添加hadoop ALL=(ALL:ALL) ALL. 安装SSH server、配置SSH无密码登陆 ssh 是一个很著名的安全外壳协议 Secure Shell Protocol。 rsync 是文件同步命令行工具 sudo apt-get install ssh rsync

数据去重： 数据去重，只是让出现的数据仅一次，所以在reduce阶段key作为输入，而对于values-in没有要求，即输入的key直接作为输出的key，并将value置空。具体步骤类似于wordcount： Tip：输入输出路径配置。 import java.io.IOException; import org.apache.hadoop.conf.Configuration; import org.apache.hadoop.fs.Path; import org.apache.hadoop.io.Text; import org.apache.hadoop.mapreduce.Job; import org.apache.hadoop.mapreduce.Mapper; import org.apache.hadoop.mapreduce.Reducer; import org.apache.hadoop.mapreduce.lib.input.FileInputFormat; import org.apache.hadoop.m

摘要: ​尽管Hadoop框架是用java写的，但是Hadoop程序不限于java，可以用python、C++、ruby等。本例子中直接用python写一个MapReduce实例，而不是用Jython把python代码转化成jar文件。 例子的目的是统计输入文件的单词的词频。 输入：文本文件 输出：文本（每行包括单词和单词的词频，两者之间用'\t'隔开） Python MapReduce 代码 使用python写MapReduce的“诀窍”是利用Hadoop流的API，通过STDIN(标准输入)、STDOUT(标准输出)在Map函数和Reduce函数之间传递数据。 我们唯一需要做的是利用Python的sys.stdin读取输入数据，并把我们的输出传送给sys.stdout。Hadoop流将会帮助我们处理别的任何事情。 Map阶段：mapper.py 在这里，我们假设把文件保存到hadoop-0.20.2/test/code/mapper.py #!/usr/bin/env python import sy

网络爬虫是捜索引擎抓取系统的重要组成部分。爬虫的主要目的是将互联网上的网页下载到本地形成一个或联网内容的镜像备份。这篇博客主要对爬虫以及抓取系统进行一个简单的概述。

摘要: 在Ubuntu14.04下通过PPA仓库安装JDK，这样就无需自己配置环境变量，完全自动配置好，比较方便，而且还可以保持JDK的版本是最新的． 在我们继续了解如何安装Java之前，让我们快速地了解JRE、OpenJDK和Oracle JDK之间的不同之处。 JRE（Java Runtime Environment），它是你运行一个基于Java语言应用程序的所正常需要的环境。如果你不是一个程序员的话，这些足够你的需要。 JDK代表Java开发工具包，如果你想做一些有关Java的开发（阅读程序），这正是你所需要的。 OpenJDK是Java开发工具包的开源实现，Oracle JDK是Java开发工具包的官方Oracle版本。尽管OpenJDK已经足够满足大多数的案例，但是许多程序比如Android Studio建议使用Oracle JDK，以避免UI/性能问题。 检查Java是否已经安装在Ubuntu上 打开终端，输入以下命令： java -version 如果有看到类似以下的输出，则表明你的电脑上已经安装好了JDK，否

摘要: MapReduce框架对处理结果的输出会根据key值进行默认的排序，这个默认排序可以满足一部分需求，但是也是十分有限的。在我们实际的需求当中，往往有要对reduce输出结果进行二次排序的需求。对于二次排序的实现，网络上已经有很多人分享过了，但是对二次排序的实现的原理以及整个MapReduce框架的处理流程的分析还是有非常大的出入，而且部分分析是没有经过验证的。本文将通过一个实际的MapReduce二次排序例子，讲述二次排序的实现和其MapReduce的整个处理流程，并且通过结果和map、reduce端的日志来验证所描述的处理流程的正确性。 概述 MapReduce框架对处理结果的输出会根据key值进行默认的排序，这个默认排序可以满足一部分需求，但是也是十分有限的。在我们实际的需求当中，往往有要对reduce输出结果进行二次排序的需求。对于二次排序的实现，网络上已经有很多人分享过了，但是对二次排序的实现的原理以及整个MapReduce框架的处理流程的分析还是有非常大的出入，而且部分分析是没有经过验证的。本文将通过一个实际的MapReduce二次排序例子，讲述二次排序

Dijkstra算法是典型的算法。Dijkstra算法是很有代表性的算法。Dijkstra一般的表述通常有两种方式，一种用永久和临时标号方式，一种是用OPEN, CLOSE表的方式，这里均采用永久和临时标号的方式。注意该算法要求图中不存在负权边。 　　 　　

算法问题描述： 世界名画陈列馆问题。世界名画陈列馆由m×n个排列成矩形阵列的陈列室组成。为了防止名画被盗，需要在陈列室中设置警卫机器人哨位。每个警卫机器人除了监视它所在的陈列室外，还可以监视与它所在的陈列室相邻的上、下、左、右4个陈列室。试设计一个安排警卫机器人哨位的算法，使得名画陈列馆中每一个陈列室都在警卫机器人的监视之下，且所用的警卫机器人数最少。 算法问题形式化表示 本问题的m*n的陈列室的解可表示如下图所示。其中1代表在该陈列室设置警卫机器人哨位，0表示未在该陈列室设置警卫机器人哨位。 最为极端的情况是所有元素的值为1。那什么情况下是最优解呢？就是设置警卫机器人哨位数最少即为最优。因为每个矩阵中的值都可以为1或0，有m*n个元素，有 种可能满足约束条件的矩阵，要从 种可能中遍历找到满足约束条件的1的个数最小的矩阵。由此可见这是一个NP问题。这里的约束条件就是当某一个元素为1时，相邻的4个方向上的

Kmeans算法，最为经典的基于划分的聚类方法 Kmeans算法： k-means 算法接受参数 k ；然后将事先输入的n个数据对象划分为 k个聚类以便使得所获得的聚类满足：同一聚类中的对象相似度较高；而不同聚类中的对象相似度较小。聚类相似度是利用各聚类中对象的均值所获得一个“中心对象”（引力中心）来进行计算的。 K-means算法是最为经典的基于划分的聚类方法，是十大经典数据挖掘算法之一。K-means算法的基本思想是：以空间中k个点为中心进行聚类，对最靠近他们的对象归类。通过迭代的方法，逐次更新各聚类中心的值，直至得到最好的聚类结果。 假设要把样本集分为c个类别，算法描述如下： （1）适当选择c个类的初始中心； （2）在第k次迭代中，对任意一个样本，求其到c个中心的距离，将该样本归到距离最短的中心所在的类； （3）利用均值等方法更新该类的中心值； （4）对于所有的c个聚类中心，如果利用（2）（3）的迭代法更新后，值保持不变，则迭代结束，否则继续迭代。 该算法的最大优势在于简洁和快速。算法的关键在于初始中心的选择和距离公式。