2019第一篇arts, 果然學(xué)習(xí)都是反人性的
**Algorithm**
每周至少做一個(gè)leetcode算法題
**Review**
閱讀并點(diǎn)評(píng)至少一篇英文技術(shù)文章
（英文論文文獻(xiàn)）
**Tip**
至少學(xué)習(xí)一個(gè)技術(shù)技巧
**Share**
分享一篇有觀點(diǎn)和思考的技術(shù)文章
Algorithm
看了下數(shù)據(jù)結(jié)構(gòu)與算法之美的A*搜索算法：是一種基于Dijkstra算法優(yōu)化的次優(yōu)解算法，意在減少搜索時(shí)間，不保證是最優(yōu)解
自己按照思路簡(jiǎn)單畫(huà)了個(gè)導(dǎo)圖如下：
大概實(shí)現(xiàn)了下，還好之前有Dijkstra算法的基礎(chǔ)，不然一下午根本搞不定：
- 基本數(shù)據(jù)結(jié)構(gòu)
//邊
public class Edge {
int start;
int end;
int weight;
public Edge(int start, int end,int weight){
this.start = start;
this.end = end;
this.weight = weight;
}
}
//節(jié)點(diǎn)坐標(biāo)信息類
public class Vertx {
int nodeValue; //圖中節(jié)點(diǎn)值
int distance; //節(jié)點(diǎn)距離起點(diǎn)的最小值
int x,y; //節(jié)點(diǎn)在xy坐標(biāo)系中的坐標(biāo)
int f; //f=distance+節(jié)點(diǎn)距離終點(diǎn)的曼哈頓距離(|x1-x2|+|y1-y2|)
public Vertx(int nodeValue, int x, int y){
this.nodeValue = nodeValue;
this.x = x;
this.y = y;
}
}
//相應(yīng)的圖結(jié)構(gòu)，包括鄰接表，各個(gè)頂點(diǎn)的坐標(biāo)數(shù)組等
public class AStarGraph {
int v;
LinkedList<Edge>[] adj; //鄰接表
Vertx[] vertxes;
public AStarGraph(int v){
this.v = v;
adj = new LinkedList[v];
for(int i=0;i<v;i++){
adj[i] = new LinkedList<>();
}
vertxes = new Vertx[v];
}
//s->t，權(quán)重為weight
public void addEdge(int s, int t, int weight){
adj[s].add(new Edge(s,t,weight));
}
//添加頂點(diǎn)的坐標(biāo)
public void addVertx(int id, int x, int y){
vertxes[id] = new Vertx(id,x,y);
}
}
- 優(yōu)先級(jí)隊(duì)列: 根據(jù)Vertex.f構(gòu)建小頂堆
package com.zxb.structurealgo.AStarAlgo49;
/**
* @ClassName AStarPriorityQueue
* @Description 優(yōu)先級(jí)隊(duì)列，根據(jù)Vertex.f構(gòu)建小頂堆
* @Author xuery
* @Date 2019/3/21 20:43
* @Version 1.0
*/
public class AStarPriorityQueue {
Vertx[] nodes; //堆數(shù)組
int count; //當(dāng)前隊(duì)列實(shí)際存在多少個(gè)值
public AStarPriorityQueue(int v){
/**
* 多加1，從下標(biāo)為1的位置開(kāi)始存數(shù)據(jù)，方便計(jì)算堆的節(jié)點(diǎn)的左右子樹(shù)
* 下標(biāo)為i的左右子樹(shù)為:2*i,2*i+1,父節(jié)點(diǎn)為i/2
*/
nodes = new Vertx[v+1];
count = 0; //專欄里面應(yīng)該是寫(xiě)錯(cuò)了
}
public Vertx poll(){
if(count == 0){
return null;
}
/**
* 下標(biāo)為1的元素就是要出隊(duì)列的元素，
* 利用小頂堆性質(zhì)：將下標(biāo)為1的元素與最后一個(gè)元素交換，最后一個(gè)元素出隊(duì)列并將count減1，之后從第一個(gè)元素開(kāi)始向下堆化
* 假設(shè)堆化時(shí)有n個(gè)元素，下標(biāo)1...n,則只需要堆化到n/2即可，因?yàn)楹罄m(xù)的都是葉子節(jié)點(diǎn)，舉個(gè)例子就知道了
*/
Vertx pollVertx = nodes[1];
swap(nodes, 1, count);
count--;
//從1-count/2開(kāi)始堆化
int i=1;
while(count > 1 && i <= count/2){
//如果i比它的左右葉子節(jié)點(diǎn)2*i,2*i+1大則繼續(xù)調(diào)整
int f = nodes[i].f;
int swapIndex = -1;
if(f > nodes[2*i].f){
f = nodes[2*i].f;
swapIndex = 2*i;
}
if(2*i+1 <= count && f > nodes[2*i+1].f){
swapIndex = 2*i+1;
}
if(swapIndex != -1){
swap(nodes,i,swapIndex);
i = swapIndex;
} else {
break;
}
}
return pollVertx;
}
private void swap(Vertx[] nodes, int i, int j){
Vertx tmp = nodes[i];
nodes[i] = nodes[j];
nodes[j] = tmp;
}
public void add(Vertx vertx){
/**
* 小頂堆插入數(shù)據(jù)，count加1，先將其插入末尾
* 然后從末尾開(kāi)始往上按照小頂堆堆化
*/
count++;
nodes[count] = vertx;
int i = count; //i的父節(jié)點(diǎn)為i/2
while(i/2 >=1){
if(nodes[i].f < nodes[i/2].f){
swap(nodes,i,i/2);
i = i/2;
} else {
break;
}
}
}
public void update(Vertx vertx){
/**
* 先根據(jù)vertex.nodeValue找到其在堆數(shù)組中的位置并更新它的f
* 之后從該點(diǎn)開(kāi)始，在這里之所以更新它是因?yàn)檎业搅烁〉膄,
* 所以從該點(diǎn)開(kāi)始向上按小頂堆堆化即可，畫(huà)圖舉例就知道了
*
* 這個(gè)查找復(fù)雜度為O(n),有點(diǎn)高,這里其實(shí)可以通過(guò)構(gòu)造map來(lái)實(shí)現(xiàn)快速查找<nodeValue,在數(shù)組中的位置>
*/
int updateIndex = -1;
for(int i=1;i<=count;i++){
if(nodes[i].nodeValue == vertx.nodeValue){
updateIndex = i;
break;
}
}
if(updateIndex != -1){
nodes[updateIndex].f = vertx.f;
}
int i = updateIndex;//從updateIndex開(kāi)始向上堆化
while(i/2 >=1){
if(nodes[i].f < nodes[i/2].f){
swap(nodes,i,i/2);
i = i/2;
} else {
break;
}
}
}
public boolean isEmpty(){
return count == 0;
}
public void clear(){
count = 0;
}
}
- 算法具體實(shí)現(xiàn)類
package com.zxb.structurealgo.AStarAlgo49;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
/**
* @ClassName AStarAlgo
* @Description A*搜索算法，快速找出一條次優(yōu)路徑解，參考49講
*
* 與Dijkstra算法的區(qū)別：
* 1. 節(jié)點(diǎn)引入(x,y)屬性，出隊(duì)列順序要綜合頂點(diǎn)離起點(diǎn)的距離+頂點(diǎn)離終點(diǎn)的距離=f
* 2. 距離等于1中兩者之和，新增屬性f=g+h;
* 3. 遍歷到終點(diǎn)就結(jié)束，所以不保證最優(yōu)解
* @Author xuery
* @Date 2019/4/9 15:27
* @Version 1.0
*/
public class AStarAlgo {
public static void main(String[] args) {
AStarGraph graph = AStarGraphGenUtil.aStarGraphGen2();
AStarAlgo aStarAlgo = new AStarAlgo();
List<Integer> result = aStarAlgo.aStarAlgo(graph,2,5);
System.out.println(result);
}
public List<Integer> aStarAlgo(AStarGraph graph, int start, int end){
//優(yōu)先級(jí)隊(duì)列，用于每次取距離最短的哪個(gè)節(jié)點(diǎn),這里java自帶的優(yōu)先級(jí)隊(duì)列沒(méi)有提供update接口，只能自己實(shí)現(xiàn)一個(gè)了
int v = graph.v;
LinkedList<Edge>[] adj = graph.adj;
Vertx[] vertxes = graph.vertxes;
AStarPriorityQueue queue = new AStarPriorityQueue(v);
//preNode數(shù)組，這里節(jié)點(diǎn)取值是0-v-1, 所以直接用數(shù)組就可以了；如果不是的話就要用map了
int[] preNodeArr = new int[v];
boolean[] visited = new boolean[v];
int[] currMinDisArr = new int[v];
//start作為第一個(gè)點(diǎn),然后根據(jù)當(dāng)前節(jié)點(diǎn)廣度優(yōu)先遍歷其后繼節(jié)點(diǎn)
Vertx vertx0 = vertxes[start];
queue.add(vertx0);
preNodeArr[start] = -1;
visited[start] = true;
while(!queue.isEmpty()){
Vertx currMinFVertx = queue.poll();
//看它的后繼節(jié)點(diǎn)
LinkedList<Edge> nextEdges = adj[currMinFVertx.nodeValue];
for(int i=0;i<nextEdges.size();i++){
Edge nextEdge = nextEdges.get(i);
if(!visited[nextEdge.end]){
//該節(jié)點(diǎn)之前沒(méi)有進(jìn)入過(guò)隊(duì)列，說(shuō)明是第一次遍歷到它
Vertx vertx = vertxes[nextEdge.end];
vertx.distance = currMinFVertx.distance + nextEdge.weight;
vertx.f = vertx.distance + Math.abs(vertx.x-vertxes[end].x)+Math.abs(vertx.y-vertxes[end].y);
queue.add(vertx);
preNodeArr[nextEdge.end] = currMinFVertx.nodeValue;
visited[nextEdge.end] = true;
currMinDisArr[nextEdge.end] = vertx.distance;
} else {
//非第一次遍歷到它，需要比較下currMinFVertx.distance+nextEdge.weight與nextEdge.end對(duì)應(yīng)的distance
//這里不能每次都去隊(duì)列中查對(duì)應(yīng)的數(shù)據(jù)比較，太慢了，構(gòu)建一個(gè)輔助數(shù)組
int currDis = currMinFVertx.distance+nextEdge.weight;
if(currMinDisArr[nextEdge.end] > currDis){
//需要更新一波
Vertx vertx = vertxes[nextEdge.end];
vertx.distance = currDis;
vertx.f = vertx.distance + Math.abs(vertx.x-vertxes[end].x)+Math.abs(vertx.y-vertxes[end].y);
queue.update(vertx);
preNodeArr[nextEdge.end] = currMinFVertx.nodeValue;
currMinDisArr[nextEdge.end] = currDis;
}
}
//截止條件：遍歷到end節(jié)點(diǎn)就結(jié)束
if(nextEdge.end == end){
queue.clear();
break;
}
}
}
//根據(jù)preNodeArr回溯
List<Integer> resultList = new ArrayList<>();
int index = end;
while(index != -1){
resultList.add(index);
index = preNodeArr[index];
}
return resultList;
}
}
- 簡(jiǎn)單的圖產(chǎn)生測(cè)試用例
package com.zxb.structurealgo.AStarAlgo49;
/**
* @ClassName AStarGraphGenUtil
* @Description 拓?fù)鋱D生成類
* @Author xuery
* @Date 2019/3/21 10:56
* @Version 1.0
*/
public class AStarGraphGenUtil {
/**
*
* @return
*/
public static AStarGraph aStarGraphGen1(){
AStarGraph graph = new AStarGraph(6);
graph.addEdge(0,1,1);
graph.addEdge(0,2,3);
graph.addEdge(1,2,1);
graph.addEdge(1,3,2);
graph.addEdge(2,3,1);
graph.addEdge(3,4,2);
graph.addEdge(3,5,5);
graph.addEdge(4,5,2);
graph.addVertx(0,0,0);
graph.addVertx(1,0,0);
graph.addVertx(2,0,0);
graph.addVertx(3,0,0);
graph.addVertx(4,0,0);
graph.addVertx(5,0,0);
return graph;
}
public static AStarGraph aStarGraphGen2(){
AStarGraph graph = new AStarGraph(6);
graph.addEdge(2,0,4);
graph.addEdge(2,1,2);
graph.addEdge(1,0,1);
graph.addEdge(0,5,2);
graph.addEdge(2,3,4);
graph.addEdge(2,4,5);
graph.addEdge(3,5,6);
graph.addEdge(4,5,7);
graph.addVertx(0,0,0);
graph.addVertx(1,1,1);
graph.addVertx(2,2,2);
graph.addVertx(3,3,3);
graph.addVertx(4,4,4);
graph.addVertx(5,5,5);
return graph;
}
}
Review
Raft算法
今天大概看了下Raft算法，理解了一些基礎(chǔ)的東西，做下總結(jié)，希望自己之后可以更深入的理解
1. Raft算法出現(xiàn)的目的
因?yàn)镻AXOS算法過(guò)于晦澀，常人難以理解，且落地困難。想要找到一種這樣的一致性算法：可實(shí)現(xiàn)性強(qiáng)，減少開(kāi)發(fā)的工作量；必須安全且大部分情況下是可用的；大部分操作必須是高效的；可理解性強(qiáng)，Raft一致性算法應(yīng)運(yùn)而生。
2. Raft算法的核心
領(lǐng)導(dǎo)選舉
集群中的每個(gè)節(jié)點(diǎn)有三種狀態(tài)：Follower(跟隨者),Candidate(參與選舉者),Leader(領(lǐng)導(dǎo)者)；
所有節(jié)點(diǎn)的初始狀態(tài)為Follower, 每個(gè)節(jié)點(diǎn)都有一個(gè)隨機(jī)時(shí)間，超過(guò)隨機(jī)時(shí)間時(shí)，如果相應(yīng)的Follower沒(méi)有收到其他節(jié)點(diǎn)的選舉信息，則會(huì)變成Candidate(先會(huì)給自己投一票), 再向其余的節(jié)點(diǎn)發(fā)送參與選舉領(lǐng)導(dǎo)者請(qǐng)求并接收其余節(jié)點(diǎn)的投票，如果投票數(shù)超過(guò)一半則節(jié)點(diǎn)由Candidate變成Leader, 選舉完畢，保證每次最多只會(huì)選出一個(gè)領(lǐng)導(dǎo)者。
有兩個(gè)timeout設(shè)置來(lái)保證領(lǐng)導(dǎo)選舉的順利進(jìn)行：一個(gè)是election timeout,它就是上面所說(shuō)的每個(gè)Follower有一個(gè)隨機(jī)的election timeout， 超過(guò)這個(gè)時(shí)間則節(jié)點(diǎn)由Follower變成Candidate狀態(tài)，一般設(shè)置為150ms-300ms, 這里每個(gè)節(jié)點(diǎn)的election timeout可能都是不一樣的，可以保證盡快的選出領(lǐng)導(dǎo)（可以想想如果都是一個(gè)確定的值，每個(gè)節(jié)點(diǎn)都同時(shí)由Follower變成Candidate,那樣選出領(lǐng)導(dǎo)的速度肯定會(huì)變慢的）；一個(gè)是heartbeats timeout, 一旦確定領(lǐng)導(dǎo)者，領(lǐng)導(dǎo)者會(huì)定時(shí)向Follower發(fā)送心跳，來(lái)保證領(lǐng)導(dǎo)者正常的情況下，其他Follower不會(huì)變成Candidate
當(dāng)領(lǐng)導(dǎo)者掛了之后，重新開(kāi)始選舉流程：由于heartbeats timeout了，所以會(huì)有節(jié)點(diǎn)從Follower變成Candidate, 然后跟之前一樣選舉出領(lǐng)導(dǎo)者即可
當(dāng)多個(gè)Follower同時(shí)變成Candidate，且投票結(jié)果Candidate都沒(méi)有超過(guò)半數(shù)以上，則等待下一輪超時(shí)重新選舉，直到選舉出leader.(注：每次選舉的時(shí)候term會(huì)加1)
日志復(fù)制
選好領(lǐng)導(dǎo)者之后開(kāi)始日志復(fù)制，就是領(lǐng)導(dǎo)者將更新通知到Follower, 要保證所有節(jié)點(diǎn)的更新數(shù)據(jù)的一致性，主要流程如下：當(dāng)客戶端發(fā)起一個(gè)更新請(qǐng)求會(huì)先給到leader，leader會(huì)將更新記錄追加到它的日志末尾，然后leader會(huì)將更新發(fā)給其他的Follower, 同理Follower也會(huì)記錄日志到其對(duì)應(yīng)的日志末尾并ack一個(gè)信號(hào)給leader, 當(dāng)leader收到超過(guò)半數(shù)的ack之后，會(huì)commit更新并通知Follower也commit這個(gè)更新。（有點(diǎn)類似于2PC，先prepare再commit）
當(dāng)發(fā)生腦裂時(shí)，raft算法還可能可以保證一致性，這是由于要半數(shù)以上ack所決定的，即使不返回?cái)?shù)據(jù)，也不會(huì)返回錯(cuò)誤數(shù)據(jù)。
參考：http://thesecretlivesofdata.com/raft/
Tip
項(xiàng)目中一個(gè)接口列表慢查詢優(yōu)化實(shí)踐
背景：項(xiàng)目開(kāi)發(fā)中提供給外部系統(tǒng)一個(gè)列表查詢接口，在測(cè)試環(huán)境驗(yàn)證響應(yīng)時(shí)間1s左右（現(xiàn)在看來(lái)也挺慢的_），感覺(jué)問(wèn)題不大，上了生產(chǎn)之后調(diào)用方反饋接口響應(yīng)時(shí)間太長(zhǎng)了，有些時(shí)候甚至超過(guò)5s，顯然這是不能忍受的，已經(jīng)超過(guò)http的超時(shí)時(shí)間了，通過(guò)響應(yīng)參數(shù)發(fā)現(xiàn)，這個(gè)列表查詢每次能返回100多條數(shù)據(jù)，之前完全沒(méi)預(yù)料到，于是乎開(kāi)始優(yōu)化
代碼大概是下面這樣的：
List<RouteRes> result = new ArrayList<>();
//根據(jù)條件查詢出符合條件的task列表
List<Task> tasks = queryTaskService.getTaskByCondition(map);
//將task列表按照routeId分組
Map<String> taskMap = tasks.stream.collect(Collectors.groupingBy(event -> event.getRouteId));
taskMap.forEach((routeId, tasks) -> {
//根據(jù)routeId查詢對(duì)應(yīng)的Route信息，這里面會(huì)查緩存，帶Biz后綴的類都會(huì)加事務(wù)
long t1 = System.System.currentTimeMillis();
Route route = routeServiceBiz.getRouteByRouteId(routeId);
long t2 = System.System.currentTimeMillis();
//組裝RouteRes
RouteRes routeRes = routeServiceBiz.buildRouteRes(route);
result.add(routeRes);
});
return result;
- 首先之前在taskMap.forEach((routeId, tasks)循環(huán)里面，調(diào)了一個(gè)不應(yīng)該調(diào)的rpc接口（復(fù)用原來(lái)的接口導(dǎo)致的嗚嗚嗚），代碼里沒(méi)有列出來(lái)，每次rpc大概20-30ms, 100多次循環(huán)就是2-3s，去除掉基本就節(jié)約一半時(shí)間了
- 還是需要2s多，不正常，再來(lái)；分析來(lái)分析去只有循環(huán)里面查緩存比較耗時(shí)，按經(jīng)驗(yàn)緩存查詢一次最多5ms，100多次也就500ms，跟2s相差還是很多??；那就把在routeServiceBiz.getRouteByRouteId里面把查緩存的時(shí)間全部打印出來(lái)，結(jié)果發(fā)現(xiàn)一次緩存大概2-3ms，100多次就是200-300ms，那時(shí)間究竟花在哪里了呢？
- 百思不得奇解，最后加了上面的t1,t2，計(jì)算出所有循環(huán)t2-t1的累計(jì)值發(fā)現(xiàn)比查緩存的累積值要大很多；再想想，外層只是通過(guò)方法調(diào)用了一下而已??；不對(duì)每次方法調(diào)用都會(huì)開(kāi)啟一次事務(wù)，基本可以確定了循環(huán)100多次就有100多次事務(wù)，主要時(shí)間花在了事務(wù)上
- 解決方法：去除掉事務(wù)，查詢根本不需要事務(wù)，之后重新查詢發(fā)現(xiàn)200ms左右，優(yōu)化完畢
總結(jié)：循環(huán)中最好不要循環(huán)加事務(wù)，當(dāng)循環(huán)次數(shù)多的時(shí)候，事務(wù)占用的時(shí)間非常多；造成這樣的最終原因還是因?yàn)椴捎玫目蚣?，Biz結(jié)尾的service所有方法都會(huì)默認(rèn)加上事務(wù)，所以對(duì)于項(xiàng)目中的查詢方法不要寫(xiě)在Biz結(jié)尾的service層，應(yīng)該重新建一個(gè)不帶Biz結(jié)尾的service，將相關(guān)的查詢方法寫(xiě)到里面去
Share
其實(shí)買(mǎi)極客時(shí)間的專欄，如果你能認(rèn)真的去看完并做筆記和思考，收獲還是蠻多的，當(dāng)然專欄只是把主要的知識(shí)點(diǎn)羅列出來(lái)，如果真的想要深入理解的話，可以借助專欄的思路去看相關(guān)的書(shū)籍和英文官方文檔，一步一步拓展，那你習(xí)得的知識(shí)將會(huì)比大部分人都要深。
