技术头条 - 一个快速在微博传播文章的方式     搜索本站
您现在的位置首页 --> 算法 --> 如何使用1M的内存排序100万个8位数

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

浏览:10910次  出处信息

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

   最早这个问题是在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的空间。接下来的问题是如何编码这100万个差值,能尽可能压缩空间,作者举出了算数编码来解决这一问题,最终给出所需要的内存为小于1070312.5bytes。另外还给出了一个针对该问题的哈夫曼编码解决。算数编码看懂了,但是怎样运用到解决本问题中,还不是太明白。同时作者也给出了339行的解决问题的实战代码。

   系列博客链接:1 2 3 4

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


建议继续学习:

  1. 快速排序(Quicksort)的Javascript实现    (阅读:10095)
  2. 腾讯-1亿个数据取前1万大的整数-题解答    (阅读:9047)
  3. 深入浅出插入类排序算法(直接插入, 折半插入, 希尔排序)    (阅读:6192)
  4. 深入浅出交换类排序算法(冒泡排序,快速排序)    (阅读:5989)
  5. Java程序员必知的8大排序算法    (阅读:4460)
  6. Mysql中的排序优化    (阅读:4365)
  7. Vim(gVim)对排序的妙用    (阅读:4225)
  8. 快速排序详细分析    (阅读:3956)
  9. 深入浅出选择类排序算法(简单选择排序,堆排序)    (阅读:3757)
  10. 排序算法 Sleep Sort    (阅读:3159)
QQ技术交流群:445447336,欢迎加入!
扫一扫订阅我的微信号:IT技术博客大学习
© 2009 - 2024 by blogread.cn 微博:@IT技术博客大学习

京ICP备15002552号-1