- 浏览: 353003 次
- 性别:
- 来自: 上海
文章分类
最新评论
-
希恩杰:
采样器的目的是啥?使数据均匀分布到所有分区?使key的数量均匀 ...
Hadoop深入学习:Hadoop全排序中的Sampler采样器 -
lawlietwf:
三篇文章中有两篇链接地址一样,po主看下
Hadoop中的快速排序算法 -
坏小四:
...
《Hbase权威指南》深入学习hbase:表,列族,列标识,版本和cell -
fbwfbi:
发现使用pika-0.9.13的版本依然出错:Tracebac ...
RabbitMQ:使用python发布/订阅消息 -
hehu158:
centos6.5 chmod +x qq2012.tra.g ...
CentOS 6.4安装qq2012
在Hadoop中,排序是MapReduce框架中最重要的操作之一,Map Task和Reduce Task都会对数据按照key排序,不管逻辑上是否真的需要排序,任何程序中的数据都会被排序,这是Hadoop的默认行为。
MapReduce中使用了两种排序算法:快速排序和优先队列。在Map和Reduce Task的缓冲区使用的是快速排序,而对磁盘上的IFile文件合并使用的是优先队列。
在学习Hadoop中实现的快速排序之前,我们先来回顾一下之前的三篇文章快速排序及改进、取中位数的算法和三向切分的快速排序算法:有大量重复元素的快速排序,MapReduce中使用的快速排序在经典的快速排序之上进行了一些列的优化,具体优化处理如下:
1)、由于快速排序的分割基数(基数左边的数都不大于该基数,而右边的都不小于该基数)选择的好坏直接影响快速排序的性能,最坏的情况是划分过程中是中产生两个极端不对称称的子序列——一个长度为1而另一个长度为n-1,此时有最坏的时间复杂度O(N^2),为了减小出现划分严重不对称的可能性,Hadoop将序列的守卫和中间元素中的中位数作为选择的分割基数;
2)、子序列的划分方法,Hadoop使用了两个索引i和j分别从左右两端进行扫描,并让索引i扫描到大于等于分割基数为止,索引j扫描到小于等于分割基数为止,然后交换两个元素,重复这个过程直到两个索引相遇;
3)、对相同的元素的优化,在每次划分子序列时,将于分割基数相同的元素放在中间位置,让他不再参与后续的递归处理,即将序列划分为三部分:小于分割基数、等于分割基数和大于分割基数;
4)、当子序列中元素数小于13时,直接使用插入排序算法,不在递归。
对于这四种处理,再对照之前我们学过的《快速排序及改进》、《取中位数的算法》和《三向切分的快速排序算法:有大量重复元素的快速排序》,看看都用到了那些知识?
具体实现代码如下:
MapReduce中使用了两种排序算法:快速排序和优先队列。在Map和Reduce Task的缓冲区使用的是快速排序,而对磁盘上的IFile文件合并使用的是优先队列。
在学习Hadoop中实现的快速排序之前,我们先来回顾一下之前的三篇文章快速排序及改进、取中位数的算法和三向切分的快速排序算法:有大量重复元素的快速排序,MapReduce中使用的快速排序在经典的快速排序之上进行了一些列的优化,具体优化处理如下:
1)、由于快速排序的分割基数(基数左边的数都不大于该基数,而右边的都不小于该基数)选择的好坏直接影响快速排序的性能,最坏的情况是划分过程中是中产生两个极端不对称称的子序列——一个长度为1而另一个长度为n-1,此时有最坏的时间复杂度O(N^2),为了减小出现划分严重不对称的可能性,Hadoop将序列的守卫和中间元素中的中位数作为选择的分割基数;
2)、子序列的划分方法,Hadoop使用了两个索引i和j分别从左右两端进行扫描,并让索引i扫描到大于等于分割基数为止,索引j扫描到小于等于分割基数为止,然后交换两个元素,重复这个过程直到两个索引相遇;
3)、对相同的元素的优化,在每次划分子序列时,将于分割基数相同的元素放在中间位置,让他不再参与后续的递归处理,即将序列划分为三部分:小于分割基数、等于分割基数和大于分割基数;
4)、当子序列中元素数小于13时,直接使用插入排序算法,不在递归。
对于这四种处理,再对照之前我们学过的《快速排序及改进》、《取中位数的算法》和《三向切分的快速排序算法:有大量重复元素的快速排序》,看看都用到了那些知识?
具体实现代码如下:
/* * Licensed to the Apache Software Foundation (ASF) under one * or more contributor license agreements. See the NOTICE file * distributed with this work for additional information * regarding copyright ownership. The ASF licenses this file * to you under the Apache License, Version 2.0 (the * "License"); you may not use this file except in compliance * with the License. You may obtain a copy of the License at * * http://www.apache.org/licenses/LICENSE-2.0 * * Unless required by applicable law or agreed to in writing, software * distributed under the License is distributed on an "AS IS" BASIS, * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. * See the License for the specific language governing permissions and * limitations under the License. */ package org.apache.hadoop.util; /** * An implementation of the core algorithm of QuickSort. */ public final class QuickSort implements IndexedSorter { private static final IndexedSorter alt = new HeapSort(); public QuickSort() { } private static void fix(IndexedSortable s, int p, int r) { if (s.compare(p, r) > 0) { s.swap(p, r); } } /** * Deepest recursion before giving up and doing a heapsort. * Returns 2 * ceil(log(n)). */ protected static int getMaxDepth(int x) { if (x <= 0) throw new IllegalArgumentException("Undefined for " + x); return (32 - Integer.numberOfLeadingZeros(x - 1)) << 2; } /** * Sort the given range of items using quick sort. * {@inheritDoc} If the recursion depth falls below {@link #getMaxDepth}, * then switch to {@link HeapSort}. */ public void sort(IndexedSortable s, int p, int r) { sort(s, p, r, null); } /** * {@inheritDoc} */ public void sort(final IndexedSortable s, int p, int r, final Progressable rep) { sortInternal(s, p, r, rep, getMaxDepth(r - p)); } private static void sortInternal(final IndexedSortable s, int p, int r, final Progressable rep, int depth) { if (null != rep) { rep.progress(); } while (true) { if (r-p < 13) { for (int i = p; i < r; ++i) { for (int j = i; j > p && s.compare(j-1, j) > 0; --j) { s.swap(j, j-1); } } return; } if (--depth < 0) { // give up alt.sort(s, p, r, rep); return; } // select, move pivot into first position fix(s, (p+r) >>> 1, p); fix(s, (p+r) >>> 1, r - 1); fix(s, p, r-1); // Divide int i = p; int j = r; int ll = p; int rr = r; int cr; while(true) { while (++i < j) { if ((cr = s.compare(i, p)) > 0) break; if (0 == cr && ++ll != i) { s.swap(ll, i); } } while (--j > i) { if ((cr = s.compare(p, j)) > 0) break; if (0 == cr && --rr != j) { s.swap(rr, j); } } if (i < j) s.swap(i, j); else break; } j = i; // swap pivot- and all eq values- into position while (ll >= p) { s.swap(ll--, --i); } while (rr < r) { s.swap(rr++, j++); } // Conquer // Recurse on smaller interval first to keep stack shallow assert i != j; if (i - p < r - j) { sortInternal(s, p, i, rep, depth); p = j; } else { sortInternal(s, j, r, rep, depth); r = i; } } } }
发表评论
-
CentOS 6.4 hadoop集成 Hbase Hive
2013-07-10 00:05 2282在之前的CentOS 5.4 hadoop集 ... -
CentOS 6.4 hadoop集成 Hbase Zookeeper
2013-07-09 22:41 2463再上一章中我们已经学习了Hadoop-1.0. ... -
CentOS 6.4 hadoop集成Hive
2013-07-09 01:58 2360在本节中,我们来学习如何安装Hive。在之前我 ... -
Hadoop深入学习:MapReduce Job中的Shuffle和sort
2013-07-06 22:30 1437... -
Hadoop深入学习:解析HDFS的写文件流程
2013-07-06 16:43 7210之前,我们 ... -
Hadoop深入学习:再谈MapReduce作业提交和执行
2013-07-03 22:00 1981在本章中,我们将来重温一下和Hadoop的作业 ... -
CentOS 6.4 安装伪分布式Hadoop 1.0.3
2013-07-02 00:52 2320在本章中学习如何在CentOS 6.4上安装配 ... -
Hadoop深入学习:Combiner
2013-07-04 00:03 10582在本节中,我们着重学习MapReduce编程模 ... -
Hadoop深入学习:MapReduce的Shuffle过程详解
2013-05-29 22:11 5140在本节中,我们再来仔细回顾一下MapRedu ... -
Hadoop深入学习:Hadoop全排序中的Sampler采样器
2013-05-28 18:27 4145在Partitioner组件的设计与实现中,我 ... -
Hadoop深入学习:ReduceTask详解
2013-05-28 16:16 1486本节我们来着重学习ReduceTask的内部操 ... -
Hadoop深入学习:MapTask详解
2013-05-28 15:23 4487在本节中 ... -
Hadoop深入学习:MapReduce中的心跳机制
2013-05-28 13:13 3133在本节中,我们特别来学习一些有心跳(Heart ... -
Hadoop深入学习:MapReduce作业提交和初始化
2013-05-27 22:24 4472之前已经学过了MapReduce接口编程模型及 ... -
Hadoop深入学习:OutputFormat组件
2013-05-27 16:45 2575在本节中,我们着重来学习一下MapReduc ... -
Hadoop深入学习:Reduce组件详解
2013-05-27 15:59 1411在本节中我们主要来学习MapReduce编程接 ... -
Hadoop深入学习:Partitioner组件的设计与实现
2013-05-27 15:31 3389本节我们来学习MapReduce编程框架中的P ... -
Hadoop深入学习:Mapper组件详解
2013-05-26 22:29 2164本节我们主要学习MapReduce编程接口模型 ... -
Hadoop深入学习:InputFormat组件
2013-05-26 22:26 8410在本节里, ... -
Hadoop深入学习:MapReduce的序列化
2013-05-26 20:27 2100在学习MapReduce ...
相关推荐
再通过对Hadoop平台的几种现有的排序算法的分析比较,发现频繁的读写磁盘降低数据处理的效率,提出了一种优化现有排序算法的置换选择算法,并进行了测试。测试结果表明,该算法简化了运行过程,可实现更快速的合并,...
技术点46 避免reducer 技术点47 过滤和投影技术点48 使用 combiner技术点49 超炫的使用比较器的快速排序6.4.4 减轻倾斜技术点50 收集倾斜数据技术点51 减轻reducer 阶段倾斜6.4.5 在MapReduce 中优化...
技术点49 超炫的使用比较器的快速排序 6.4.4 减轻倾斜 技术点50 收集倾斜数据 技术点51 减轻reducer 阶段倾斜 6.4.5 在MapReduce 中优化用户的Java 代码 6.4.6 数据序列化 6.5 本章小结 第4 部分 ...
:这个例子展示了使用 JSON-FP 实现快速排序算法是多么直观和优雅。 :展示如何使用 JSON-FP 来查询对象。 :统计程序是众多流行的 Hadoop 示例之一。 我们的 JSON-FP 计数器部分展示了如何在函数式编程风格中完成...
因此可以采⽤⼀些内存数据库,将热点数据常驻内存之中,从⽽取得⾮常快速的分析 能⼒,⾮常适合实时分析业务。图1是⼀种实际可⾏的MongoDB分析架构。 图1 ⽤于实时分析的MongoDB架构 MongoDB⼤集群⽬前存在⼀些稳定...
RDD提供了⽐MapReduce 丰富的模型,可以快速在内存中对数据集进⾏多次迭代,来⽀持复杂的数据挖掘算法和图形计算算法 4. Spark 多个作业之间数据通信是基于内存,效率更⾼ 缺点: 1. Spark 是基于内存的,由于内存...
3) 平台针对匹配模型推荐结果的排序算法 基于⽤户交互⽇志通过模型训练特征权重,采⽤排序算法来实现⾃动匹配个性化推荐。在系统实现技术架构上,为⽀撑个性化 推荐系统平均⾄少每周进⾏算法迭代,采⽤HBase、Spark...
而且不再有人机交互那么好的客户端了,至少要懂流处理、HADOOP、列式或分布式键值数据库吧,还需要能在SPARK上开发算法程序,对于用户画像、产品标签化、推荐系统、排序算法都应有所理解。 因此,大数据相对于传统BI...
业务价值导向 业务价值实现 大数据 基础平台 行业应用 提供一站式大数据应用支撑平台产品能力 交换汇集 挖掘分析 可视化 存储计算 融合治理 提供专业服务能力 政府 金融 能源 交通 军工 企业 咨询 设计 算法 定制 ...
hadoop hbase mongodb strom spark java语言 语言语法基础 异常 泛型 内部类 反射 序列化 nIo 匿名类 包装类 优先级 引用 语言工具类库 容器类 集合 链表 map 工具类 系统类 日期类 数字...