文档章节

TopK算法及实现

SibylY
 SibylY
发布于 2013/12/16 09:24
字数 1353
阅读 108
收藏 1
点赞 0
评论 0
1. 问题描述
  在大规模数据处理中,常遇到的一类问题是,在海量数据中找出出现频率最高的前K个数,或者从海量数据中找出最大的前K个数,这类问题通常称为“top K”问题,如:在搜索引擎中,统计搜索最热门的10个查询词;在歌曲库中统计下载率最高的前10首歌等等。

2. 当前解决方案

  针对top k类问题,通常比较好的方案是【分治+trie树/hash+小顶堆】,即先将数据集按照hash方法分解成多个小数据集,然后使用trie树或者hash统计每个小数据集中的query词频,之后用小顶堆统计出每个数据集中出频率最高的前K个数,最后在所有top K中求出最终的top K。
  实际上,最优的解决方案应该是最符合实际设计需求的方案,在实际应用中,可能有足够大的内存,那么直接将数据扔到内存中一次性处理即可,也可能机器有多个核,这样可以采用多线程处理整个数据集。

本文针对不同的应用场景,介绍了适合相应应用场景的解决方案。
3. 解决方案
3.1 单机+单核+足够大内存
  设每个查询词平均占8Byte,则10亿个查询词所需的内存大约是10^9*8=8G内存。如果你有这么大的内存,直接在内存中对查询词进行排序,顺序遍历找出10个出现频率最大的10个即可。这种方法简单快速,更加实用。当然,也可以先用HashMap求出每个词出现的频率,然后求出出现频率最大的10个词。

3.2 单机+多核+足够大内存
  这时可以直接在内存中实用hash方法将数据划分成n个partition,每个partition交给一个线程处理,线程的处理逻辑是同3.1节类似,最后一个线程将结果归并。
该方法存在一个瓶颈会明显影响效率,即数据倾斜,每个线程的处理速度可能不同,快的线程需要等待慢的线程,最终的处理速度取决于慢的线程。解决方法是,将数据划分成c*n个partition(c>1),每个线程处理完当前partition后主动取下一个partition继续处理,直到所有数据处理完毕,最后由一个线程进行归并。

3.3 单机+单核+受限内存
  这种情况下,需要将原数据文件切割成一个一个小文件,如,采用hash(x)%M,将原文件中的数据切割成M小文件,如果小文件仍大于内存大小,继续采用hash的方法对数据文件进行切割,直到每个小文件小于内存大小,这样,每个文件可放到内存中处理。采用3.1节的方法依次处理每个小文件。

3.4 多机+受限内存
  这种情况下,为了合理利用多台机器的资源,可将数据分发到多台机器上,每台机器采用3.3节中的策略解决本地的数据。可采用hash+socket方法进行数据分发。
从实际应用的角度考虑,3.1~3.4节的方案并不可行,因为在大规模数据处理环境下,作业效率并不是首要考虑的问题,算法的扩展性和容错性才是首要考虑的。算法应该具有良好的扩展性,以便数据量进一步加大(随着业务的发展,数据量加大是必然的)时,在不修改算法框架的前提下,可达到近似的线性比;算法应该具有容错性,即当前某个文件处理失败后,能自动将其交给另外一个线程继续处理,而不是从头开始处理。
  Top k问题很适合采用MapReduce框架解决,用户只需编写一个map函数和两个reduce 函数,然后提交到Hadoop(采用mapchain和reducechain)上即可解决该问题。对于map函数,采用hash算法,将hash值相同的数据交给同一个reduce task;对于第一个reduce函数,采用HashMap统计出每个词出现的频率,对于第二个reduce 函数,统计所有reduce task输出数据中的top k即可。

  附上小根堆实现的c/c++代码:

/*
 *交换函数
*/
template<typename T>
inline void Swap( T &a, T &b)
{
	T c;
	c = a;
	a = b;
	b = c;
}
/*

 */
