一,题目:
如何在1MB的空间里面对一千万个整数进行排序?并且每个数都小于1千万。实际上这个需要1.25MB的内存空间。
1MB总共有838,8608。所以估计也可以在1MB左右的空间里面进行排序了。
二,分析:
1)基于磁盘的归并排序(耗时间)
2)每个号码采用32位整数存储的话,1MB大约可以存储250 000 个号码,需要读取文件40趟才能把全部整数排序。(耗时间)
3)位图法,采用一个1千万位的字符串表示每个数,比如{0,2,3}表示为 1 0 1 1 0 0 0 0 。遍历每一个整数,有则标记为1,否则标记为0。然后按顺序输出每个整数。这种方法实际需要1.25MB内存,如果可以方便弄到内存的话可以采用此种方法。
4)假如严格限制为1MB,可以采用的策略:两次遍历或者除去第一位为0或1的整数。
解释:考虑到没有以数字0或1开头的电话号码,可以省略对这些数的操作。
两次遍历:对 1 ---4999 999之间的数排序,需要存储空间为:5000 000/8 =625 000 字节(8为一个字节中的位数)
对 5000 000 -10000 000 之间的数排序。
如果需要采用k趟算法,方法类似。
三,源码:
四,课后的题目:
1、使用库函数来进行排序
使用set容器
2、使用位运算
3、比较位图排序与系统排序
位图排序是最快的,针对这个问题而言,qsort比stl sort速度快。
4、随机生成[0, n)之间不重复的随机数(关键思想为:先把所有可能数顺序放到数组,然后打乱顺序,则保证不重复)
5、如果1MB是严格控制的空间,如果数据有1.25MB的bit数目。那么应该是需要读取2次。
k = 需要跑几趟直接用 需要排序的数据量/内存空间bit数,往上取整则可。
时间开销 = kn
空间开销 n/k
注意的是,每次在扫描的时候,取数据的范围是不一样的。
6、如果每个数据出现最多10次,那么需要4个bit位来刻录一个数。这时存储空间减小至原来的1/4。
那么如果一定要按照bitmap的方式来进行处理,则需要利用5题中的结论。
7、问题:[R. Weil]本书1.4 节中描述的程序存在一些缺陷。首先是假定在输入中没有出现两次的整数。如果某个数出现超过一次的话,会发生什么?在这种情况下,如何 修改程序来调用错误处理函数?当输入整数小于零或大于等于n时,又会发生什么?如果某个输入不是数值又如何?在这些情况下,程序该如何处理?程序还应该包含 哪些明智的检查?描述一些用以测试程序的小型数据集合,并说明如何正确处理上述以及其他的不良情况。
如果某个数出现超过一次的话,会发生什么?
会被忽略掉, 因为原来的程序本身就是用来处理只出现一次的情况的。
在这种情况下,如何修改程序来调用错误处理函数?
当输入整数小于零或大于等于n时,又会发生什么?
会出现访问越界的情况。-1访问时,会访问a[-1]的31个bit位。
如果某个输入不是数值又如何?在这些情况下,程序该如何处理?
输入可能是浮点数,或是字符什么的~~
可以先读入字符串,再用atoi转换成为整形数,如果失败,则进行出错处理。
程序还应该包含哪些明智的检查?
8、免费电话号码至少有800,878,888等,那么如何查看一个号码是否是免费号码。?
第一种方案:如果是一千万个电话号码都有可能成为免费号码,那么至需要1.25MB * (免费号码前缀个数)。
第二种方案:省空间,多次扫描文件:
1、首先扫描整个文件,看有哪个免费号码前缀。以及每个免费号码前缀下的号码个数。
2、设置区间映射表:比如800前缀有125个免费号码,找到最大的数,与最小的数,差值做为bit长度。
第三种方案:建立索引的方式来进行处理。以最后7位为索引,后面800,878什么的,为值。如果不是免费号码,应该是不用加入到这个hash表中。
9、避免初始化问题
做法是:使用两个等长的辅助数组,比如要把a[n]初始化,那么在第一次访问时:
b[i] = top;
c[b[i]] = i;
++top;
给出示例代码
分享到:
相关推荐
编程珠玑书后源代码编程珠玑书后源代码编程珠玑书后源代码编程珠玑书后源代码编程珠玑书后源代码编程珠玑书后源代码
我觉得不错,和大家分享! 编程珠玑 编程珠玑 编程珠玑
本资源只是“编程珠玑之第二章questionC: 求变位词问题”的简单的测试数据。
编程珠玑编程珠玑
编程珠玑和编程珠玑续两本,上传赚点分,填充填充填充
《编程珠玑(续)》是计算机...书中涵盖了程序员操纵程序的技术、程序员取舍的技巧、输入和输出设计以及算法示例,这些内容组成一个有机的整体,如一串串珠玑展示给程序员。 《编程珠玑(续)》适合各级程序员阅读参考。
编程珠玑(第二版)答案
编程珠玑 第二版 中文版 英文版 大家可以看看 还附有源代码哦!
书的内容围绕程序设计人员面对的一系列实际问题展开。作者Jon Bentley 以其独有的洞察力和创造力,引导读者理解这些问题并学会解决方法,而这些正是程序员实际编程...《编程珠玑(第2版)》是计算机科学方面的经典名著。
编程珠玑第二版及源代码实现(C/C++) 如果让程序员们列举他们喜欢的书籍,Jon Bentley的《编程珠玑》一定可以归于经典之列。如同精美的珍珠出自饱受沙砾折磨的牡蛎,程序员们的精彩设计也来源于曾经折磨他们的实际...
编程珠玑II(编程珠玑·续) 扫描版6.56M pdf格式
编程珠玑续、编程珠玑续本、编程珠玑续本、编程珠玑续本
编程珠玑 第2版 azw3格式电子书,适合kindle阅读 Jon Bentley是位于新泽西州Murray Hill的朗讯贝尔实验室计算机科学研究中心的技术委员会委员,Jon自1998年就成为Dr. Dobb's Joumal杂志的特约编辑,他的“编程珠玑”...
编程珠玑第二版英文版
《编程珠玑》第2版中文PDF+源代码,仅仅用于个人学习,传播获利违法
算法经典书籍编程珠玑第2版,这本书除了讲算法,更是讲述解决问题的思想。
编程珠玑 第2版 修订版 Jon Bentley著 黄倩等译,高清带目录,人民邮电出版社。
《编程珠玑》第一版是我早期职业生涯中阅读过的对我影响较大的书籍之一,在书中首次接触到的很多观点都让我长期受益。作者在这一版本中做了重要更新。新增加的很多例子让我耳目一新。 ——Steve McConnell,《代码...
编程珠玑是一本提升coding能力不可多得的好书,看书时,可以结合这个笔记,突出重点。