数据规模分析
不考虑操作系统的区别,通常将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的最小值即可。与使用堆的过程如出一辙。
分享到:
相关推荐
腾讯效果广告平台部的Peacock大规模主题模型机器学习系统,通过并行计算可以高效地对 10亿x1亿 级别的大规模矩阵进行分解,从而从海量样本数据中学习10万到100万量级的隐含语义。该系统应用到了腾讯业务中,包括 QQ ...
模板1-数据仓库项目计划 模板2-命名规范 模板3_访谈提问和沟通记录单模板 模板4_公共数据资源管理调研模板 模板5_公共数据资源管理分析模板 模板6-报表需求梳理 内部分享-基于 Hudi 和 Kylin 构建准实时高性能数据...
"商业保险"互联网大数据分析报告全文共8页,当前为第1页。"商业保险"互联网大数据分析报告全文共8页,当前为第1页。"商业保险"互联网大数据分析报告 "商业保险"互联网大数据分析报告全文共8页,当前为第1页。 "商业...
LDA是一个简洁、优雅、实用的隐含主题模型,腾讯效果广告平台部(广点通)的工程师们为了应对互联网的大数据处理,开发了大规模隐含主题模型建模系统Peacock,通过并行计算对10亿x1亿级别的大规模矩阵进行分解,从而...
Prepared on 22 November 2020 Prepared on 22 November 2020 医疗大数据分析报告(1)全文共5页,当前为第1页。医疗大数据分析报告 医疗大数据分析报告(1)全文共5页,当前为第1页。 大数据的意义在于提供"大见解":从...
市场更新作品评论量 数据统计显示,第30周更新作品评论量最大,为917万个,28周更新作品评论量最小 ,为685万个。 数据统计显示,7月有妖气平台更新作品评论量占比45%,位列第一名,动漫之家、动 漫屋、网易紧随其后...
关键词:循证、患者数据库 医疗大数据分析报告(3)全文共4页,当前为第1页。降低再入院率:看病费用之所以上涨,原因之一是因为患者离开医院30天内,再入院率居高不下。利用大数据分析,按照过往记录、图表信息和...
腾讯电脑管家历史装机量超过3.5亿,帮助1亿网民,修复六十多亿次漏洞,网页防火墙日拦截超过2200万次,恶意URL网址日拦截超过1500万次,日云查总次数超过145亿次,日拦截病毒木马逾2000万次,腾讯电脑管家已荣获AV-...
关键词:循证、患者数据库 医疗大数据分析报告(2)全文共4页,当前为第1页。降低再入院率:看病费用之所以上涨,原因之一是因为患者离开医院30天内,再入院率居高不下。利用大数据分析,按照过往记录、图表信息和...
第一部分,我们介绍苏宁支付平台的演进路线, 架构演进的驱动与目标 第二部分介绍现在正在运行的总体架构设计,包括总体业务架构设计,总体系统架构设计,总体技 第二是
1.5.6. 输入两个整数 n 和 m,从数列 1,2,3.......n 中 随意取几个数 ....... 116 1.5.7. 输入一个表示整数的字符串,把该字符串转换成整数并输出.............. 118 1.5.8. 给出一个数列,找出其中最长的单调...
项背景:腾讯看点数据中-实时数据分析系统万亿条/天实时数据分析系统-案选型Ø 实时计算引擎:实时计算引擎准确性容错机制延时吞吐量易性业界使Checkpoint轻
65亿美元-较2一轮+C+轮)估值 67亿美元具有一定折价 退出路径明晰 IPO退出:标的2019年上市-预计2市市值120-150亿美元 第1方转让退出:若2020年O没有以%0-100亿美元市值IPO-大股4以 年08%回购 二手车市场数据分析...
腾讯有幸在大浪潮里能够有这么好的—个机遇,包括现在和未来都会有很多新的机遇涌现,更关键还是靠人的意识,是不是真正能去把握好的机遇。 时刻保持创新。中国企业不仅要和国际企业比拼服务,更要拼创新和核心技术...
预测2015年中 国云计算产业规模最高达1万亿元。事实证明,互联网行业、商业智能与咨询服务领域、 零售行业尤其快速消费品领域收益最大。在过去几年中,应用大数据的市场主体主要局 限在互联网巨头、电信运营商等大数...
AI大模型方面,腾讯表示正大力投入人工智能与云基础设施建设,腾讯混元AI大模型覆盖NLP(自然语言处理)、CV(计算机视觉)、多模态等基础模型和众多行业与领域模型,还推出了万亿中文NLP预训练模型。 具体应用方面...
报告显示,2018年中国数字经济规模已经达到29.91万亿元,数字经济占比继续提升,2018年中国GDP总量的1/3借助数字技术实现,数字中国初具规模。 报告包含“数字中国指数”,下设数字产业、数字文化、数字生活以及...
其每秒接入的数据峰值达到了2.1亿条,每天接入的数据量达到了17万亿条,每天的数据增长量达到了3PB,每天需要进行的实时计算量达到了20万亿次。 近年来大数据技术的发展,特别是HDFS和HBase这些大数据存储系统以及...
工信部 预测数据显示,到2020年,大数据相关产品和服务业务收入将突破1万亿元,复合年增长 率保持在30%左右。 目前,三大电信运营商也进入大数据争夺战当中。中国移动早在2016年就率先 提出了"大连接"战略。中国电信...
抖音,2016 年 9 月上线,经过 1 年 5 个月,日活超 过 1 亿,成为中国移动互联网继微信之后,成长最快的产品;2019 年 7 月,抖音日活达到 3.2 亿;2020 年 1 月,抖音日活超过 4 亿。腾讯,中国互联网巨头,在前期...