template<typename T>
void HeapAdjustSmall(T *array, int i, int nLength)
{ 
	int nChild; 
	T   tTemp; 
	for (tTemp = array[i]; 2 * i + 1 < nLength; i = nChild) { 
		nChild = 2 * i + 1;  
		if (nChild < nLength - 1 && array[nChild + 1] < array[nChild]) 
			++nChild; 
		if (tTemp > array[nChild]) { 
				array[i]= array[nChild]; 
		}
		else { 
			break; 
		} 
			array[nChild]= tTemp; 
	} 
}
/*
 *@ µ÷ÕûÐòÁеÄÇ°°ë²¿·ÖÔªËØ,µ÷ÕûÍêÖ®ºóµÚÒ»¸öÔªËØÊÇÐòÁеÄ×îСµÄÔªËØ
 */
template<typename T>
void HeapCreate(T *array, int length) {
	 
	for (int i = length / 2 - 1; i >= 0; --i) 
	{ 
		HeapAdjustSmall(array, i, length); 
	} 
} 
/*
*/
template<typename T>
void HeapSort(T *array, int length) { 
	for (int i = length - 1; i > 0; --i) { 
		Swap(array[0], array[i]); 
		HeapAdjustSmall(array, 0, i); 
	} 
}

template<typename T>
void HeapUpdate(T *array, int nLength, T *value) { 

	if ( *value > array[0] ) {
		array[0] = *value;
		HeapAdjustSmall(array, 0, nLength);
	}else
		return;
}

template <typename T>
inline bool GetTopK(T *pData, const se_uint32_t num, se_uint32_t k){
	
	num_t size = 0;
	HeapCreate(pData, k);
	for ( int i = k; i < num; ++i ) {
		HeapUpdate( pData, k, (pData + i) );
	}
	HeapSort(pData, k);
	return true;
}
#endif



本文转载自:http://blog.csdn.net/jj8582/article/details/6890521

共有 人打赏支持
SibylY
粉丝 29
博文 410
码字总数 327499
作品 0
海淀
程序员
ComputeColStats UDF中 近似算法的介绍

一,前面的话 表和列的统计信息对CBO的结果有着极大地影响,能够高效和准确的收集统计信息是极其重要的。但高效和准确是矛盾的,更准确的统计信息往往需要更多的计算,我们能做的是在高效和准...

阿里云云栖社区
04/26
0
0
从海量数据中提取TopK过程模拟

在工作面试中,经常会出现考察海量数据处理的问题:给你若干个数,从其中找到出现次数最多的K个数据。 (百度面试题中,有N多IP地址,让你找访问量TopK的IP) 解决方法 1. 有大量重复数据 如...

西昆仑
2012/08/22
0
8
阿里新突破!自主创新的下一代匹配&推荐技术:任意深度学习+树状全库检索

I 背景 推荐、搜索、广告投放是互联网内容提供商进行流量分配的核心业务,也是大数据和机器学习技术的典型应用场景。无论是推荐,搜索,还是广告投放问题,都可以描述为从大规模候选中给用户...

技术小能手
03/28
0
0
快排以及基于快排思想的topk 一锅端demo

算法不好,补补基本的排序算法,弄懂了快排,发现topK问题中也能用快排的思想所以写了一个demo 填坑解释法解释快排很形象,我是看这篇看懂快排的,这里推荐一下 http://blog.csdn.net/chengqi...

霁雪清虹
2017/11/10
0
0
python与自然语言处理 2结巴分词

特点 1,支持三种分词模式: a,精确模式,试图将句子最精确地切开,适合文本分析; b,全模式,把句子中所有的可以成词的词语都扫描出来, 速度非常快,但是不能解决歧义; c,搜索引擎模式,在...

qq_37634812
2017/12/18
0
0
Java--使用公私钥对加解密

Java-使用公私钥对加解密 一,问题描述 当你在某些安全行业,比如说金融,在与外部对接接口时,常常会用到加解密,今天我们 主要来简单记录下有关如何使用 Java 去实现加解密 本博客适用于使...

fajor
2016/09/13
56
0
搜索引擎关键字智能提示的一种实现

搜索引擎关键字智能提示的一种实现 美团技术团队 问题背景 搜索关键字智能提示是一个搜索应用的标配,主要作用是避免用户输入错误的搜索词,并将用户引导到相应的关键词上,以提升用户搜索体...

