海量数据处理:经典实例分析

标签: 数据 经典 实例 | 发表时间:2016-06-22 00:06 | 作者:oMengLiShuiXiang1234
出处:http://blog.csdn.net

有关海量数据处理的问题,主要有以下3类:top K问题、重复问题、排序问题

top K 问题

在大规模数据处理中,经常会遇到的一类问题:在海量数据中找出出现频率最高的前K个数,或者从海量数据中找出最大的前K个数,这类问题通常被称为top K问题。例如,在搜索引擎中,统计搜索最热门的10个查询词;在歌曲库中统计下载率最高的前10首歌等。

针对top k 类问题,通常比较好的方案是分治+Trie树+小顶堆,即现将数据集按照hash方法分解成多个小数据集,然后使用Trie树或者Hash统计每个小数据集中的query词频,之后用小顶堆求出每个数据集中出现频率最高的前K个数,最后在所有top K中求出最终的top K。

例子:有1亿个浮点数,找出其中最大的10000个?

解决方案

将数据全部排序

最容易想到的方法是将数据全部排序,然后在排序后的集合中进行查找,最快的排序算法的时间复杂度一般为O(nlogn),如快速排序。而在32位机器上,每个float类型占4个字节,1亿个浮点数就要占用400MB的存储空间,对于一些可用内存小于400MB的计算机而言,很显然是不能一次将全部数据读入内存进行排序的。其实即使内存能够满足要求,该方法也并不高效,因为题目要求是寻找出最大的10000个数即可,而排序却是将所有的元素都排序了。

局部淘汰法

该方法与排序方法类似,用一个容器保存前10000个数,然后将剩余的所有数字一一与容器内的最小数字相比,如果所有后续的元素都比容器内的1000个数还小,那么容器内的这10000个数就是最大的10000个数。如果某一后续元素比容器内的最小数字大,则删掉容器内最小元素,并将该元素插入容器,最后遍历完这1亿个数,得到的结果容器中保存的数即为最终结果了。此时的时间复杂度为O(n+m^2),其中m为容器的大小,即10000.

分治法

将1亿个数据分成100份,每份100万个数据,找出每份数据中最大的10000个,最后在剩下的100*10000个数据里面找出最大的10000个。如果100万数据选择足够理想,那么可以过滤掉1亿数据里面99%的数据。100万个数据里面查找最大的10000个数据的方法如下:
用快速排序的方法,将数据分为2堆,如果大的那堆个数N大于10000个,继续对大堆快速排序一次分成2堆,如果大堆个数N小于10000,就在校的那堆里面快速排序一次,找第10000-n大的数字;递归以上过程,就可以找到第1w大的数。参考上面的找出的第1w大数字,就可以类似的方法找出前10000大数字了。此种方法每次需要的内存空间为10^6*4=4MB,一共需要101此这样的比较

Hash法

如果这1亿个数里面有很多重复的数,先通过Hash法,把着1亿个数字去重复,这样如果重复率很高的话,会减少很大的内存用量,从而缩小运算空间,然后通过分治法或最小堆法查找最大的10000个数。

最小堆

首先读入前10000个数来创建大小为10000的小顶堆,建堆的时间复杂度为O(mlogm)(m为数组的大小即为10000),然后遍历后续的数字,并与堆顶(最小)数字进行比较。如果比最小的数小,则继续读取后续数字;如果比堆顶数字大,则替换对顶元素并重新调整堆为小顶堆。整个过程直至1亿个数全都遍历完为止。然后按照中序遍历的方式输出当前堆中的所有10000个数字。该算法的时间复杂度为O(nmlogm),空间复杂度是10000(常数)。

实际上,最优的解决方案应该是最腹黑实际设计需求的方案,在实际应用中,可能有足够大的内存,那么直接将数据扔到内存中一次性处理即可,也可能机器有多个核,这样可以采用多线程处理整个数据集。

不同应用场景的解决方案

单机+单核+足够大内存

如果需要查找10亿个查询词(每个占8B)中出现频率最高的10个,考虑到每个查询词占8B,则10亿个查询词所需的内存大约是10^9*8B = 8GB 内存。如果有这么大的内存,直接在内存中对查询词进行排序,顺序遍历找出10个出现频率最大的即可。这种方法简单快速,更加实用。当然,也可以先用HashMap求出每个词出现的频率,然后求出频率最大的10个词。

