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项的值的通项公式如下:

image20200530234242315.png

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. 矩阵算法

思路:构建矩阵乘法
image20200531181252222.png

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

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]; }

Share

出自于谷歌于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大小的数据块,并将它们分散存储在不 同的服务器上。

v25642ac8d1e37098be1c97836341a7210_1440w.jpg

参考

极客时间 winter--如何优雅地计算斐波那契数列?

58沈剑--拜托,面试别再问我斐波那契数列了

6种解法解决斐波那契数列

Pow(x, n)