《编程珠玑》笔记（第06-10章）

• 第7章 粗略估算
• 第8章 算法设计技术
• 第9章 代码调优
• 第10章 节省空间

第7章 粗略估算

1. 72法则：假设以年利率r%投资一笔钱y年，金融版本的72法则指出，如果ry=72，那么你的投资差不多会翻倍。
2. pi秒就是一个纳世纪：1纳世纪=10^(-9)*100年=10^(-7)年
3. Little定律：系统中物体的平均数量等于物体离开系统的平均速率和每个物体在系统中停留的平均时间的乘积。

第8章 算法设计技术

1. 习题4：一个数组长n，每个元素都是从区间[-1, 1]中均匀选出的随机实数，那么最大子向量的期望值是多少？

   经网上搜索无解。只能用蒙特卡罗方法模拟？

2. 使用分治法求解最大连续子段和，要求时间复杂度O(n)。
   • 解：像线段树那样，每个线段保存如下状态：
     • 当前段包含左端点的和最大的子段及其右端点
     • 当前段包含右端点的和最大的子段及其左端点
     • 当前段最大连续子段和及其左右端点

     然后自底向上更新一次，共O(n)条线段。故。

3. 习题10a：查找总和最接近0的子向量。
   • 解：保存累加和，则问题等价于找到累加和数组中两个元素，使差值最小。最简单的方法是排序后遍历一遍。

     有不使用排序的O(n)算法吗？

4. 习题10b：查找总和最接近某一给定实数t的子向量。
   • 解：对累加和数组S排序后遍历，维护俩指针p1和p2使得S[p2]-S[p1]<=t而S[p2+1]-S[p1]>t即可。

5. 习题12：将数组x[0,...,n-1]初始化全0后执行类似于以下的操作n次：

   for i=[l, u] do x[i] += v
   

   其中l，u，v为每次运算的参数，求一个更快的算法达到同样效果。

   • 解：初始化y[0,...,n-1]为全0，对每个操作令y[l]+=v和y[u+1]-=v。则结束时x[i]=sigma{k=0 to i}(y[k])。正确性：只需证明每一次执行完操作之后该性质保持不变即可。
6. 书籍：Dr.Dobb’s Essential Books on Algorithms and Data Structuers

第9章 代码调优

1. 如果对内存的访问占用了大量运行时间，或程序的运行时间主要消耗在输入输出上，那么对程序中的计算进行加速是毫无意义的。
2. 对现代计算机来说，将循环展开有助于避免管道阻塞、减少分支、增加指令级的并行性
3. 性能监视（profiling）可以帮我们找到程序中的关键区域，对于其他区域，我们遵循有名的格言：没有坏的话就不要修。
4. 进行“改进”之后要用具有代表性的输入来度量程序的效果。
5. 常用法则：利用等价的代数表达式、使用内联甚至宏、使用哨兵来合并测试条件、修改数据结构、展开循环。

第10章 节省空间

1. 每次使用new来分配一个新对象所用空间会比存储该对象所需的空间大很多。因此一次性分配一个对象数组（像vector底层那样）能节省不少空间，时间也更快。
2. 节省数据空间的技术
   • 重新计算：不保存之前的计算结果
   • 使用稀疏结构
   • 信息论：压缩
   • 简单性：最重要的原则
3. 节省代码空间的技术
   • 函数定义：重用
   • 使用解释程序
   • 翻译成紧凑的机器语言