文章 56
评论 98
浏览 271517
数据库内部排序算法之两阶段多路归并排序算法实现

数据库内部排序算法之两阶段多路归并排序算法实现

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

64位Ubuntu14.04下安装hadoop2.6单机配置和伪分布配置详解

64位Ubuntu14.04下安装hadoop2.6单机配置和伪分布配置详解

环境 系统: 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 3. 给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

mapreduce之数据去重和数据排序实例

mapreduce之数据去重和数据排序实例

数据去重: 数据去重,只是让出现的数据仅一次,所以在 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平台wordcount程序的python实现

hadoop平台wordcount程序的python实现

摘要: ​尽管 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 s....

网络爬虫详解与python实现

网络爬虫详解与python实现

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

Ubuntu下通过PPA仓库安装JDK

Ubuntu下通过PPA仓库安装JDK

摘要: 在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实现自定义二次排序

MapReduce实现自定义二次排序

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

用Dijkstra算法求解无向图的最短路径

用Dijkstra算法求解无向图的最短路径

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

ACM刷题之-内存分配(POJ-1193 )

ACM刷题之-内存分配(POJ-1193 )

摘要: 内存是计算机重要的资源之一,程序运行的过程中必须对内存进行分配。 经典的内存分配过程是这样进行的: 1. 内存以内存单元为基本单位,每个内存单元用一个固定的整数作为标识,称为地址。地址从0开始连续排列,地址相邻的内存单元被认为是逻辑上连续的。我们把从地址i开始的s个连续的内存单元称为首地址为i长度为s的地址片。 2. 运行过程中有若干进程需要占用内存,对于每个进程有一个申请时刻T,需要内存单元数M及运行时间P。在运行时间P内(即T时刻开始,T+P时刻结束),这M个被占用的内存单元不能再被其他进程使用。 3、假设在T时刻有一个进程申请M个单元,且运行时间为P,则: 1. 若T时刻… 算法分析: 维护一个进程的链表,每个节点存有进程开始时间t,进程运行时间p, 在内存中的首地址s,占用内存大小m,和下一节点指针。 维护一个队列,表示还没有空间运行的进程。 维护一个释放内存的最早时间nexttime,每读入一个新进程的时候,若进程开始时间不小于nexttime,表示有进程在这之前已结束(可能不止一个),将其从链表删除,并循环检测队首

世界名画陈列馆问题(回溯法)

世界名画陈列馆问题(回溯法)

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

ACM刷题之-POJ-1002(487-3279)

ACM刷题之-POJ-1002(487-3279)

Description Businesses like to have memorable telephone numbers. One way to make a telephone number memorable is to have it spell a memorable word or phrase. For example, you can call the University of Waterloo by dialing the memorable TUT-GLOP. Sometimes only part of the number is used to spell a word. When you get back to your hotel tonight you can order a pizza from Gino’s by dialing 310-GINO. Another way to make a telephone number memorable is to group the digits in a memorable way. Yo

ACM刷题之-POJ-1011(Sticks)

ACM刷题之-POJ-1011(Sticks)

Description George took sticks of the same length and cut them randomly until all parts became at most 50 units long. Now he wants to return sticks to the original state, but he forgot how many sticks he had originally and how long they were originally. Please help him and design a program which computes the smallest possible original length of those sticks. All lengths expressed in units are integers greater than zero. Input The input contains blocks of 2 lines. The first line con

ACM刷题之-POJ-1014(Dividing)

ACM刷题之-POJ-1014(Dividing)

Description Marsha and Bill own a collection of marbles. They want to split the collection among themselves so that both receive an equal share of the marbles. This would be easy if all the marbles had the same value, because then they could just split the collection in half. But unfortunately, some of the marbles are larger, or more beautiful than others. So, Marsha and Bill start by assigning a value, a natural number between one and six, to each marble. Now they want to divide the marbl

ACM刷题之-POJ-1061(青蛙的约会)

ACM刷题之-POJ-1061(青蛙的约会)

Description 两只青蛙在网上相识了,它们聊得很开心,于是觉得很有必要见一面。它们很高兴地发现它们住在同一条纬度线上,于是它们约定各自朝西跳,直到碰面为止。可是它们出发之前忘记了一件很重要的事情,既没有问清楚对方的特征,也没有约定见面的具体位置。不过青蛙们都是很乐观的,它们觉得只要一直朝着某个方向跳下去,总能碰到对方的。但是除非这两只青蛙在同一时间跳到同一点上,不然是永远都不可能碰面的。为了帮助这两只乐观的青蛙,你被要求写一个程序来判断这两只青蛙是否能够碰面,会在什么时候碰面。 我们把这两只青蛙分别叫做青蛙A和青蛙B,并且规定纬度线上东经0度处为原点,由东往西为正方向,单位长度1米,这样我们就得到了一条首尾相接的数轴。设青蛙A的出发点坐标是x,青蛙B的出发点坐标是y。青蛙A一次能跳m米,青蛙B一次能跳n米,两只青蛙跳一次所花费的时间相同。纬度线总长L米。现在要你求出它们跳了几次以后才会碰面。 Input 输入只包括一行5个整数x,y,m,n,L,其中x≠y < 2000000000,0 < m、n < 2000000000,0 < L < 21

ACM刷题之-POJ-1396(Simple Arithmetics)

ACM刷题之-POJ-1396(Simple Arithmetics)

Description One part of the new WAP portal is also a calculator computing expressions with very long numbers. To make the output look better, the result is formated the same way as is it usually used with manual calculations. Your task is to write the core part of this calculator. Given two numbers and the requested operation, you are to compute the result and print it in the form specified below. With addition and subtraction, the numbers are written below each other. Multiplication

鲜衣怒马提银枪,一日看尽长安花,此间少年。