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