单机+多核+足够大内存

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

单机+单核+受限内存

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

多机+受限内存

这种情况下,为了合理利用多台机器的资源,可将数据分发到多台机器上,每台机器采用(3)节中的策略解决本地的数据。可采用hash+socket方法进行数据分发。

小结

从实际应用考虑,上述的不同场景的解决方案并不可行,因为在大规模数据处理环境下,作业效率并不是首要考虑的问题,算法的扩展性和容错性才是首要考虑的。算法应该具有良好的扩展性,以便数据量进一步加大(随着业务的发展,数据量加大是必然的)时,在不修改算法框架的前提下,可达到近似的线性比;算法应该具有容错性,即当前某个文件处理失败后,能自动将其交给另外一个线程继续处理,而不是从头开始处理。

TOP K问题很适合采用MapReduce框架解决,用户只需编写一个Map函数和两个Reduce函数,然后提交到Hadoop(采用Mapchain和Reducechain)上即可解决该问题。具体而言,就是首先根据数据值或者把数据hash(MD5)后的值按照范围划分到不同的机器上,最好可以让数据划分后依次读入内存,这样不同的机器赋值处理不同的数值范围,实际上就是Map。得到结果后,各个机器只需拿出各自出现次数最多的前N个数据,然后汇总,选出所有的数据中出现次数最多的前N个数据,这实际上就是Reduce的过程。对于Map函数,采用Hash算法,将Hash值相同的数据交给同一个Reduce task;对于第一个Reduce函数,采用HashMap统计出每个词出现的频率,对于第二个Reduce函数,统计所有Reduce task,输出数据中的top K 即可。

直接将数据均分到不同的机器上进行处理时无法得到正确的结果的。因为一个数据可能被均分到不同的机器上,而另一个则可能完全聚集到一个机器上,同时还可能存在具有相同数目的数据。

Top K问题还有很多应用场景,尤其是在程序媛面试笔试中有很多实例,它们都可以采用上述方法解决。以下是一些历年来经常被各大互联网公司提及的该类问题。
(1)有1亿个记录,这些查询串的重复度比较高,如果除去重复后,不超过3百万个。一个查询串的重复度过高,说明查询它的用户越多,也就是越热门。请统计最热门的10个查询串,要求使用的内存不能超过1GB
(2)有10个文件,每个文件1GB,每个文件的每一行存放的都是用户的query,每个文件的query都可能重复。按照query的频度排序。
(3)有一个1GB大小的文件,里面的每一行是一个词,词的大小不超过16个字节,内存限制大小是1MB。返回频数最高的100个词
(4)提取某日访问网站次数最多的那个IP
(5)10亿个整数找出重复次数最多的100个整数
(6)搜索的输入信息是一个字符串,统计300万条输入信息中最热门的前10条,每次输入的一个字符串为不超过255B,内存使用只有1GB
(7)有1000万个身份证号以及它们对应的数据,身份证号可能重复,找出出现次数最多的身份证号。

重复问题

海量数据中查找出重复出现的元素或者去除重复出现的元素
针对此类问题,一般可以通过位图法实现。

例如,已知某个文件内包含一些电话号码,每个号码为8位数字,统计不同号码的个数。

本题最好的解决方法是通过使用位图法来实现。8位整数可以表示的最大十进制数值为99999999.如果每个数字对应于位图中一个bit位,那么存储8位整数大约需要99MB。因为1B=8bit,所以99Mbit折合成内存为 99/8 = 12.375MB的内存表示所有的8位数电话号码的内容。

  #include<iostream>
#include<stdlib.h>
#include<time.h>

using namespace std;

#define BITWORD 32
#define ARRNUM 100
int mmin = 10000000;
int mmax = 99999999;

int N = (mmax-mmin+1);
#define BITS_PER_WORD 32
#define WORD_OFFSET(b) ( (b)/BITS_PER_WORD )
#define BIT_OFFSET(b) ((b)%BITS_PER_WORD )

void SetBit( int *words, int n )
{
    n -= mmin;
    words[WORD_OFFSET(n)] |= ( 1<< BIT_OFFSET(n));
}

