这是一本有可能让我提前掉头发的书
2010-07-30
传说功力不强的人阅读高深的武功秘籍容易伤身甚至走火入魔。看来这本书已经逼近自己的极限。
不过好消息是挺过这个过程传说功力就能上一甲子。
我阅读本书的前两章是一个翻过－》退回去－》再翻过的痛苦过程，直到我把所有东西都搞懂。如同前言所说，不要急着看完它，多想想。
相比某些奇技淫巧华而不实的编程难题，书中列举了许多现实中实实在在的困难需求，以及魔法一般的解决方法。这些方法在我看来是如此帅气，以至于有的我即使看了答案，还要花1天甚至更久的时间来理解（感谢电力出版社那个烂烂烂的翻译）。
比如这个问题 编程珠玑（第二版）第二章 问题A
给定一个包含32位整数的顺序文件，它至多包含40亿个这样的整数，并且次序是随机的。请查找一个此文件不存在的32位整数（2^32>40亿，所以必然有遗漏）。内存空间只有上百字节以及若干备用文件的磁盘空间可以使用
http://www.cs.cmu.edu/afs/cs.cmu.edu/academic/class/15750-s04/www/HW4_sol.txt
天杀的这答案翻译还翻译错了，我花了一天的时间想了一下，然后看了上面的链接，再想了半天，总算明白了。网上有网友的解释跟代码实现，但我一看，错了。作者明明白白的说明，这个解法，不需要对表进行排序。而网友给出的答案，是对表进行分割，然后分割到小文件可以放进内存以后，进行排序，这不是作者答案的意思。
我自己还在学习笔记里记下：二分查找法之前需要对表进行排序。现在看了这个问题以后，完全推翻了笔记中的结论。作者之前说明，只要给定一个范围，并且能将这个范围二分，并且保证答案就在这个更小的范围里头，或者原本就不存在就可以了。
实际的答案意思是（如同大学里某些牛人教授，跳过了关键解题步骤，让我这种一般人情和以堪）：算法读取所有记录，将他们分为高位为1，以及高位为0两类放到不同文件里（用低位也可以），这个过程不需要多少工作内存，几十个byte足够。
ok，书作者没有说清楚的在这里。通过这次分拣，他就知道遗漏的数字在哪一堆，不需要排序。why？因为第32位为1的数字必定有2^31个，算法中必定有个计数器，做完跟2^31比较一下，比它小的话，那么遗漏的数字肯定就在这一堆。
依次类推，在遗漏数字的这一堆，再二分为31位为1跟31位为0两堆，再二分……
刚刚发现这个东西，絮絮叨叨写出来作为笔记，高手勿笑，谢谢观看，再见！