ARTS-第66周

发表于

ARTS （第66周）

循序而渐进，熟读而精思

Algorithm 算法

最简单的编译器(加法、乘法)

AST和token节点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
package compiler.ast;

import lombok.AllArgsConstructor;
import lombok.Getter;
@AllArgsConstructor
@Getter
public enum NodeType {
    Plus("加法","+",1),
    Mul("乘法","*",2),
    Literal("字面量",null,3);
    String code;
    String text;
    int level;//优先级
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
package compiler.ast;

import compiler.util.CommonUtil;
import lombok.Data;

import java.util.ArrayList;
import java.util.List;
import java.util.regex.Matcher;
import java.util.regex.Pattern;

@Data()
public class SimpleASTNode {
    //SimpleASTNode parent = null;

    List<SimpleASTNode> children = new ArrayList<SimpleASTNode>();
    NodeType nodeType = null;
    String text = null;


    public int calValue(){
        if(nodeType== NodeType.Mul){
            if(children.size()<2){
                throw  new RuntimeException("乘法节点解析错误");
            }
            int res = children.get(0).calValue();
            for (int i = 1; i < children.size(); i++) {
                res*=children.get(i).calValue();
            }
            return res;
        }
        if(nodeType== NodeType.Plus){
            if(children.size()<2){
                throw  new RuntimeException("加法节点解析错误");
            }
            int res = children.get(0).calValue();
            for (int i = 1; i < children.size(); i++) {
                res+=children.get(i).calValue();
            }
            return res;
        }
        if(CommonUtil.isNumeric(text))
            return Integer.parseInt(text);
        throw  new RuntimeException("无法将token解析成数字");
    }


}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
package compiler.token;

import lombok.Data;

/**
 * 一个简单的Token。
 * 具有文本值、类型、在字符串中的位置等属性。
 */
@Data
public class Token {

    //token的类型
    private TokenType tokenType = null;

    //token的文本值
    private String text = null;


}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
package compiler.token;

import lombok.AllArgsConstructor;
import lombok.Data;
import lombok.Getter;

@Getter
@AllArgsConstructor
public enum TokenType {
    Literal("","字面量"),
    Int("int","变量声明"),
    Plus("+","加法"),
    Mul("*","乘法");

    public String code;
    public String text;

    public static TokenType getTypeByCode(String code) {
        TokenType[] enums = values();
        for (TokenType e : enums) {
            if (e.getCode().equals(code)) {
                return e;
            }
        }
        return null;
    }
}

解析和编译

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
package compiler.compile1;

import compiler.token.Token;
import compiler.token.TokenType;

import java.util.ArrayList;
import java.util.List;

import static com.sun.org.apache.xalan.internal.lib.ExsltStrings.split;

public class TokenAnalyser {

    public static List<Token> analyserTokenOneLine(String code) {
        String[] tokens = code.split("\\s+");
        List<Token> tokenOneLine = new ArrayList<>();
        for (String tokenStr : tokens) {
            Token token = new Token();
            token.setText(tokenStr);
            token.setTokenType(getTokenType(tokenStr));
            tokenOneLine.add(token);
        }
        return tokenOneLine;
    }

    public static List<List<Token>> analyserToken(String code) {
        ArrayList<List<Token>> result = new ArrayList<>();
        String[] lines = code.split(getLineSeparator());
        for (String line : lines) {
            String[] tokens = line.split("\\s+");
            List<Token> tokenOneLine = new ArrayList<>();
            for (String tokenStr : tokens) {
                Token token = new Token();
                token.setText(tokenStr);
                token.setTokenType(getTokenType(tokenStr));
                tokenOneLine.add(token);
            }
            result.add(tokenOneLine);
        }
        return result;
    }

    private static TokenType getTokenType(String s) {
        if (s.equals("*"))
            return TokenType.Mul;
        if (s.equals("+"))
            return TokenType.Plus;
        if (s.equals("int"))
            return TokenType.Int;

        return TokenType.Literal;
    }

