PART1. 开篇
问题描述
- 输入
- 一个至多包含n个正整数的文件
- 每个数都小于n，其中n = 10^7
- 出现重复就是致命错误
- 输出
- 升序排列的输入整数列表
- 约束
- 约1M可用内存，磁盘空间充足
策略一：外部排序
- 读入1MB数据至内存，进行内部排序
- 将排序结果写入磁盘
- 重复1，2，直至文件中数据都存入不同的临时文件中
- 多路归并
- 读入若干份临时文件的部分数据
- 且预留一部分空间做输输出缓冲区
- 执行多路归并，将输出结果存至输出缓冲区
- 输出缓冲区满，则写入目标文件，并清空缓冲区
- 重复4，直至临时文件的数据均读完
策略二：BitMap
- 严格来说，这个数组需要1.25Mb
- 步骤
- 定义/初始化bitset数组
- 遍历文件中每个整数，将对应位置1
- 遍历数组，如果该位为1，就输出对应整数
- 问题
- 1M内存都用于开辟位数组空间，不需要读取文件到内存？
- 严格只能用1M内存的话
- 拆成两半执行步骤
- 最后对两个步骤输出的文件进行一次归并排序
PART2.啊哈，算法
海量数据问题
- 至多包含40亿个随机排列的32位整数的顺序文件
- 找出一个该文件不包含的一个整数
- 条件
- 1G内存下如何解决
- 10MB内存如何解决
A. 将文件分成若干块临时文件,每块大小，小于等于10MB
B. 假如块大小是1000，则第一块是0-999，第二块1000-1999....
C. 每块有一个计数器，每读入一个数，所在块相应计数器加一
D. 找到一个计数器值小于1000的块，使用bitMap策略
- 相关链接
- Cracking the coding interview--Q12.3(10.3)
- BitMap算法
旋转数组
- 例子
- 假设n=8,i=3
- 向量abcdefgh 旋转之后得到 向量defghabc
- 策略：3次反转
- reverse(0, i-1); // cbadefgh
- reverse(i, n-1); // cbahgfed
- reverse(0, n-1); // defghabc
变位词
- 问题描述
* 给定一本英语单词词典
* 找出所有变位词集 - 解决步骤
* 每个单词均按字典序排序,作为原单词的签名
* 对所有单词按照其签名排序
* 变位词分组，形成变位词集
image.png
PART3.数据决定程序结构
- 能用小程序实现的，就不要编写大程序
- 更一般性的问题也许更容易解决
- 困难
直接编写解决23种情况的问题很困难
- 容易
编写一个处理n种情况的通用程序再令n = 23得到结果
- 困难
- 数据结构对软件的贡献
- 将大程序缩减为小程序
- 节省空间、时间
- 提高可移植性、可维护性
在节省时间、空间方面无计可施时
- 跳脱代码，退回起点，研究数据
- 使用数组重新编写重复代码
- 封装复杂结构
- 尽可能用高级工具
超文本键值对数据库正则表达式
- 从数据得出程序的结构
使用恰当的数据结构代替复杂的代码编码前彻底理解输入、输出和中间数据结构围绕数据结构构建程序
- 数据的表示形式是程序设计的根本
PART4.编写正确的程序
如何编写正确的程序
- 正确的问题定义
- 巧妙的算法设计
- 正确的数据结构选择
- 编程技巧：编写正确的代码
验证程序正确的方法
- 使用测试用例
- 优点
有效易用易于理解方便检测错误
- 缺点
对程序有很深的理解
- 优点
- 使用断言式注释
- 使用情景
代码初次编写完，进行初次模拟之时
- 违反断言语句的情况即指明了程序的错误所在
- 使用情景
编写简单代码是编写正确程序的关键
例子：折半查找
实现需注意的细节及优化
- 两种情况[0,n),[0,n]
- 注意（min + max）/ 2溢出问题
- 半改变min或max时，防止出现死循环
相关链接
- 断言的用法
- 折半查找实现相关
PART5.编程小事
- 脚手架： 赶脚就是各种可以测试该程序的代码或工具
- 编程中的细节问题
- 使用断言assert
- 自动化测试
PART6.程序性能分析
程序性能提升的几个方面
- 算法和数据结构
二叉树
- 算法调优
使用较大时间步
- 数据结构重组
产生适合树算法的簇
- 与系统无关的代码调优
单精度浮点代替双精度浮点数
- 与系统相关的代码调优
使用汇编语言重新编写关键函数
- 硬件
浮点加速器
程序员优化代码的非条件反射
- 更改算法
- 优化排队纪律
- 考虑所有方面，选择最大加速而所耗精力最少的方面
PART7. 粗略估算
- 任何计算的输出最多只和其输入一样好
- 两个答案总比一个答案好
- 72法则
- 问题
- struct node{int i; struct node *p;};
- 200万个这样的节点能否装入128MB的内存中
- 结论
- 假设int占4字节，指针亦占4字节，即总共8字节
- 两百万个节点仅需16MB
- 但每个节点除了8字节以外，还额外多占用了40字节的空间
- molloc的分配器分配了连续的指针，每个指针分配的大小为48字节
PART8.算法设计技术
问题：求连续子数组的最大和
策略一：立方算法
策略二：平方算法
-
方法一
-
方法二
策略三：分治算法
策略四：扫描算法
image.png
算法设计原则
- 保存状态，避免重新计算
- 将信息预处理到数据结构中
- 分而治之
- 扫描，保存旧答案和一些辅助数据，以计算新答案
PART9.代码调优
问题一：整数求余
- k = （j + rotdist）% n;
- k = j + rotdist;
- while(k >= n) k -= n;
- k = (j + rotdist) - [floor( (j + rotdist) / n ) * n]
问题二：函数、宏以及内联代码
float max（float a, float b）
return a > b ? a : b;#define max(a, b) (a > b ? a : b)
问题三：顺序寻找
原始代码
-
减少判断测试代码
- 该改动，x[n]越界问题不考虑吗？
循环展开代码
折半查找优化代码
image.png
代码优化原则：尽量少用代码优化
PART 10. 相关链接
偶滴水平有限，总结的也比较简陋，后面几章也因为之前准备找工作，木有时间总结啦，下面附上牛人的一篇《编程珠玑》读薄，以表敬仰之情~
