ARTS-week02

ARTS是什么？
Algorithm：每周至少做一个LeetCode的算法题
Review：阅读并点评至少一篇英文技术文章
Tip：学习至少一个技术技巧
Share：分享一篇有观点和思考的技术文章

Algorithm

leetcode-50 Pow(x, n)

题目：实现 pow(x, n) ，即计算 x 的 n 次幂函数。

解决方法一：递归分治

时间复杂度：O(logn)，即为递归的层数。
空间复杂度：O(logn)，即为递归的层数。这是由于递归的函数调用会使用栈空间。

class Solution {
    public double myPow(double x, int n) {
        //底数为0的任何次方都为0
        if(x == 0)
            return 0;
        long N = n;
        return n >= 0 ? quickMul(x,N) : 1/quickMul(x,-N);
    }
    public double quickMul(double x, long N){
        //指数为0，返回1
        if(N == 0)
            return 1.0;
        //指数为1，返回底数
        if(N == 1)
            return x;
        //递归求一半的值
        double y = quickMul(x,N/2);
        ////根据递归结果，如果N为偶数，x^N = y^2 ; 如果N为奇数，x^N = y^2*x
        return N % 2 == 0 ? y * y : y * y * x;  

        /*
        位运算的效率比乘除法及求余运算的效率要高的多
        因为移位指令占 2 个机器周期，而乘除法指令占 4 个机器周期。
        从硬件上看，移位对硬件更容易实现，所以我们更优先用移位。
        */
        // //递归求一半的值, 用右移运算符代替了除以 2
        // double y = quickMul(x,N >> 1);
        // //用位与运算符代替了求余运算符 % 来判断是一个奇数还是一个偶数  等于1就是奇数
        // return (N & 0x1) == 1 ? y * y * x : y * y ;
    }
}

解决方法二：迭代分治 O(lgN)

时间复杂度：O(logn)，即为对 n 进行二进制拆分的时间复杂度。
空间复杂度：O(1)。

Review

How to Analyze and Tune MySQL Queries for Better Performance

这篇文章介绍了MySQL高可用性解决方案，并分析了他们的优点和缺点。

首先为什么需要高可用方案，可能是

在灾难时需要多个副本
提高读写吞吐量
遇到故障后，依然能提供可用的服务

CAP定理

一致性（所有结点访问的数据是同样的）

比如一个分布式购物系统，将这个系统部署在A和B两个服务器上，这时只剩一件物品了，用户C先下手为快，点了购买，这时服务器A和B都应该是无货状态，但是服务器B由于网络故障没有更新完成，这时又来了一个用户，点击查询，却返回了有货状态。显然这种情况就是不满足一致性定理的。
可用性（就是任意非故障的服务器都必须对客户的请求产生响应，除非服务器全崩了）
分区容错性（就是在一个分布式系统中，如果某几个结点之间出现故障，使整个网络出现分区，但也能正常返回）

要考虑的问题

数据丢失问题
避免单节点失败
是否可以承担丢失的事务
冲突检测和解决
是故障转移还是分布式系统
想要多少个9的可用性
是否需要规模读取或写入
集群至少有三个结点
我有多少个数据中心
灾难恢复
需要什么存储引擎
负载均衡的选择
集群重启带来的问题
'''''''''''''''

Tip

求斐波那契数列的几种方法

1. 递归算法(复杂度O(2^n))

public static double fib(int n) {
	return n <= 0 ? 0 : n == 1 ? 1 : fib(n - 2) + fib(n - 1);
}

2. 迭代算法(复杂度O(n))

public static double fib(int n) {
    if (n == 0)
        return 0;
    int a1 = 0, a2 = 1;
    for (int i = 1; i < n; i++) {
        a1 = a2;
        a2 = a1 + a2;
    }
    return a2;
}

3. 公式算法(复杂度O(logN))

斐波那契数列第n项的值的通项公式如下：

public static double fib(int n) {
	return (Math.pow((1+Math.sqrt(5))/2,n) - Math.pow((1-Math.sqrt(5))/2,n))/Math.sqrt(5);
}

查看源码，发现其实现调用了StrictMath类的pow函数，并且，Math中很多函数都调是直接调用了StrictMath类中的函数，而在StrictMath类中方法用native修饰，表明调用的并非java代码，而是其它的。经了解，这里是C代码来实现这些方法的，而这些源码在jdk中并没有公布。

power(a, n)的求解

第一种解法：不断的乘以自己，的时间复杂度O(N)

第二种解法：递归分治，O(lgN)

第三种解法：通过N的二进制位，迭代分治，O(lgN)

4. 矩阵算法

思路：构建矩阵乘法

代码我还没搞懂，等搞懂了在补上

5. 查表法

思路：提前算好结果，打表的时间复杂度为O(1)

static final int[] fibs = {0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946, 17711, 28657, 46368, 75025, 121393, 196418, 317811, 514229, 832040};
 public int fib(int N) { return fibs[N]; }

出自于谷歌于2004年发表的论文MapReduce: Simplifed Data Processing on Large Clusters

这篇经典论文介绍了MapReduce的工作原理，使用MapReduce可以进行数据清洗，每个Map必须完全独立，并且只能查看其参数的纯函数（其实就是函数式编程实现）

执行Map的worker会将map的结果存储在本地硬盘，然后将本地硬盘位置发给master，然后reducer通过master知道中间输出位置，通过RPC来拿数据。

图中没有输入输出文件所在的位置，因为我们想要灵活的读取任何worker服务器上的任何输入，这意味着我们需要某种网络文件系统来存储输入数据，该论文中称之为GFS或者谷歌文件系统，GFS是一个文件系统集群，它与运行MapReduce的worker是在同一个服务器集上（也就是服务器上两者都有部署），当你读取的文件在GFS上时，GFS会自动将文件分割成很多64MB大小的数据块，并将它们分散存储在不同的服务器上。