void ClearBit( int *words, int n )
{
    words[WORD_OFFSET(n)] &= ~( 1<< BIT_OFFSET(n));
}
int GetBit( int *words, int n )
{
    int bit = words[WORD_OFFSET(n)] & ( 1<< BIT_OFFSET(n));
    return bit != 0 ;
}


int main()
{
    int arr[ ARRNUM ];
    int *words = new int[ 1+N/BITS_PER_WORD ];
    if( words == NULL )
    {
        cout << " new error \n " << endl;
        exit(0);
    }

    int count = 0;
    for(int i=0; i<N; i++ )
        ClearBit( words,i);
    srand( (unsigned)time(NULL));
    cout << " the size of the array : " << ARRNUM << endl;

    for(int j=0; j<ARRNUM; j++ )
    {
        arr[j] = rand() % N;
        arr[j] += mmin;
        cout << arr[j] << "\t";
    }

    for(int j=0; j<ARRNUM; j++ )
        SetBit( words, arr[j]);

    cout << "after sort, a : " << endl;
    for( int i=0; i<N; i++ )
        if( GetBit( words,i) )
        {
            cout << i+mmin << "\t";
            count++;
        }
    cout << " sum is : " << count << endl;
    delete[] words;
    words = NULL;

    return 0;
}

上例中,采用时间作为种子,产生了100个随机数,对这100个数进行位图法排序,进而找出其中重复的数据。与此问题相似的面试笔试题还有:
(1)10亿个正整数,只有1个数重复出现过,要求在O(n)的时间里找出这个数
(2)给定a、b两个文件,各存放50亿个url,每个url各占用64B,要求在O(n)的时间里找出a、b文件共同的url
(3)给40亿个不重复的unsigned int的整数,没拍过序的,然后再给一个数,如何快速判断这个数是否在那40亿个数中?

排序问题

海量数据处理中一类常见的问题就是排序问题,即对海量数据中的数据进行排序。例如,一个文件中有9亿条不重复的9位整数,对这个文件中的数字进行排序。

针对这个问题,最容易想到的方法是将所有数据导入到内存中,然后使用常规的排序方法,如插入排序、快速排序、归并排序等各种排序方法对数据进行排序,最后将排序好的数据存入文件。但这些方法却不能在此适用,由于数据量巨大,在32位机器中,一个整数占用4个字节,而9亿条数据共占用9*10^8*4B,大约需要占用3.6GB内存,对于32位机器而言,很难将这么多数据一次载入到内存,所以,需要考虑其他方法。

数据库排序法

将文本文件导入到数据库中,让数据库进行索引排序操作后提取数据到文件。该种方法虽然操作简单、方便,但是运算速度较慢,而且对数据库设备要求比较高。

分治法

通过hash将9亿条数据分为20段,每段大约5000万条,大约占用5*10^6*4B=200MB空间,在文件中依次搜索0~5000万,50000001~1亿。。。将排序的结果存入文件。该方法要装满9位整数,一共需要20此,所以一共要进行20次排序,需要对文件进行20次读操作。该方法虽然缩小了每次使用的内存空间大小,但是编码复杂,速度也慢。

位图法

考虑到最大的9位整数为 999999999,由于9亿条数据是不重复的,可以把这些数据组成一个队列或数组,让它有0~999999999(一共10亿个数)个元素数组下标表示数值,结点中用0表示没有这个数,1表示存在这个数,判断0或1只用一个bit存储就够了,而声明一个可以包含9位整数的bit数组,一共需要10亿/8,大约120MB内存,把内存中的数据全部初始化为0,读取文件中的数据,并将数据放入内存。比如读到一个数据为341245909,那就先在内存中找到341245909这个bit,并将bit值置为1,遍历整个bit数组,将bit为1的数组下标存入文件,最终得到排序后的内容。

此类排序问题的求解方法一般都是采用上述方法。海量数据处理中与此类似的问题还有以下几种:
(1)一年的全国高考考生人数为500万,分数使用标准分,最低100分,最高900分,不存在成绩为小数的情况,把这500万考生的分数排序
(2)一个包含n个正整数的文件,每个正整数小于n,n等于1000万,并且文件内的正整数没有重复和关联数据u,输出整数的升序排列。

