数据规模分析
不考虑操作系统的区别,通常将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的最小值即可。与使用堆的过程如出一辙。
分享到:
相关推荐
湖仓一体架构是现代大数据处理领域的一个重要发展方向,它结合了数据湖(Data Lake)的灵活性和数据仓库(Data Warehouse)的高效分析能力,旨在提供一个统一的数据服务平台。该架构允许企业以更敏捷的方式处理结构...
例如,寻找100万个数中最大的前100个数,可以使用一个100个元素的最小堆来实现。 3. **Bit-map**:Bit-map是一种高效的数据存储方式,用一个bit位来表示一个元素的Value。在处理海量数据时,例如有限的内存空间,...
1. **云计算**:为了解决大数据处理的挑战,云计算提供了大规模分布式计算的解决方案,通过虚拟化技术整合资源,提供低成本、易于扩展的服务。它解决了传统计算的高成本、资源分散等问题,降低了能耗并有利于环境...
腾讯 QQ IM 后台架构的演化与启示是指腾讯QQ即时通讯(IM)后台架构的演化过程和启示,从十万级到亿级在线的整个过程中,吸取了很多教训,对海量服务的理解是长期积累的结果。 演化过程可以分为三个阶段:IM 后台 ...
它在微信平台、开放平台、腾讯云、游戏和电商平台中得到广泛应用,应对日访问量超过万亿次的挑战。该系统的特点包括低成本、可扩展性强、高性能、高可用性、高数据持久性以及完善的运维体系。与流行的开源NoSQL解决...
这些项目已经在实际应用中处理了超过数万亿条数据,证明了其在大规模数据处理方面的能力。 **2. YDB架构** YDB采用了先进的分布式架构,结合了Hadoop的分布式文件系统(HDFS)以及Spark计算框架的优势。具体而言,...
- 全渠道长音频用户数量达到1.9亿,移动设备月活用户达1.23亿,IoT设备接入用户达6900万。 - 音乐与长音频内容的协同效应体现在音乐用户自然转化为音频用户,以及整体用户时长的共同增长。 3. 投资建议: - 分析...
- **题目描述**:在1亿个浮点数中找到最大的1万个数,要求具有较好的时间复杂度。 - **解答思路**: - 使用最小堆数据结构来维护当前已经找到的最大值集合。 - 可以考虑使用二分查找或快速排序等算法来优化查找...
首先,Gaia解决了可扩展性问题,能够处理每天万亿条实时接入的数据,单个集群规模可达到6000台服务器,支持超过120万个Job的日常运行。其次,它提供了高并发任务调度能力,可以服务于MapReduce等离线业务以及实时...
- 数据分片:将大表拆分为多个小表,每个小表包含一部分数据,可以分布式存储,减少单表查询压力。 - 前缀索引:如果QQ号码长度固定,可以考虑使用前缀索引来进一步缩小查询范围。 - 使用内存数据库:如InnoDB的内存...
- **目标与优势**:Hermes旨在为公司内部的大数据分析业务提供一套实时的、多维的、交互式的查询、统计和分析系统,使万级维度、千亿级数据下的秒级统计分析成为可能。相较于传统的关系型数据库集群或内存计算平台,...
腾讯效果广告平台部的Peacock大规模主题模型机器学习系统,通过并行计算可以高效地对 10亿x1亿 级别的大规模矩阵进行分解,从而从海量样本数据中学习10万到100万量级的隐含语义。该系统应用到了腾讯业务中,包括 QQ ...
伴随着交易量从1000亿到万亿级别的跃升,苏宁支付平台的处理能力也从最初的100笔/秒提升至20万笔/秒,展现了其强大的技术革新能力。\n\n演进的驱动力主要来自两方面:一是业务需求的快速响应,苏宁的O2O模式使得业务...
- 在互联网协会的网络游戏排名中,腾讯与联众、盛大并列前三。 - 全球最流行网站排名中,腾讯一度超越Google位列第二。 - 一季度IM(即时消息)最高在线用户数达到3406万,稳居榜首。 - 2007年第一季度,QQ继续保持...
5. 腾讯微博的用户规模:腾讯凭借庞大的社交网络基础,微博注册用户达到2.33亿,尽管活跃用户数有所下滑,但平台转化的用户增长迅速,腾讯将继续强化名人效应和媒体合作。 6. 搜狐微博的市场定位:虽未公布具体用户...
腾讯课堂作为重要的在线教育平台,截至报告发布时,已累计入驻机构超过7.2万家,课程数量达到17.8万个,每周最高有约120万用户参与上课。全年的用户报名课程总数达3430.6万次,累计学习时间长达7531年。课程分类主要...
该平台拥有超过5000台服务器,超过100,000个CPU核心,300TB以上的内存以及700,000块硬盘,总存储容量超过100PB,每天处理的作业数量超过1000万个,每天扫描的数据量达到6PB以上,且系统利用率非常高。 2. **TRC实时...