《编程珠玑》学习笔记-第1、2章

《编程珠玑》学习笔记

第一部分

第1章 开篇（2018.07.11）

ü 抛出问题：“怎样给一个磁盘文件排序”

ü 引导明确问题：输入：最多包含N个正整数，每个书都小于N，N=10⁷，无重复、关联数据；

输出：按升序排列的整数列表；

约束条件：最多约1MB内存空间可用，充足的磁盘存储空间可用，运行时间最多几分钟，10秒就无需再优化。

ü 程序设计：起点：基于磁盘的归并程序实现

利用排序问题的特殊性：每个号码7byte，1MB可存143000个；如每个号码32位证书，1MB可存250000个。可使用输入遍历文件40趟，内存中用快排完成排序。

优化：利用位图数据结构，集合中数值位都置1，其他位都置0。

小结：1、对小问题的仔细分析有时可以得到明显的实际益处。

2、位图数据结构：描述了一个有限定义域内的稠密集合，其中的每一个元素最多出现一次并且没有其他任何数据与该元素相关联。

3、时间—空间折中与双赢。空间需求的减少会导致运行时间的原因：处理的数据变少了，意味着处理数据所需的时间变少了；同时将这些数据保存在内存中而不是磁盘上，进一步避免了磁盘访问的时间。   

第2章 啊哈！算法

ü 抛出问题：A：文件包含最多40亿个随机排列的32位整数，需要找出一个不存在  

于该文件中的32位整数。

B:仅使用几十个字节的额外空间将一个N元向量X在正比于N的时间内向左旋转i个位置。

C:给定一本英语单词字典，要求找出所有的变位词分类。

ü 解决思路：A:二分搜索：定义范围、元素的表示方式、探测确定哪一半范围存在缺失整

数;

B:将问题看做是把数组AB转换成BA，同时假定拥有一个将数组中特定部分元素求逆。首先对A求逆，得到A^rB，然后对B求逆，得到A^rB^r，最后整体求逆，得到（A^rB^r）^r，此时恰好是BA。

C:选择基于排序的标识、集中具有相同标识的单词。

小结：1、排序最显而易见的用处是产生有序的输出。

2、二分搜索在有序表中查找元素时极为高效，并且可用于内存排序或磁盘排序。