ARTS 打卡第四周

1. Algorithm

剑指 Offer 10- I. 斐波那契数列

写一个函数，输入 n ，求斐波那契（Fibonacci）数列的第 n 项（即 F(N)）。斐波那契数列的定义如下：

F(0) = 0,   F(1) = 1F(N) = F(N - 1) + F(N - 2), 其中 N > 1.

斐波那契数列由 0 和 1 开始，之后的斐波那契数就是由之前的两数相加而得出。

答案需要取模 1e9+7（1000000007），如计算初始结果为：1000000008，请返回 1。

示例 1：

输入：n = 2输出：1

示例 2：

输入：n = 5输出：5

提示：

• 0 <= n <= 100
  

方法一：递归（时间超限），通过优化可以 AC

方法二：动态规划

方法三：矩阵快速幂，递推：

    public int fib(int n) {        if(n==0)return 0;        if(n==1||n==2)return 1;        int[][]base={            {1,1},            {1,0}        };         int [][] res = matrixPower(base,n-1);        return res[0][0];    }    public int[][]matrixPower(int [][] m, int temp){        int[][] ret = {{1, 0}, {0, 1}};            while(temp!=0){                // 如果对应二进制位为1 则乘进去                if((temp&1)!=0){                     ret = muliMatrix(ret, m);                }                m = muliMatrix(m, m);                temp>>=1;            }        return ret;    }    public static int[][] muliMatrix(int[][] a, int[][] b) {         int[][] c = new int[2][2];        for (int i = 0; i < 2; i++) {            for (int j = 0; j < 2; j++) {                c[i][j] = (int) (((long) a[i][0] * b[0][j] + (long) a[i][1] * b[1][j]) % 1000000007);            }        }        return c;    }

2. Review

谷歌 MapReduce 论文阅读：MapReduce: simplified data processing on large clusters.

Abstract

MapReduce is a programming model and an associated implementation for processing and generating large data sets. Users specify a map function that processes a key/value pair to generate a set of intermediate key/value pairs, and a reduce function that merges all intermediate values associated with the same intermediate key.

MapReduce 通过 Map 函数对一个基于 k-v 对的数据集进行处理，生成对应的中间数据集，再通过 Reduce 函数对这些中间数据集中具有相同的 key 的 value 进行合并。

问题的关注点

The run-time system takes care of the details of partitioning the input data, scheduling the program’s execution across a set of machines, handling machine failures, and managing the required inter-machine communication.

• 如何分割输入数据。

• 分布式集群的调度。

• 机器的错误处理。

• 集群机器间的通信。

模型

MapReduce 的模型原理是：对 input key/value pairs 对进行处理，生成对应的 output key/value pairs，这两步通过 Map 函数和 Reduce 函数来完成。

• Map：由用户编写，接受一个 input key/value pair ，生成一个 intermediate key/value pairs 的集合，MapReduce Libray 将所有具有相同 intermediate key 的 value 集合一起后传递给 Reduce 函数。

• Reduce：由用户编写，接受一个 intermediate key 和一个对应这个 key 的 value 集合，Reduce 函数会合并这些 value，生成一个较小的 value 集合。一般而言每次 Reduce 只产生 0 个或 1 个 output value。通常会使用迭代器将 intermediate value 传递给 Reduce 函数，这样就可以处理一些大到无法全部放入内存的 value 集合。

Conclusions

MapReduce 的几个方面：

• 高度封装，没有分布式经验的程序员也能十分容易地使用。

• 可处理大量不同类型问题，例如可以生成用于 Google web search service 使用的数据、用于排序、用于数据挖掘、用于机器学习的数据等等。

• 在数千台机器组成的大型集群上部署了 MapReduce 实现，这样能更有效地利用这些计算资源，且能在处理其他需要大量计算的问题上用到。

• Restricting 编程模型使得并行和分布式计算变得容易，也易于构建具有容错性的计算环境。

• 网络带宽是稀有资源，MapReduce 中的许多优化都是为了减少网络传输，例如本地化读取策略，中间文件写入本地磁盘、只写入一份中间文件等。

• 多次执行相同任务可以减少性能缓慢的机器带来的影响，同时还能解决由于机器故障导致的数据丢失问题。

3. Technique/Tips

Go 何时使用指针：

• 需要修改内容。

type A struct {    i int}
func (a *A) f() {    a.i++}

• 传递大型结构体时，使用指针传递提高效率。

// bad casevar a []VeryBigStruct// good casevar a []*VeryBigStruct
// bad casevar a map[int]VeryBigStruct// good case var a map[int]*VeryBigStruct

需要注意的是，使用指针传递一个小结构体并不一定比按值传递开销小，这是 GC 和复制数据之间的权衡。

• 如果一个对象的任何一个方法使用了指针接受者，那么这个对象的所有方法都应该使用指针接受者，即使有些方法不必要。

何时不用指针：

• 不修改内容。

// bad casefunc (a *A) getI() int {    return a.i}
// good casefunc (a A) getI() int {    return a.i}

• 传递小型数据。

// bad casevar a []*int
// good casevar a []int

• 不要捕获循环变量的指针。

// bad casea := []int{1, 2, 3}b := make([]*int, 0, len(a))for _, v := range a {    b = append(b, &v)}fmt.Println(b)for _, v := range b {    fmt.Println(*v)}/*[0xc0000ae030 0xc0000ae030 0xc0000ae030]333 */
// good casea := []int{1, 2, 3}b := make([]*int, 0, len(a))for _, v := range a {        t := v // 必需      b = append(b, &t)}fmt.Println(b)for _, v := range b {        fmt.Println(*v)}/*[0xc0000160a0 0xc0000160a8 0xc0000160b0]123 */

循环里创建的所有循环变量 v 共享相同的存储位置，这意味着获取这些循环变量的地址只会得到一个指向同一位置的指针，而循环变量 v 的值在每轮循环中被更新，因此 b 中获取的所有 v 的指针都指向同一个地址，其中存储的值就是最后一轮循环时更新的值。

4. Share

思考框架

• 我现在是个什么水平？（现状）

• 我想达到一个什么水平？（目标）

• 我将怎样到达那个目标？（实现路径）

例如要去改造一个遗留系统：

现状

对于第一个问题，面对遗留系统，我们的现状是什么呢？现状看似是遗留系统，烂代码，赶紧改吧。但请稍等！这只是现象，不是根因。 先分析一下，找到问题的根因。比如，实现一个直觉上需要两天的需求，要做两周或更长时间，根因是代码耦合太严重，改动影响的地方太多；再比如，性能优化遇到瓶颈，怎么改延迟都降不下来，根因是架构设计有问题，等等。

为什么一定要先做这个分析，直接重写不就好了？因为如果不进行根因分析，你很难确定问题到底出在哪，更关键的是，你无法判断重写是不是真的能解决问题。如果是架构问题，你只进行模型的调整是解决不了问题的。同样，如果是模型不清楚，你再优化架构也是浪费时间。所以，我们必须要找到问题的根源，防止自己重新走上老路。

目标

第二个问题，对于遗留系统而言，这个问题反而是最好回答的：重写某些代码。

先尝试重构你的代码，尽可能在已有代码上做小步调整，不要走到大规模改造的路上，因为重构的成本是最低的。

实现路径

将目标分解

要重写一个模块，这时你需要思考，怎么才能保证我们重写的代码和原来的代码功能上是一致的。对于这个问题，唯一靠谱的答案是测试。对两个系统运行同样的测试，如果返回的结果是一样的，我们就认为它们的功能是一样的。构建测试防护网，保证新老模块功能一致

怎么去替换遗留系统，答案是分成小块，逐步替换。------》任务分解思想