宇智波带土
2014/06/06
0
1
《程序员代码面试指南》Python实现(个人读书笔记)

说明   最近一直在读左神的书——《程序员代码面试指南—IT名企算法与数据结构题目最优解》,为了记录自己的学习成果,并且方便以后查看,将自己读书时的想法与使用python实现的代码记录在...

qq_34342154
2017/09/09
0
0
给定100亿个网址,如何检测出重复的文件。

给定100亿个网址,如何检测出重复的文件?这里所谓的“重复”是指两个URL完全相同。 或者: 使用hash将所有整数映射到1000个文件中,在每个文件中使用 bitmap,用两个bit表示出现次数,00表示...

一贱书生
2016/11/25
31
0
机器学习实战(一)KNN算法:简单的数据分类和决策

说明:该案例来源 机器学习实战之KNN,里面有更详尽的KNN原理分析和案例实现流程详解,是一个关于机器学习实战的不错的学习资料,推荐一波。出于编程实践和机器学习算法梳理的目的,按照自己...

stayfoolish_fan
05/13
0
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

Spark Streaming + Kafka Integration Guide

The Spark Streaming integration for Kafka 0.10 is similar in design to the 0.8 Direct Stream approach. It provides simple parallelism, 1:1 correspondence between Kafka partition......

刺猬一号
8分钟前
0
0
数据结构与算法2

一个数组的例子,实现查找,显示和删除的功能。 public class array {public static void main(String[] args){long[] arr;arr = new long[100];int nElems = 0;int j;...

沉迷于编程的小菜菜
18分钟前
0
0
Python3 基于 requests 批量下载图片

Python3 基于 requests 批量下载图片 import requestsheaders = {'Accept': 'text/html,application/xhtml+xml,application/xml;q=0.9,image/webp,image/apng,*/*;q=0.8','Accept-Encod......

leeyi
19分钟前
0
0
java获取当前时间所在一周的周一和周日日期

/** * 当前时间所在一周的周一和周日时间 * @param time 当前时间 * @return */ public static Map getWeekDate(String time) { Map map = new HashedMap(); SimpleDateFormat sdf = new Si......

小弱鸡
51分钟前
0
0
Redis数据的导出和导入(dump和load方式)

网上有些文章已经不再适用,本人也是踩了些坑,在此记录下。 迁移redis数据一般有如下3种方式: 第三方工具redis-dump,redis-load aof机制,需要开启aof功能 rdb存储机制 这里介绍第一种方式...

iplusx
56分钟前
2
0
ElasticSearch 高亮显示大文档搜索结果

2016年12月,我们开始研究Ambar——一个文档搜索系统。Ambar使用ElasticSearch作为核心搜索引擎。 在Ambar开发的过程中,我们处理了很多与ES相关的问题,我们想分享我们得到的宝贵经验。让我...

九州暮云
今天
1
0
Python 使用 pywifi 模块 破解wifi密码

git https://github.com/awkman/pywifi 常见常量 from pywifi import const# Define interface status.IFACE_DISCONNECTED = 0IFACE_SCANNING = 1IFACE_INACTIVE = 2IFACE_CONNEC......

阿豪boy
今天
2
0
phpstorm使用Iedis

phpstorm的redis插件Iedis是真好用 看了网上挺多的文章,但是由于我系统还是ubuntu,就有点尴尬了,现在破解之后,留个笔记,即使自己之后有需要也可以很快翻阅 先下载资源 资源下载 zip压缩...

贤郎--均灵
今天
0
0
第三章 spring-bean之FactoryBeanRegistrySupport(4)

前言 从FactoryBeanRegistrySupport类的名字可以看出FactoryBeanRegistrySupport负责FactoryBean的注册与支持。如果想知道FactoryBean相关的资料,请阅读spring-bean中关于FactoryBean的解读...

鸟菜啊
今天
0
0
CentOS “Destination Host Unreachable”问题解决办法

挑战极速安装CentOS时遇到局域网主机不能通信的情况: [root@zjd network-scripts]# ping 8.8.8.8PING 8.8.8.8 (8.8.8.8) 56(84) bytes of data.64 bytes from 8.8.8.8: icmp_seq=1 ttl=......

wffger
今天
0
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部