《编程珠玑》|《编程珠玑》| 由实际问题引出的实用技巧与原则

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. 相关链接 【《编程珠玑》|《编程珠玑》| 由实际问题引出的实用技巧与原则】偶滴水平有限,总结的也比较简陋,后面几章也因为之前准备找工作,木有时间总结啦,下面附上牛人的一篇《编程珠玑》读薄,以表敬仰之情~
《编程珠玑》|《编程珠玑》| 由实际问题引出的实用技巧与原则
文章图片

    推荐阅读