编程珠玑

参考资料

• 编程珠玑

开篇

磁盘文件排序

• 考虑内存解决 -> 归并排序 -> 桶排序优化 -> 最后决定位图
• 总而言之, 考虑输入的特征 / 问题本质 / 权衡时空

啊哈, 算法

给定一个包含 40 亿个 32 位整数的数组, 找出其中缺失的整数

• 位图肯定秒杀
• 正解, 二分数字范围, 减治

旋转数组

• 力扣原题

统计变位词

• 用每个词的排序作为 key, 统计出现次数

数据决定程序结构

• 能用小程序解决的问题, 就不要用大程序
• 更一般性的问题往往更容易解决
  • 即使你的程序仅仅解决了一个特殊情况, 也不如解决一个更一般的问题更简单

编写正确的程序

程序验证

• 循环不变式证明二分搜索的正确性 (详见离散数学)
• 使用断言检查中间步骤结论正确性
• 数学证明 + 验证语言 (断言)

编程小事

• 以上我们的工作包括
  • 分析理解问题
  • 设计算法并选择合适的数据结构
  • 验证算法正确性
• 现在可以开始编写程序并且进行软件测试

程序性能分析

• 讲了一堆古老的性能分析策略, 太简单
  • 问题定义 (少做无用功)
  • 软件架构 (用于支撑调优)
  • 数据结构与算法选择
  • 调优
  • 系统 (绕过操作系统)
  • 硬件 (考虑缓存, 指令流水线等)

粗略估算

• 基本技巧
  • 多角度估算
  • 量纲检验
  • 经验
• 72 法则, 年利率 \(r%\), 年数 \(n\) 期, 若 \(r \times n \leq 72\), 则大概会翻倍
• 一年是 \(3.155 \times 10^7\) 秒, 换言之, \(\Pi\) 秒就是一个纳世纪
• 系统中物体的平均数量等于物体离开系统的平均速率和每个物体在系统中停留的平均时间的乘积

算法设计技术

最大子数组和

• 力扣原题

代码调优

• 减法代替取余 (显然需要一次增长不超过模数)
• 内联
• 哨兵代替边界检查
• 空间换时间
• 利用输入数据的特征

节省空间

• 稀疏数据结构
• 弱拷贝
• 内存池
• 奇技淫巧, 不浪费即可, 何必如此

排序

• 略

取样问题

从 \(0\) - \(n\) 中随机输出 \(k\) 个有序整数

• 顺序遍历, 动态概率
• 直接生成随机数去重
• 直接打乱 \(0\) - \(n\) 然后取前 \(k\) 个

搜索

• 略

堆

• 略

字符串

最长重复子串

• 后缀数组