关于
我的项目
相关阅读
无关联文章
热度排行
- [转] 宫崎骏用动漫教给我们的人生哲理,每一句都能说到心里! - (日期:[八月 24, 2013] 点击:[53,204])
- Google 网页爬虫报告无法连接站点解决办法 - (日期:[七月 20, 2014] 点击:[38,637])
- 架设Tiny Tiny RSS(TTRSS)阅读器,找回Google Reader! - (日期:[九月 27, 2013] 点击:[27,767])
- SkyDrive、DropBox和Google Drive三大公有云存储服务对比 - (日期:[六月 25, 2013] 点击:[25,570])
- 升级到至强E5440后,与i5 CPU笔记本性能对比 - (日期:[二月 18, 2014] 点击:[23,709])
- 公钥私钥加密解密数字证书数字签名详解 - (日期:[四月 19, 2014] 点击:[22,958])
- 本站建站技术合集 - (日期:[九月 20, 2013] 点击:[22,486])
- 使用OpenerDNS解决无法访问Google的问题 - (日期:[七月 5, 2014] 点击:[21,788])
- WordPress博客添加“返回顶部”按钮 - (日期:[七月 14, 2013] 点击:[21,199])
- Linux文件系统基础之inode和dentry - (日期:[三月 13, 2015] 点击:[20,165])
- 云存储中的HTTP鉴权算法分析 - (日期:[二月 7, 2014] 点击:[18,639])
- 存储基础知识之——磁盘阵列原理及操作实战 - (日期:[二月 9, 2014] 点击:[17,490])
- 精选37条强大的常用linux shell命令组合 - (日期:[九月 4, 2013] 点击:[17,427])
- DNS原理、架构和配置详解 - (日期:[九月 6, 2013] 点击:[16,800])
- Netty和Jetty的Java NIO 网络框架模型分析 - (日期:[七月 13, 2013] 点击:[16,332])
- CoreOS 初识之安装 - (日期:[十一月 16, 2014] 点击:[16,169])
- Windows与Linux文件系统互访的几种方法 - (日期:[八月 21, 2014] 点击:[15,732])
- Dijkstra算法求解最短路径分析 - (日期:[七月 12, 2014] 点击:[14,924])
- NAS解决方案实现多媒体文件共享播放 - (日期:[十二月 21, 2014] 点击:[13,913])
- 简介 - (日期:[九月 1, 2012] 点击:[13,754])
- 如何编程实现 2 + 2 = 5? - (日期:[六月 2, 2014] 点击:[13,269])
- 搭建了一个iNews程序 - (日期:[十月 15, 2013] 点击:[13,236])
- 2014年9月曝出的Bash ShellShock漏洞简析 - (日期:[九月 26, 2014] 点击:[13,137])
- 彻底解决WordPress博客垃圾评论的问题 - (日期:[八月 5, 2013] 点击:[13,085])
- 如何使用1M的内存排序100万个8位数 - (日期:[三月 27, 2014] 点击:[12,552])
- 全部日志列表 - (日期:[十一月 11, 2012] 点击:[12,328])
- 关于回调函数和this指针探讨 - (日期:[八月 24, 2014] 点击:[12,207])
- 给定一个long型常量,其值为x,给定long型变量a,要求a & x 的取值集合 - (日期:[九月 8, 2012] 点击:[11,701])
- WordPress建站必备实用插件 - (日期:[八月 7, 2014] 点击:[11,359])
- Amazon 云计算业务全面介绍 - (日期:[三月 9, 2014] 点击:[11,268])
分类目录
文章归档
- 2024年四月 (1)
- 2024年二月 (1)
- 2023年九月 (1)
- 2023年一月 (1)
- 2022年十月 (1)
- 2022年八月 (2)
- 2022年四月 (1)
- 2022年三月 (1)
- 2021年十二月 (2)
- 2021年十月 (2)
- 2021年九月 (1)
- 2021年八月 (1)
- 2021年五月 (1)
- 2021年三月 (2)
- 2021年一月 (2)
- 2020年十二月 (5)
- 2020年十一月 (2)
- 2020年十月 (2)
- 2020年九月 (1)
- 2020年八月 (5)
- 2020年七月 (2)
- 2019年九月 (1)
- 2018年八月 (1)
- 2018年七月 (1)
- 2018年六月 (1)
- 2018年五月 (1)
- 2018年三月 (1)
- 2018年二月 (1)
- 2018年一月 (2)
- 2017年十二月 (3)
- 2017年十月 (4)
- 2017年九月 (1)
- 2017年七月 (1)
- 2017年六月 (1)
- 2016年十二月 (1)
- 2016年十月 (1)
- 2016年九月 (1)
- 2016年七月 (2)
- 2016年六月 (1)
- 2016年二月 (3)
- 2015年十二月 (3)
- 2015年十一月 (2)
- 2015年十月 (1)
- 2015年八月 (2)
- 2015年七月 (4)
- 2015年六月 (1)
- 2015年三月 (2)
- 2015年二月 (1)
- 2015年一月 (4)
- 2014年十二月 (2)
- 2014年十一月 (2)
- 2014年十月 (5)
- 2014年九月 (8)
- 2014年八月 (11)
- 2014年七月 (17)
- 2014年六月 (7)
- 2014年五月 (15)
- 2014年四月 (16)
- 2014年三月 (14)
- 2014年二月 (5)
- 2013年十二月 (5)
- 2013年十一月 (3)
- 2013年十月 (13)
- 2013年九月 (13)
- 2013年八月 (13)
- 2013年七月 (9)
- 2013年六月 (8)
- 2013年五月 (1)
- 2013年三月 (3)
- 2013年一月 (1)
- 2012年十一月 (1)
- 2012年九月 (12)
- 2012年八月 (3)
- 2011年二月 (1)
- 2009年三月 (1)
- 2009年二月 (1)
- 2008年十一月 (1)
- 2008年六月 (1)
- 2008年四月 (1)
- 2008年三月 (1)
如何使用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的空间,但是还有很多大于128的数值需要编码,这样有一些数值的编码大于7个bit。因此,接下来的问题是如何编码这100万个差值,能尽可能压缩空间,作者举出了算数编码来解决这一问题,选择一种简单的编码规则,即:看第一个bit位,如果是0,则后6个bit位表示数值,如果是1,则表示差值为64,继续读取后一位,如果仍然为1,则差值继续累加1,直到读到0,然后读取后面的6个bit,这样可以表示所有可能出现的值,这样下来,最终计算出所需要的内存为1070312.5bytes,仍然大于1M。
最终采用了一个针对该问题的哈夫曼编码解决。算数编码看懂了,哈夫曼编码也似乎看明白了,但是怎样运用到解决本问题中,还不是太明白。同时作者也给出了339行的解决问题的实战代码。
另外文中也提到了另外一位程序员使用其他办法解决了该问题:Nick Cleaton。
3 条评论
100万个8位数,最小的是1千万,最大是9999 9999,这100万个8位数就在1000 000 - 9999 9999中。9999 9999 - 1000 0000 = 8999 9999,8999 9999 / 100 0000 = 90,这100万个数的平均差值约等于90,90可以用6位来表示,即1字节表示,这样只纪录最小值,其他数只记录与前一位的差值,差值用的存储就是999 999字节,第一个最小的8位数用3个字节表示,总共就是100 0002字节,小于1M的1024 * 1024 字节
你的计算更严谨细致,赞!
缺少对不定长Step的考虑哦~连续两个数字只差可能为1,也可能为1000 0000,如何设计这个玩意才是重点吧。
当然,哈夫曼是贪心最优解,也是全局最优解。但是否可参考类似Unicode->UTF-8的方案。