• 网站首页
• 网站建设
• 短视频
• 网站推广
• 网站模板
• 客户案例
• 资讯动态
• 关于我们

20亿数字的文本排序_数据库

当前位置：网站建设 > 技术支持

20亿数字的文本排序？

使用堆的时间复杂度为O(n log k)（n为元素个数，k为取前多少个数），而使用Quickselect的平均时间复杂度为O(n)，优于使用堆的算法，而且显然已经是理论下限。 @D Flip Flop 是这题下第一个提出这一正确思路的（看不懂或不想看上面的英文维基百科链接的话，我简单搜了一下找到一篇中文介绍选取第K大数的快速选择算法和注意事项 | Comzyh的博客）如果非得担心naive实现中的O(n^2)最坏时间复杂度，我们有Median of medians可以以最坏时间复杂度O(n)求出中位数，在Quickselect中总是以中位数作为主元（pivot）即可保证最坏时间复杂度仍为O(n)。当然，这样做会带来非常大的常数惩罚，因此只有渐近分析上的意义，实践中无意义。（中文介绍十四、第三章再续：快速选择SELECT算法的深入分析与实现 - Hibernate4 - 博客园，这篇包含了普通的Quickselect）本题要求的20亿个数，每个32位的话总共大约7.5G，每个64位的话大约15G，当代（2016年12月）的服务器单机内存一般都放得下。如果考虑内存放不下的情况，可以将文件分成数块（数量记为m）保证每一块都能放进内存，依次处理每一个块，用上述算法求出每块的前k个数并存在内存里，然后将这m份“前k个数”合并成一个数组，再用上述算法求出这mk个数中的其前k个数即可

==============================================

做了一下实验，在我自己的笔记本上，n=2000万 k=100时 Quickselect vs 堆 大约是0.15s vs 0.9s，n=2亿 k=100时大约是0.9s vs 9s，优势还是很明显的（时间均不含读取文件时间，因为用当场生成随机数代替了读文件……我的辣鸡机械硬盘读文件太慢了orz）算法用C++实现，堆用的是C++标准库的priority_queue，开O2编译。评论区还有人提到cache的问题，其实我因为上学期做某课大作业，还真有一个模拟器可以分析缓存性能的……不过懒得为这道水题开了orz

版权说明：
本网站凡注明“广州京杭 原创”的皆为本站原创文章，如需转载请注明出处！
本网转载皆注明出处，遵循行业规范，如发现作品内容版权或其它问题的，请与我们联系处理！
欢迎扫描右侧微信二维码与我们联系。