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]; }
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大小的数据块，并将它们分散存储在不 同的服务器上。
