如何使用1M的内存排序100万个8位数

新浪微博 QQ空间

今天看到这篇文章,颇为震撼,感叹算法之“神通”。借助于合适的算法可以完成看似不可能的事情。

最早这个问题是在Stack Overflow网站上面给出的(Sorting numbers in RAM):

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行的解决问题的实战代码。

系列博客链接:1 2 3 4

另外文中也提到了另外一位程序员使用其他办法解决了该问题:Nick Cleaton

新浪微博 QQ空间

| 1 分2 分3 分4 分5 分 (4.00- 5票) Loading ... Loading ... | 这篇文章归档在:奇趣见闻, 算法数据结构 | 标签: . | 永久链接:链接 | 评论(3) |

3 条评论

  1. sin2800
    评论于 八月 13, 2014 at 16:34:52 CST | 评论链接

    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 字节

    • 童燕群
      评论于 八月 13, 2014 at 21:24:53 CST | 评论链接

      你的计算更严谨细致,赞!

    • 匿名
      评论于 九月 14, 2014 at 12:33:44 CST | 评论链接

      缺少对不定长Step的考虑哦~连续两个数字只差可能为1,也可能为1000 0000,如何设计这个玩意才是重点吧。
      当然,哈夫曼是贪心最优解,也是全局最优解。但是否可参考类似Unicode->UTF-8的方案。

评论

邮箱地址不会被泄露, 标记为 * 的项目必填。

8 - 2 = *



You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <img alt="" src="" class=""> <pre class=""> <q cite=""> <s> <strike> <strong>

返回顶部