如何使用1M的内存排序100万个8位数
今天看到这篇文章,颇为震撼,感叹算法之“神通”。借助于合适的算法可以完成看似不可能的事情。
最早这个问题是在Stack Overflow网站上面给出的(Sorting numbers in RAM):
题目:
提供一个1M的ROM和1M的RAM,一个输入流和一个输出流。程序代码最终烧录在1M的ROM中,程序可以使用1M的RAM进行运算。输入流中依次输入100万个8位的整数,要求输出流中输出这100万个数排序后的结果。
已经可以搜索到很多解法了,今天看到一个国外的程序员的分析,觉得很有趣,想把他的分析过程简单转在这里。简单一看,根本不可能,100万个8位数无论如何也不能在1M的内存里装下。排序过程是利用归并排序,效率较高。最难的地方是在如何将排序后的100万个数字存下来。换一种思路,不一定要存下每一个数字本身,因为数字都已经排序了,那么相邻两个数字之间的差值是非常小的,如果在极端的情况下,两个数字之间的差值非常大,那么必然会有更多量的相邻数字之间的差值更小,因此存下所有的100万个数字的差值需要的空间是可以估算的。平均每一个差值的大小为:10^8/100万 = 100,100需要7个bit位来表示,因此共需要100万×7 = 875, 000 字节,不到1M的空间。接下来的问题是如何编码这100万个差值,能尽可能压缩空间,作者举出了算数编码来解决这一问题,最终给出所需要的内存为小于1070312.5bytes。另外还给出了一个针对该问题的哈夫曼编码解决。算数编码看懂了,但是怎样运用到解决本问题中,还不是太明白。同时作者也给出了339行的解决问题的实战代码。
另外文中也提到了另外一位程序员使用其他办法解决了该问题:Nick Cleaton。
建议继续学习:
- 快速排序(Quicksort)的Javascript实现 (阅读:10095)
- 腾讯-1亿个数据取前1万大的整数-题解答 (阅读:9047)
- 深入浅出插入类排序算法(直接插入, 折半插入, 希尔排序) (阅读:6192)
- 深入浅出交换类排序算法(冒泡排序,快速排序) (阅读:5989)
- Java程序员必知的8大排序算法 (阅读:4460)
- Mysql中的排序优化 (阅读:4365)
- Vim(gVim)对排序的妙用 (阅读:4225)
- 快速排序详细分析 (阅读:3956)
- 深入浅出选择类排序算法(简单选择排序,堆排序) (阅读:3757)
- 排序算法 Sleep Sort (阅读:3159)
扫一扫订阅我的微信号:IT技术博客大学习
- 作者:童燕群 来源: 忘我的追寻
- 标签: 排序
- 发布时间:2014-11-30 23:23:24
- [52] IOS安全–浅谈关于IOS加固的几种方法
- [51] android 开发入门
- [50] 如何拿下简短的域名
- [48] 图书馆的世界纪录
- [48] Oracle MTS模式下 进程地址与会话信
- [46] 【社会化设计】自我(self)部分――欢迎区
- [46] Go Reflect 性能
- [43] 读书笔记-壹百度:百度十年千倍的29条法则
- [37] 视觉调整-设计师 vs. 逻辑
- [34] 程序员技术练级攻略