    private static String getLineSeparator() {
        return "\\r\\n";//windows
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
package compiler.compile1;

import compiler.token.Token;

import java.util.List;

/**
 * Token流。
 * 可以read或peekToken。
 * 可以通过unread、setPosition()回溯。
 */
public class TokenReader {

    List<Token> tokens = null;

    //当前指针位置。
    int pos = 0;

    public TokenReader(List<Token> tokens) {
        this.tokens = tokens;
    }

    /**
     * 读取一个Token，并移动指针。
     * @return 如果已经读完，则返回null。
     */
    public Token read() {
        if (pos < tokens.size()) {
            return tokens.get(pos++);
        }
        return null;
    }

    /**
     * 预读一个Token。
     * @return 如果已经读完，则返回null。
     */
    public Token peek() {
        if (pos < tokens.size()) {
            return tokens.get(pos);
        }
        return null;
    }

    /**
     * 回溯一个Token。
     */
    public void unread() {
        if (pos > 0) {
            pos--;
        }
    }

    /**
     * 获取当前指针位置。
     * @return
     */
    public int getPosition() {
        return pos;
    }

    /**
     * 设置指针位置。用于回溯。
     * @param position
     */
    public boolean setPosition(int position) {
        if (position >=0 && position < tokens.size()){
            pos = position;
            return true;
        }
        return false;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
package compiler.compile1;

import compiler.ast.NodeType;
import compiler.ast.SimpleASTNode;
import compiler.token.Token;
import compiler.token.TokenType;

import java.util.List;

public class TestCompiler {
    


    public void compilerAll(String code) {
        List<List<Token>> tokensList = TokenAnalyser.analyserToken(code);
        for (List<Token> tokens : tokensList) {
            compileLine(tokens);
        }

    }
    public SimpleASTNode compilerOneLine(String code) {
        List<Token> tokens = TokenAnalyser.analyserTokenOneLine(code);
        return compileLine(tokens);


    }


    private SimpleASTNode compileLine(List<Token> tokens) {
        TokenReader reader = new TokenReader(tokens);
        SimpleASTNode node = additive(reader);
        return node;

    }
    private SimpleASTNode additive(TokenReader reader) {
        SimpleASTNode node = null;
        node = multiplicative(reader);
        if(node != null){
            Token peek = reader.peek();
            if(peek!=null && peek.getTokenType()== TokenType.Plus){
                reader.read();
                //Token token2 = reader.read();
                SimpleASTNode node2 = additive(reader);
                if(node2 != null && node2.getNodeType().getLevel() >= NodeType.Plus.getLevel()){
                    SimpleASTNode node1 = node;
                    node = new SimpleASTNode();
                    node.setText(NodeType.Plus.getText());
                    node.setNodeType(NodeType.Plus);
                    node.getChildren().add(node1);
                    node.getChildren().add(node2);
                }else{
                    throw  new RuntimeException("加法解析错误");
                }
            }
        }

        return node;
    }
    private SimpleASTNode multiplicative(TokenReader reader) {
        SimpleASTNode node = null;
        node = primary(reader);
        if(node != null){
            Token peek = reader.peek();
            if(peek!=null && peek.getTokenType()== TokenType.Mul){
                reader.read();
                //Token token2 = reader.read();
                SimpleASTNode node2 = multiplicative(reader);
                if(node2 != null && node2.getNodeType().getLevel() >= NodeType.Mul.getLevel()){
                    SimpleASTNode node1 = node;
                    node = new SimpleASTNode();
                    node.setText(NodeType.Mul.getText());
                    node.setNodeType(NodeType.Mul);
                    node.getChildren().add(node1);
                    node.getChildren().add(node2);
                }else{
                    throw  new RuntimeException("乘法解析错误");
                }

            }

        }

        return node;
    }
    private SimpleASTNode primary(TokenReader reader) {
        SimpleASTNode node = null;
        Token peek = reader.peek();
        if(peek !=null && peek.getTokenType()== TokenType.Literal){
            node= new SimpleASTNode();
            node.setNodeType(NodeType.Literal);
            node.setText(reader.read().getText());
        }
        return node;
    }
    public static void  dump(SimpleASTNode ast ){
        dumpHelp(ast,"");
    }
    private static void  dumpHelp(SimpleASTNode ast ,String indent){
        System.out.print(indent);
        System.out.println(ast.getText()+"("+ast.getNodeType()+")");
        indent +="   ";
        for (SimpleASTNode child : ast.getChildren()) {
            dumpHelp(child,indent);
        }
    }

}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
package compiler.compile1;

import compiler.ast.NodeType;
import compiler.ast.SimpleASTNode;
import compiler.util.CommonUtil;

import java.util.List;

public class TestCalculator {

    public void calWithDump1(SimpleASTNode root){
        calWithDump1(root,"");

    }
    public void calWithDump2(SimpleASTNode root){
        calWithDump2(root,"");

    }
    private int calWithDump1(SimpleASTNode node,String indent){
        NodeType nodeType = node.getNodeType();
        String nextIndent = indent+"   ";
        List<SimpleASTNode> children = node.getChildren();
        if(nodeType== NodeType.Mul){
            if(children.size()<2){
                throw  new RuntimeException("乘法节点解析错误");
            }
            int res = calWithDump1(children.get(0),nextIndent);
            for (int i = 1; i < children.size(); i++) {
                res*=calWithDump1(children.get(i),nextIndent);
            }
            System.out.println(indent+node.getText()+"("+node.getNodeType()+")result->"+res);
            return res;
        }
        if(nodeType== NodeType.Plus){
            if(children.size()<2){
                throw  new RuntimeException("加法节点解析错误");
            }
            int res =  calWithDump1(children.get(0),nextIndent);
            for (int i = 1; i < children.size(); i++) {
                res += calWithDump1(children.get(i),nextIndent);
            }
            System.out.println(indent+node.getText()+"("+node.getNodeType()+")result->"+res);
            return res;
        }
        if(CommonUtil.isNumeric(node.getText())){
            System.out.println(indent+node.getText()+"("+node.getNodeType()+")result->"+node.getText());
            return Integer.parseInt(node.getText());
        }
        throw  new RuntimeException("无法将token解析成数字");
    }

    private int calWithDump2(SimpleASTNode node,String indent){
        System.out.println(indent+node.getText()+"("+node.getNodeType()+")");
        NodeType nodeType = node.getNodeType();
        String nextIndent = indent+"   ";
        List<SimpleASTNode> children = node.getChildren();
        if(nodeType== NodeType.Mul){
            if(children.size()<2){
                throw  new RuntimeException("乘法节点解析错误");
            }
            int res = calWithDump2(children.get(0),nextIndent);
            for (int i = 1; i < children.size(); i++) {
                res*=calWithDump2(children.get(i),nextIndent);
            }
            System.out.println(indent+"result->"+res);
            return res;
        }
        if(nodeType== NodeType.Plus){
            if(children.size()<2){
                throw  new RuntimeException("加法节点解析错误");
            }
            int res =  calWithDump2(children.get(0),nextIndent);
            for (int i = 1; i < children.size(); i++) {
                res += calWithDump2(children.get(i),nextIndent);
            }
            System.out.println(indent+"result->"+res);
            return res;
        }
        if(CommonUtil.isNumeric(node.getText())){
            //System.out.println(indent+"result->"+node.getText());
            return Integer.parseInt(node.getText());
        }
        throw  new RuntimeException("无法将token解析成数字");
    }

    public void calByRecursion(SimpleASTNode root){
        System.out.println("res->:"+root.calValue());

    }

    public static void  dumpWithValue1(SimpleASTNode ast ){
        dumpHelp1(ast,"");
    }
    private static void  dumpHelp1(SimpleASTNode ast ,String indent){
        System.out.print(indent);
        System.out.println(ast.getText()+"("+ast.getNodeType()+")result->"+ast.calValue());
        indent +="   ";
        for (SimpleASTNode child : ast.getChildren()) {
            dumpHelp1(child,indent);
        }

    }
}

测试

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
package compiler.compile1;

import compiler.ast.SimpleASTNode;

public class Test {
    public static void main(String[] args) {
        TestCompiler compiler = new TestCompiler();
        TestCalculator calculator = new TestCalculator();
        String code = "2 + 3 * 5 * 6 + 7 * 8";
        System.out.println("code_>"+code);
        SimpleASTNode root = compiler.compilerOneLine(code);
        TestCompiler.dump(root);
        System.out.println("**************************");
        System.out.println("**************************");
        calculator.calByRecursion(root);
        TestCalculator.dumpWithValue1(root);
        System.out.println("**************************");
        System.out.println("**************************");
        calculator.calWithDump1(root);
        System.out.println("**************************");
        System.out.println("**************************");
        calculator.calWithDump2(root);
    }
}

Review 英文文章

https://spring.io/guides/topicals/spring-boot-docker/

springboot 整合docker

Tip 技巧

缓存常见问题和解决方案

缓存穿透

缓存穿透是指缓存和数据库中都没有的数据，而用户不断发起请求，如发起为id为“-1”的数据或id为特别大不存在的数据。一般是由于黑客故意去请求缓存中不存在的数据，导致所有的请求都落到数据库上，造成数据库短时间内承受大量请求而崩掉

1、布隆过滤器

最常见的解决方法是采用布隆过滤器，将所有可能存在的数据hash到一个足够大的bitmap中，一个一定不存在的数据会被这个bitmap拦截掉，从而避免了对底层存储系统的查询压力。

2、接口层增加校验，如用户鉴权校验，id做基础校验，id<=0之类的的直接拦截；

3、还有一个更为简单粗暴的方法，即使一个查询返回的数据为空，我们仍然把这个空结果进行缓存，但它的过期时间会很短，最长不超过五分钟。

缓存击穿

缓存击穿是指缓存中没有但数据库中有的数据（一般是缓存时间到期），这时由于并发用户特别多，同时读缓存没读到数据，又同时去数据库去取数据，引起数据库压力瞬间增大，造成过大压力

  1. 设置热点数据永远不过期。

  2. 加互斥锁

    互斥锁：若缓存中没有数据，则获取锁（当前缓存行的锁，如根据缓存的key值创建分布式锁）再从数据库去取数据，获取不到锁则等待一会再去缓存里获取。

缓存雪崩

缓存雪崩是指缓存中数据大批量到过期时间，而查询数据量巨大，引起数据库压力过大甚至down机。和缓存击穿不同的是， 缓存击穿指并发查同一条数据，缓存雪崩是不同数据都过期了，很多数据都查不到从而查数据库。

解决方案：

1、缓存数据的过期时间设置随机，防止同一时间大量数据过期现象发生。
2、如果缓存数据库是分布式部署，将热点数据均匀分布在不同搞得缓存数据库中。
3、设置热点数据永远不过期。

缓存 “无底洞” 现象

指的是为了满足业务要求添加了大量缓存节点，但是性能不但没有好转反而下降了的现象。

产生原因
  缓存系统通常采用 hash 函数将 key 映射到对应的缓存节点，随着缓存节点数目的增加，键值分布到更多的节上，导致客户端一次批量操作会涉及多次网络操作，这意味着批量操作的耗时会随着节点数目的增加而不断增大。此外，网络连接数变多，对节点的性能也有一定影响。

解决方案

1、优化批量数据操作命令；

2、减少网络通信次数；

3、降低接入成本，使用长连接 / 连接池，NIO 等。

缓存一致性

缓存一致性要求数据更新的同时缓存数据也能够实时更新。

解决方案
1、在数据更新的同时立即去更新缓存；
2、在读缓存之前先判断缓存是否是最新的，如果不是最新的先进行更新。
3、要保证缓存一致性需要付出很大的代价，缓存数据最好是那些对一致性要求不高的数据，允许缓存数据存在一些脏数据。

Share 分享

https://my.oschina.net/7001/blog/1619842 Hystrix原理与实战

https://www.jetbrains.com/idea/download/other.html IDEA各版本下载

https://blog.csdn.net/Leon_Jinhai_Sun/article/details/100920263 SpringCloud版本定义说明

https://www.jianshu.com/p/51f744091012 MVP（Minimum Viable Product） 最小可行性产品

https://www.jb51.net/article/135852.htm top命令参数和输出