编程珠玑ProgrammingPearls

Posted on | Edited on | In ,

第一章

问题

  • 开始的问题是如何对文件进行排序 -> merge sort
  • 整合问题之后，问题变成了需要对7位数字进行排序，这样的话需要的时间就远小于merge sort了

另一种方法

  • 如果在每个byte里面存一个数字，那么1MB可以存143000左右的号码（e6/7)
  • 但是如果把每个数字表示成一个32位的int（也就是说每7位数存成一个32位的整数，那么这7位数就占4个byte），那么可以存250000左右的号码
  • 从这个角度考虑，快排的速度比merge快

实现

  • 从上面的问题分析来看，用bitmap或者bit vector来表示数据很常见。
    • 比如，可以用一个20bit的string来表示{1,2,3,5,8,13}
    • 0 1 1 1 0 1 0 0 1 0 0 0 0 1 0 0 0 0 0 0
    • 在这个里面，出现在集合里的数字就表示为1，没有出现的就表示为0
  • 在实际解决问题过程中，7位数字可以表示成一个小于千万的数。如果用一个千万的二进制串来表示，那么如果整个文件里面有现在的号码的时候，这个位才被表示为1，否则就被表示为0
  • 分为三个阶段
    • 关闭所有的位，即千万个位全都是0
    • 从输入文件里面导入所有的数字，比如2897的话，就是b[2897]=1
    • 全部输入完毕之后，再根据现有存在的数字就可以直接排序，输出了

处理原则

总原则：在开始处理问题之前分析问题，才能让问题更好解决

  • 确定正确的问题 -> 最重要的一点
  • 选择了bitmap的数据结构：选择这个数据结构是根据电话号码不会重复这个特殊条件得到的
  • multi-pass
  • 时间和空间的trade off
  • 简单设计

第二章 算法

问题1：

  • 如果有最多40亿个排好序的32位浮点数，其中有遗漏的数据，如何找到遗漏的数据。考虑内存足够的时候和内存不够的时候的情况
    • 如果内存足够，可以像第一章说的一样，用位图来表示这些数据，然后看哪些没有

如果内存不够？

  • 二分查找
    • 必须定义范围，范围里面每个数字的表示方法和探测方法
    • 比如如果把这些数据分成两部分，比如1-10里面取中位数，因为缺数据的原因，总是会有一边的个数少，那么缺的数据就肯定在少的这边

问题2：

  • 将具有n个元素的向量x左旋i个位置，时间上与n成正比，有十几字节的额外空间
  • 直接方法
    • 储存到额外数组 -> 太浪费空间了
    • 定义一个函数将数组每次移动一个位置 -> 太浪费时间了（虽然时间上和n成正比）
  • 另一个思考
    • 把一个数组分成不同的组，每次把对应组的内容转移，直到所有内容都转移成功。比如把x[0]挪出去，x[3]诺到x[0],x[6]挪到3，然后0挪到6。然后再挪x[1]和他的对应的内容们
  • 另一种思考方法：旋转x实际就是把ab转换成ba
    • 如果a是前i个元素，a比b短，把b分割成b1和b2，让b2和a的长度一样
    • 那么可以先交换a和b2 -> b2 a b1
    • 然后再集中精力交换b1和b2里的元素，也就是说这可以是一个recursive的表示方法
  • 转置：这个看起来在写Leetcode的时候非常好用啊！！！但是注意在python里面reverse要自己写
    • 如果把问题看成转置，实际上数组ab可以
      • 先转置a：aTb
      • 再转置b：aTbT
      • 再转置整个数组：（aTbT）T = ba
    • 也就是说，如果abcdefg想让他旋转三位，实际上可以做到的是
      • reverse（0，2）：cbadefg
      • reverse（3，6）：cbagfed
      • reverse（0，6）：defgabc

问题3

  • 找到一个单词的变位词：比如pots和stop

解决方法

  • 注意，找到所有的可能性是很愚蠢的，比如一个22个字母的词，所有的变位22！大概是10e21，时间爆炸了
  • 核心思想 -> 排序，排序之后的变位词就都一样了
  • leetcode 242,49
    • 这个题的核心思路就是，每个单词按字母顺序排序之后的答案就是这个单词的key，如果两个单词的key一样的话这两个单词就是变位词，如果不一样的话就是新的词
    • 在python里面直接用字典可以很好的储存变位词

第三章 数据结构

数据结构的意义就是让代码可以更加简短整洁 -> 比如用数组代替循环

  • 原则：能用小程序解决的就不要用大程序
    • 把重复性代码改写
    • 封装复杂的结构
    • 尽可能使用高级工具
    • 让数据去构造程序

第四章 正确编写程序

写一个完全正确的binary search吧！

  • 注意点
    • 求中位数的时候是前后相加，除以二
    • 注意跳出循环的条件是 start> end
    • 为了满足上面的循环条件，需要每次判断完mid之后，把start或者end移动一位，不然会陷入死循环
  • 后面的9，11，14会用到程序的验证技术
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    class Solution:
        def search(self, nums: List[int], target: int) -> int:
            start = 0
            end = len(nums) - 1
            mid = (start + end) // 2
            
            while start <= end:
                if target == nums[mid]:
                    return mid
                elif target > nums[mid]:
                    start = mid + 1
                    mid = (end + start) // 2
                elif target < nums[mid]:
                    end = mid - 1 
                    mid = (start + end) // 2
            return -1

第五章 次要问题

  • 虽然每次写完了程序，大家基本都会选择把它直接插入系统，然后强烈的希望他能运行
  • （哭了，写的也太真实了）

测试用例

  • 设置极小的测试用例（比如0个，1个，2个元素等等）
  • 设置可以自动生成的测试用例
  • 计时，测试不同方法的时间

调试 -> 引发bug是会有实际的逻辑原因的，调试的时候需要关注这些问题

第六章 性能透视

在后面的三章会说到提高运行效率的三个方法，在第六章主要讲的是各个层次如何组合为一个整体

案例

  • 一个模拟天体间受力关系，来模拟运动的程序，通过对程序的改进，在n=1000的程度下，把速度从一年提升到了不到一天，速度提升系数约为400
  • 改进方法
    • 算法和数据结构，把时间复杂度n2 -> nlogn（二叉树）
    • 算法优化，优化了两个粒子靠的很近的情况
    • 数据结构重组，减少了局部计算的次数
    • 代码优化：64位浮点数改为32位，计算时间减半。用汇编重写了某个函数，给缓慢的函数加速
    • 硬件，提升了硬件
  • 算法加速不一定是独立于硬件的，比如在超级计算机上，树形结构对时间的影响就很小

设计层次

  • 问题的定义
  • 系统结构 -> 第七章，封底估计
  • 算法和数据结构 -> 2,8章
  • 代码优化 -> 9
  • 系统软件
  • 硬件：比如实现某个功能的专门硬件

原则

  • 如果需要少量加速，研究最好的层次。虽然修改算法是非常常见的答案，但是在研究之前最好考虑一下所有可能的层次。比如硬件？这种的，最好能找到一个得到最大加速，又所需精力最少的层次
  • 如果需要大量加速，需要研究多个层次。就像上面的案例一样

封底计算

在处理问题之前，需要对这个问题的规模有一个大概的估计，才能更好的处理问题

帮助封底计算

  • 两个不同方面的答案对比
  • 量纲检测
  • 经验法则
  • 实践

性能估计 + 安全系数