`

【腾讯】1亿个数据取前1万大的整数

阅读更多

数据规模分析

 

不考虑操作系统的区别,通常将C++中的一个整型变量认为4bytes。那么1亿整型需要400M左右的内存空间。当然,就现代PC机而言,连续开辟400M的内存空间还是可行的。因此,下面的讨论只考虑在内存中的情况。为了讨论方便,假设M=1亿,N=1万。

 

 

用大拇指想想

略微考虑一下,使用选择排序。循环1万次,每次选择最大的元素。源代码如下:

//解决方案1,简单选择排序
//BigArr[]存放1亿的总数据、ResArr[]存放1万的总数据
void solution_1(int BigArr[], int ResArr[] ){
       for( int i = 0; i < RES_ARR_SIZE; ++i ){
              int idx = i;
              //选择最大的元素
              for( int j = i+1; j < BIG_ARR_SIZE; ++j ){
                     if( BigArr[j] > BigArr[idx] )
                            idx = j;
              }
              //将最大元素交换到开始位置
              ResArr[i] = BigArr[idx];
              std::swap( BigArr[idx], BigArr[i] );
       }
}

性能分析: 哇靠!时间复杂度为O(M*N)。 有人做过实验《从一道笔试题谈算法优化(上) 》,需要40分钟以上的运行时间。太悲剧了......

 

当然,用先进的排序方法(比如快排),时间复杂度为O(M*logM)。虽然有很大的改进了,据说使用C++的STL中的快排方法只需要32秒左右。确实已经达到指数级的优化了,但是否还能够优化呢?

 

 

 

 

稍微动下脑子

我们只需要1万个最大的数,并不需要所有的数都有序,也就是说只要保证的9999万个数比这1万个数都小就OK了 。我们可以通过下面的方法来该进:

 

(1) 先找出M数据中的前N个数。确定这N个数中的最小的数MinElement。

(2) 将  (N+1) —— M个数循环与MinElement比较,如果比MinElement还小,则不处理。如果比MinElement大,则与MinElement交换,然后重新找出N个数中的MinElement。

//解决方案2
void solution_2( T BigArr[], T ResArr[] ){
       //取最前面的一万个
       memcpy( ResArr, BigArr, sizeof(T) * RES_ARR_SIZE );
       //标记是否发生过交换
       bool bExchanged = true;
       //遍历后续的元素
       for( int i = RES_ARR_SIZE; i < BIG_ARR_SIZE; ++i ){
              int idx;
              //如果上一轮发生过交换
              if( bExchanged ){
                     //找出ResArr中最小的元素
                     int j;
                     for( idx = 0, j = 1; j < RES_ARR_SIZE; ++j ){
                            if( ResArr[idx] > ResArr[j] )
                                   idx = j;
                     }
              }
              //这个后续元素比ResArr中最小的元素大,则替换。
              if( BigArr[i] > ResArr[idx] ){
                     bExchanged = true;
                     ResArr[idx] = BigArr[i];
              }else
                     bExchanged = false;
       }
}

 

性能分析: 最坏的时间复杂度为O((M-N)*N)。咋一看好像比快排的时间复杂度还高。但是注意是最坏的,实际上,并不是每次都需要付出一个最小值O(N)的代价的。因为,如果当前的BigArr[i]<ResArr[idx]的话,就不需要任何操作,则1——N的最小值也就没有变化了。下一次也就不需要付出O(N)的代价去寻找最小值了。当然, 如果M基本正序的话,则每次都要交换最小值,每次都要付出一个O(N)代价。最坏的情况比快排还要差。

 

就平均性能而言,改进的算法还是比快排要好的,其运行时间大约在2.0秒左右。

 

 

使劲动下脑子

上面的解决方案2还有一个地方不太好。当BigArr[i]>ResArr[idx]时,则必须交换这两个数,进而每次都需要重新计算一轮N个数的最小值。只改变了一个数就需要全部循环一次N实在是不划算。能不能下一次的最小值查找可以借助上一次的比较结果呢?

 

基于这样一个想法,我们考虑到了堆排序的优势(每一次调整堆都只需要比较logN的结点数量)。因此我们再做一次改进:

 

(1) 首先我们把前N个数建立成小顶堆,则根结点rootIdx。

(2) 当BigArr[i]>ResArr[rootIdx]时,则交换这两个数,并重新调整堆,使得根结点最小。

 

性能分析:显然,除了第一次建堆需要O(N)时间的复杂度外,每一次调整堆都只需要O(logN)的时间复杂度。因此最坏情况下的时间复杂度为O((M-N)*logN),这样即使在最坏情况下也比快排的O(M*logM)要好的多了。

 

另外:实际上也可以使用二分查找的思想,第一次找N中的最小值的时候将N排序。以后每次替换最小值,都使用二分查找在logN代价下找到当前N的最小值即可。与使用堆的过程如出一辙。

 

 

 

 

 

 

 

 

 

1
0
分享到:
评论
3 楼 blackdog1987 2012-08-16  
很经典的  大根堆的问题
2 楼 fxltsbl 2012-03-27  
能不能考虑用布隆过滤器,把1亿个数据映射到BitSet里面,映射时记录一个最大值z(如果已知就不用比较记录了),然后倒叙从z循环整数,每次z--,循环输出最大的1w条


public static void main(String[] args){
BitSet bs = new BitSet();
//读文件,把1亿个数据映射到BitSet里面,这里只写一个
int value = 100;
int max = 1234567890;
bs.set(value);


int[] result = new int[10000];
int index = 0;
//然后倒叙从z循环整数
for(int i=max;i>0&&index<10000;i--){
if(bs.get(i)){
result[index] = i;
index++;
}
}

}
1 楼 forrest420 2011-08-19  
写的非常好

相关推荐

    万亿级湖仓一体架构下的统一数据服务平台应用实践.pdf

    湖仓一体架构是现代大数据处理领域的一个重要发展方向,它结合了数据湖(Data Lake)的灵活性和数据仓库(Data Warehouse)的高效分析能力,旨在提供一个统一的数据服务平台。该架构允许企业以更敏捷的方式处理结构...

    海量数据处理 百度、腾讯、Google面试

    例如,寻找100万个数中最大的前100个数,可以使用一个100个元素的最小堆来实现。 3. **Bit-map**:Bit-map是一种高效的数据存储方式,用一个bit位来表示一个元素的Value。在处理海量数据时,例如有限的内存空间,...

    腾讯技术 大数据分析关键技术与服务创新 共37页.pptx

    1. **云计算**:为了解决大数据处理的挑战,云计算提供了大规模分布式计算的解决方案,通过虚拟化技术整合资源,提供低成本、易于扩展的服务。它解决了传统计算的高成本、资源分散等问题,降低了能耗并有利于环境...

    1.4亿在线背后的故事-——-腾讯-QQ-IM后台架构的演化与启示.ppt

    腾讯 QQ IM 后台架构的演化与启示是指腾讯QQ即时通讯(IM)后台架构的演化过程和启示,从十万级到亿级在线的整个过程中,吸取了很多教训,对海量服务的理解是长期积累的结果。 演化过程可以分为三个阶段:IM 后台 ...

    腾讯CKV海量分布式存储系统——日访问过万亿次背后的技术挑战.pdf

    它在微信平台、开放平台、腾讯云、游戏和电商平台中得到广泛应用,应对日访问量超过万亿次的挑战。该系统的特点包括低成本、可扩展性强、高性能、高可用性、高数据持久性以及完善的运维体系。与流行的开源NoSQL解决...

    延云YDB 大数据 万亿数据秒查

    这些项目已经在实际应用中处理了超过数万亿条数据,证明了其在大规模数据处理方面的能力。 **2. YDB架构** YDB采用了先进的分布式架构,结合了Hadoop的分布式文件系统(HDFS)以及Spark计算框架的优势。具体而言,...

    20210520-广发证券-腾讯音乐-TME.US-音乐收入提速,全渠道长音频用户1.9亿+.pdf

    - 全渠道长音频用户数量达到1.9亿,移动设备月活用户达1.23亿,IoT设备接入用户达6900万。 - 音乐与长音频内容的协同效应体现在音乐用户自然转化为音频用户,以及整体用户时长的共同增长。 3. 投资建议: - 分析...

    腾讯笔试试题整理(包括答案)

    - **题目描述**:在1亿个浮点数中找到最大的1万个数,要求具有较好的时间复杂度。 - **解答思路**: - 使用最小堆数据结构来维护当前已经找到的最大值集合。 - 可以考虑使用二分查找或快速排序等算法来优化查找...

    腾讯云数据中心操作系统Gaia介绍.pptx

    首先,Gaia解决了可扩展性问题,能够处理每天万亿条实时接入的数据,单个集群规模可达到6000台服务器,支持超过120万个Job的日常运行。其次,它提供了高并发任务调度能力,可以服务于MapReduce等离线业务以及实时...

    腾讯php工程师笔试题

    - 数据分片:将大表拆分为多个小表,每个小表包含一部分数据,可以分布式存储,减少单表查询压力。 - 前缀索引:如果QQ号码长度固定,可以考虑使用前缀索引来进一步缩小查询范围。 - 使用内存数据库:如InnoDB的内存...

    腾讯Hermes实时检索分析平台.pdf

    - **目标与优势**:Hermes旨在为公司内部的大数据分析业务提供一套实时的、多维的、交互式的查询、统计和分析系统,使万级维度、千亿级数据下的秒级统计分析成为可能。相较于传统的关系型数据库集群或内存计算平台,...

    靳志辉:大规模主题模型建模及其在腾讯业务中的应用

    腾讯效果广告平台部的Peacock大规模主题模型机器学习系统,通过并行计算可以高效地对 10亿x1亿 级别的大规模矩阵进行分解,从而从海量样本数据中学习10万到100万量级的隐含语义。该系统应用到了腾讯业务中,包括 QQ ...

    40页PPT分享万亿级交易量下的支付平台设计 - 云+社区 - 腾讯云1

    伴随着交易量从1000亿到万亿级别的跃升,苏宁支付平台的处理能力也从最初的100笔/秒提升至20万笔/秒,展现了其强大的技术革新能力。\n\n演进的驱动力主要来自两方面:一是业务需求的快速响应,苏宁的O2O模式使得业务...

    腾讯2008校园招聘应聘指南

    - 在互联网协会的网络游戏排名中,腾讯与联众、盛大并列前三。 - 全球最流行网站排名中,腾讯一度超越Google位列第二。 - 一季度IM(即时消息)最高在线用户数达到3406万,稳居榜首。 - 2007年第一季度,QQ继续保持...

    微博大爆发 腾讯和新浪注册用户均超两亿.docx

    5. 腾讯微博的用户规模:腾讯凭借庞大的社交网络基础,微博注册用户达到2.33亿,尽管活跃用户数有所下滑,但平台转化的用户增长迅速,腾讯将继续强化名人效应和媒体合作。 6. 搜狐微博的市场定位:虽未公布具体用户...

    2020年中国在线教育平台用户大数据报告—腾讯课堂数据篇1

    腾讯课堂作为重要的在线教育平台,截至报告发布时,已累计入驻机构超过7.2万家,课程数量达到17.8万个,每周最高有约120万用户参与上课。全年的用户报名课程总数达3430.6万次,累计学习时间长达7531年。课程分类主要...

    腾讯大数据之--实时精准推荐-LAMDAGROUP

    该平台拥有超过5000台服务器,超过100,000个CPU核心,300TB以上的内存以及700,000块硬盘,总存储容量超过100PB,每天处理的作业数量超过1000万个,每天扫描的数据量达到6PB以上,且系统利用率非常高。 2. **TRC实时...

Global site tag (gtag.js) - Google Analytics