作者:oMengLiShuiXiang1234 发表于2016/6/21 16:06:31 原文链接
阅读:253 评论:0 查看评论

相关 [数据 经典 实例] 推荐:

海量数据处理:经典实例分析

- - CSDN博客综合推荐文章
有关海量数据处理的问题,主要有以下3类:top K问题、重复问题、排序问题. 例子有1亿个浮点数找出其中最大的10000个. 在大规模数据处理中,经常会遇到的一类问题:在海量数据中找出出现频率最高的前K个数,或者从海量数据中找出最大的前K个数,这类问题通常被称为top K问题. 例如,在搜索引擎中,统计搜索最热门的10个查询词;在歌曲库中统计下载率最高的前10首歌等.

Android数据库升级实例

- - BlogJava-qileilove
  Andoird的SQLiteOpenHelper类中有一个onUpgrade方法. 经过实践,解决了我一连串的疑问:. 帮助文档里说的“数据库升级”是指什么.   你开发了一个程序,当前是1.0版本. 到1.1版本时,你在数据库的某个表中增加了一个字段. 那么软件1.0版本用的数据库在软件1.1版本就要被升级了.

数据挖掘邻域的5篇经典文章

- yoyou - xlvector - Recommender System
转载自 http://www.dataminingblog.com/top-five-articles-in-data-mining/. Data Mining博客最近有篇文章,列举了他们认为的数据挖掘领域的5篇经典文章. Firefox 扩展:发现相关的论文.

数据挖掘十大经典算法(详解)

- - CSDN博客综合推荐文章
                                                       数据挖掘十大经典算法. C4.5算法是机器学习算法中的一种分类决策树算法,其核心算法是ID3 算法.   C4.5算法继承了ID3算法的优点,并在以下几方面对ID3算法进行了改进: . 1) 用信息增益率来选择属性,克服了用信息增益选择属性时偏向选择取值多的属性的不足; .

全球分布式数据库遇到的经典问题

- - idea's blog
全球分布式数据库因为地理距离较远(上万公里), 网络通信延迟一般在 100ms 级别, 所以只能采取异步复制的方案. 采取异步复制方案, 那就决定了最终数据被复制的时效性无法得到保证, 例如正常情况仅仅比网络延迟多几毫秒(100ms+). 但坏情况时, 例如, 因为网络线路不好, 数据可能要花费数秒甚至数分钟才能同步.

如何让数据说话! —网站实例分析

- - 互联网的那点事...
数据在很多网站都被看作是衡量一个产品或者一个设计好坏的基本指标之一. 数据指标也曾经压的我很长一段时间喘不过气来. 但是现在想想确实有时候数据能告诉你很多很多. 它未必是衡量产品好坏的唯一标准,但是它也确实能告知你很多. 那么数据究竟能告知我们些什么呢. –     你的流量有效吗. –     如何发现漏水的窟窿.

JDBC数据库的API对照实例学习

- - CSDN博客数据库推荐文章
实现数据库对数据的批处理,比如下面要输入一千条数据,不能每次都要创建连接等操作之后插入一条再断开再建立插入、、、、这样的话很显然是十分的浪费时间的. 当然了,批处理并不一定能到达很高的效率但是这是一种解决问题的方式. 时间:20131003 作者:烟大阳仔 */ public class PiChuLi {.

Oracle实例与数据库的概念详细解释

- - CSDN博客数据库推荐文章
刚接触ORACLE的人肯定会对实例和数据库感到困惑,实例到底代表些什么. ORACLE实例 = 进程 + 进程所使用的内存(SGA)实例是一个临时性的东西,你也可以认为它代表了数据库某一时刻的状态. 数据库 = 重做文件 + 控制文件 + 数据文件 + 临时文件. 数据库是永久的,是一个文件的集合.

实例剖析4种数据仓库的建模方法

- -
数据仓库,这个几乎是所有大数据开发面试必问的话题. 结合业务举例说明数据仓库建模的步骤,以及注意事项. 维度该如何选择建设,原则是什么,主键如何设计等等. 一众问题搞得小伙伴们死去活来,甚至工作好几年的小伙伴都没搞清楚过,尤其是大厂特别爱问这些问题. 有些小伙伴甚至觉得这些都是形而上学,不懂这些我不一样搞了很多年开发.