发表于

「这是我参与11月更文挑战的第7天，活动详情查看：2021最后一次更文挑战」。

今天，想和大家聊聊关于java中的参数传递的原理，参数的传递有两种，值传递和引用传递。

值传递：是指在调用函数时将实际参数复制一份传递到函数中，这样在函数中如果对参数进行修改，将不会影响到实际参数。

引用传递：是指在调用函数时将实际参数的地址传递到函数中，那么在函数中对参数所进行的修改，将影响到实际参数。

基本类型传递

先来看看下面这段最基本的代码：

1
2
3
4
5
6
7
8
9
10
11
12
java复制代码@Test
public void test() {
    int n = 10;
    test01(n);
    System.out.println("最终结果n==" + n);
}

private void test01(int m) {
    System.out.println("修改之前m==" + m);
    m = 20;
    System.out.println("修改之后m==" + m);
}

输出结果：

1
2
3
java复制代码修改之前m==10
修改之后m==20
最终结果n==10

如果跟你预期的不同，那我想你还是没有理解参数的值传递与引用传递的原理。

结合生活中的场景，深入理解一下值传递和引用传递：

你有一把钥匙，当你的朋友想要去你家的时候，如果你直接把你的钥匙给他了，这就是引用传递。这种情况下，如果他对这把钥匙做了什么事情，比如他在钥匙上刻下了自己名字，那么这把钥匙还给你的时候，你自己的钥匙上也会多出他刻的名字。

你有一把钥匙，当你的朋友想要去你家的时候，你复刻了一把新钥匙给他，自己的还在自己手里，这就是值传递。这种情况下，他对这把钥匙做什么都不会影响你手里的这把钥匙。

下面我们来画图更好的理解上述代码的例子：

image-20211128174051399

当发生函数调用的时候 n 将自己传入到 test01 方法中，同时将自己的值复制了一份并赋值给了一个新变量 m 从图中可以看出这是 n 和 m 两个变量没有一毛钱关系（m只是n的复制品），所以对 m 的修改并不会影响到 n。

如果想要改变n的值，可以使用方法的返回值：

1
java复制代码n = test01(n);

引用类型传递

下面来看看引用类型的传递：

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
java复制代码public class Dog {

    private String name;

    public String getName() {
        return name;
    }

    public void setName(String name) {
        this.name = name;
    }

    public Dog(String name) {
        this.name = name;
    }

    @Override
    public String toString() {
        return "Dog{" +
                "name='" + name + '\'' +
                '}';
    }
}


@Test
public void test() {
    Dog dog1 = new Dog("小白");
    test01(dog1);
    System.out.println("最终结果dog==" + dog1);
}

private void test01(Dog dog) {
    System.out.println("修改之前 dog==" + dog);
    dog.setName("小黑");
    System.out.println("修改之后 dog==" + dog);
}

输出结果：

1
2
3
java复制代码修改之前 dog==Dog{name='小白'}
修改之后 dog==Dog{name='小黑'}
最终结果dog1==Dog{name='小黑'}

为了方便大家理解，还是画图来分析一下：

image-20211128171133053

在 test 方法中我们创建了一个 dog1 的对象，该对象存放于堆内存中，假设内存地址为 0x1120 ，于是 dog1 这个变量便应用了这块内存地址。

当我们调用 test01 这个方法的时候会在该方法栈中创建一个变量 dog ，这个 dog 变量是由原本的入参 dog1 复制而来，所以它所对应的堆内存依然是 0x1120；

所以当我们通过 dog 这个变量修改了数据后，本质上修改的是同一块堆内存中的数据。从而原本引用了这块内存地址的 dog1 也能查看到对应的变化。

如果不理解上面的话，那么记住下面的两句话就行了：

传递引用类型的数据时，传递的并不是引用本身，依然是值；只是这个值是内存地址罢了。

因为把相同的内存地址传过去了，所以对数据的操作依然会影响到外部。

那我们继续看看下面的代码，这种情况能否改变参数的值

1
2
3
4
5
6
7
8
9
10
11
12
java复制代码@Test
public void test() {
    Dog dog1 = new Dog("小白");
    test01(dog1);
    System.out.println("最终结果dog1==" + dog1);
}

private void test01(Dog dog) {
    System.out.println("修改之前 dog==" + dog);
    dog = new Dog("小黑");
    System.out.println("修改之后 dog==" + dog);
}

输出结果：

1
2
3
java复制代码修改之前 dog==Dog{name='小白'}
修改之后 dog==Dog{name='小黑'}
最终结果dog1==Dog{name='小白'}

假设 Java 是引用传递那最终的结果应该是打印 小黑 才对，从结果看这里依然是值传递。

还是画图来分析一下：

image-20211128172501300

如果是引用传递，原本的 0x1120 应该是被直接替换为新创建的 0x1121 才对；而实际情况如上图所示，dog 直接重新引用了一个对象dog = new Dog("小黑")，两个对象之间互不干扰。

小结

Java中参数传递其实还是值传递的，只不过对于引用类型参数，值的内容是对象的引用。

本文转载自: 掘金

开发者博客 – 和开发相关的 这里全都有

发表于

「这是我参与11月更文挑战的第20天，活动详情查看：2021最后一次更文挑战」

我们在使用网络编程时，可以根据自己的业务场景，设计自己的协议。比如我们与外部接口对接，会使用一定特定的加密算法，使用特定的标签，以及固定格式的报文等等，都可以算作我们确定身份的协议。

下面我们设计一个自己的协议，来实现一些功能。

一、协议要素

创建一个好的协议，通常来说，必然要有以下要素：

  • 魔数：用来在第一时间判定是否是无效数据包
    • 例如：Java Class文件都是以0x CAFEBABE开头的。Java这么做的原因就是为了快速判断一个文件是不是有可能为class文件，以及这个class文件有没有受损。
  • 版本号：可以支持协议的升级
  • 序列化算法：消息正文到底采用哪种序列化反序列化方式
  • 指令类型：针对业务类型指定
  • 请求序号：为了双工通信，提供异步能力，序号用于回调
  • 正文长度：没有长度会导致浏览器持续加载
  • 消息正文：具体消息内容

二、自定义编解码器

我们下面简单的写一个自定义编解码器，主要是为了体验过程，深刻印象。

在写这个之前，先歇一歇准备工作；我们需要准备一个父类Message:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
java复制代码import lombok.Data;

import java.io.Serializable;

@Data
public abstract class Message implements Serializable {

    public final static int LOGIN_REQUEST_MESSAGE = 0;

    private int messageType;

    private int sequenceId;

    abstract int getMessageType();

}

一个子类LoginMessage：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
scala复制代码@Data
public class LoginMessage extends Message {

    private String username;

    private String password;

    private Date loginTime;

    public LoginMessage(String username, String password, Date loginTime) {
        this.username = username;
        this.password = password;
        this.loginTime = loginTime;
    }

    @Override
    int getMessageType() {
        return LOGIN_REQUEST_MESSAGE;
    }
}

有了以上的基础，我们就能编写编解码器了，按照前面提到的几个要素，按照顺序逐一编写：

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
ini复制代码public class MessageCodec extends ByteToMessageCodec<Message> {

    @Override
    protected void encode(ChannelHandlerContext channelHandlerContext, Message msg, ByteBuf out) throws Exception {
        // 4 字节的魔数
        out.writeBytes(new byte[]{1, 2, 3, 4});
        // 1 字节的版本,
        out.writeByte(1);
        // 1 字节的序列化方式 0:jdk
        out.writeByte(0);
        // 1 字节的指令类型
        out.writeByte(msg.getMessageType());
        // 4 个字节的请求序号
        out.writeInt(msg.getSequenceId());
        // 无意义，对齐填充,使其满足2的n次方
        out.writeByte(0xff);
        // 获取内容的字节数组
        ByteArrayOutputStream bos = new ByteArrayOutputStream();
        ObjectOutputStream oos = new ObjectOutputStream(bos);
        oos.writeObject(msg);
        byte[] bytes = bos.toByteArray();
        // 长度
        out.writeInt(bytes.length);
        // 写入内容
        out.writeBytes(bytes);
    }

    @Override
    protected void decode(ChannelHandlerContext channelHandlerContext, ByteBuf in, List<Object> out) throws Exception {
        int magicNum = in.readInt();
        byte version = in.readByte();
        byte serializerType = in.readByte();
        byte messageType = in.readByte();
        int sequenceId = in.readInt();
        in.readByte();
        int length = in.readInt();
        byte[] bytes = new byte[length];
        in.readBytes(bytes, 0, length);
        ObjectInputStream ois = new ObjectInputStream(new ByteArrayInputStream(bytes));
        Message message = (Message) ois.readObject();
        System.out.println("decode:" + magicNum + "," + version + "," + serializerType + "," + messageType + "," + sequenceId + "," + length);
        System.out.println("decode:" + message);
        out.add(message);
    }
}

下面写个客户端，用于发送消息：

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
java复制代码public class Client {

    public static void main(String[] args) {

        NioEventLoopGroup worker = new NioEventLoopGroup();
        try {
            Bootstrap bootstrap = new Bootstrap();
            bootstrap.channel(NioSocketChannel.class);
            bootstrap.group(worker);
            bootstrap.handler(new ChannelInitializer<SocketChannel>() {
                @Override
                protected void initChannel(SocketChannel ch) {
                    //引入我们的编解码器
                    ch.pipeline().addLast(new MessageCodec());
                    ch.pipeline().addLast(new ChannelInboundHandlerAdapter(){
                        @Override
                        public void channelActive(ChannelHandlerContext ctx) throws Exception {
                            //组装消息，并发送
                            Message message = new LoginMessage("Tom","123456",new Date());
                            ctx.writeAndFlush(message);
                            super.channelActive(ctx);
                        }
                    });
                }
            });
            ChannelFuture channelFuture = bootstrap.connect("127.0.0.1",8080);
            //阻塞等待连接
            channelFuture.sync();
            //阻塞等待释放连接
            channelFuture.channel().closeFuture().sync();
        } catch (InterruptedException e) {
            System.out.println("server error:" + e);
        } finally {
            // 释放EventLoopGroup
            worker.shutdownGracefully();
        }
    }
}

下面是服务端，用于接收消息和解码：

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
scss复制代码public class Server {

    public static void main(String[] args) {

        NioEventLoopGroup boss = new NioEventLoopGroup(1);
        NioEventLoopGroup worker = new NioEventLoopGroup();
        try {
            ServerBootstrap serverBootstrap = new ServerBootstrap();
            serverBootstrap.channel(NioServerSocketChannel.class);
            serverBootstrap.group(boss, worker);
            serverBootstrap.childHandler(new ChannelInitializer<SocketChannel>() {
                @Override
                protected void initChannel(SocketChannel ch) {
                    //引入编解码器
                    ch.pipeline().addLast(new MessageCodec());
                    ch.pipeline().addLast(new ChannelInboundHandlerAdapter(){
                        @Override
                        public void channelRead(ChannelHandlerContext ctx, Object msg) throws Exception {
                            //打印消息内容
                            System.out.println(msg);
                            super.channelRead(ctx, msg);
                        }
                    });
                }
            });
            ChannelFuture channelFuture = serverBootstrap.bind(8080);
            //阻塞等待连接
            channelFuture.sync();
            //阻塞等待释放连接
            channelFuture.channel().closeFuture().sync();
        } catch (InterruptedException e) {
            System.out.println("server error:" + e);
        } finally {
            // 释放EventLoopGroup
            boss.shutdownGracefully();
            worker.shutdownGracefully();
        }
    }
}

结果：

1
2
3
ini复制代码decode:16909060,1,0,0,0,326
decode:LoginMessage(username=Tom, password=123456, loginTime=Tue Nov 16 15:47:06 CST 2021)
LoginMessage(username=Tom, password=123456, loginTime=Tue Nov 16 15:47:06 CST 2021)

上面前两条是我们在编解码器中打印的日志，最后一条是我们的业务代码打印。

16909060表示我们的魔数，这里是10进制表示的，转化成二进制其实是[01 02 03 04]，后面的数字都是我们根据要素指定的。

而326使我们发送消息的字节长度。

存在的问题？
其实在我们的代码当中存在问题，我们对整个请求都设置了自己的协议，会有以下两种情况：
1）粘包，这种情况下，我们可以根据自己的规则获取到正确的消息，因为消息内容的长度等等都有指定。
2）半包，此时将导致我们的消息获取不完全，解码失败。

所以我们仍然要使用前一章节当中的解码器：

1
scss复制代码 ch.pipeline().addLast(new LengthFieldBasedFrameDecoder(1024,12,4,0,0));

参数解释分别是最大长度1024，消息长度偏移量12，消息长度4，消息长度距离消息0个长度，需要从头部剥离0个长度。

本文转载自: 掘金

开发者博客 – 和开发相关的 这里全都有

发表于

这是我参与11月更文挑战的第29天，活动详情查看：2021最后一次更文挑战

推荐阅读

大家好，我是小魔龙，Unity3D软件工程师，VR、AR，虚拟仿真方向，不定时更新软件开发技巧，生活感悟，觉得有用记得一键三连哦。

一、题目

1、算法题目

“给定一个字符串，判断是否是有效数字。”

题目链接：

来源：力扣（LeetCode）

链接：65. 有效数字 - 力扣（LeetCode） (leetcode-cn.com)

2、题目描述

有效数字（按顺序）可以分成以下几个部分：

  • 1.一个 小数 或者 整数
  • 2.（可选）一个 ‘e’ 或 ‘E’ ，后面跟着一个 整数
    小数（按顺序）可以分成以下几个部分：

（可选）一个符号字符（’+’ 或 ‘-‘）
下述格式之一：

  • 1.至少一位数字，后面跟着一个点 ‘.’
  • 2.至少一位数字，后面跟着一个点 ‘.’ ，后面再跟着至少一位数字
  • 3.一个点 ‘.’ ，后面跟着至少一位数字
    整数（按顺序）可以分成以下几个部分：

（可选）一个符号字符（’+’ 或 ‘-‘）
至少一位数字
部分有效数字列举如下：

  • [“2”, “0089”, “-0.1”, “+3.14”, “4.”, “-.9”, “2e10”, “-90E3”, “3e+7”, “+6e-1”, “53.5e93”, “-123.456e789”]
    部分无效数字列举如下：
  • [“abc”, “1a”, “1e”, “e3”, “99e2.5”, “–6”, “-+3”, “95a54e53”]
    给你一个字符串 s ，如果 s 是一个 有效数字 ，请返回 true 。
1
2
3
ini复制代码示例 1：
输入： s = "0"
输出： true
1
2
3
ini复制代码示例 2：
输入： s = "e"
输出： false

二、解题

1、思路分析

这道题可以使用有限状态机的思路解决问题，有限状态机是一种计算模型，包含一系列的状态，然后根据不同的状态进行切换。

然后，就按顺序去读取字符串中的每一个字符，如果是实现约定好的庄毅规则，就从当前状态转移到下一个状态，状态转移完成后，就读取下一个字符。

当所有的字符串读取完毕，如果状态机处于正确状态就说明该字符串正确，否则，不正确。

2、代码实现

代码参考：

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
csharp复制代码public class Solution {
    public bool IsNumber(string s) {
        Dictionary<State, Dictionary<CharType, State>> transfer = new Dictionary<State, Dictionary<CharType, State>>();
        Dictionary<CharType, State> initialDictionary = new Dictionary<CharType, State> {
            {CharType.CHAR_NUMBER, State.STATE_INTEGER},
            {CharType.CHAR_POINT, State.STATE_POINT_WITHOUT_INT},
            {CharType.CHAR_SIGN, State.STATE_INT_SIGN}
        };
        transfer.Add(State.STATE_INITIAL, initialDictionary);
        Dictionary<CharType, State> intSignDictionary = new Dictionary<CharType, State> {
            {CharType.CHAR_NUMBER, State.STATE_INTEGER},
            {CharType.CHAR_POINT, State.STATE_POINT_WITHOUT_INT}
        };
        transfer.Add(State.STATE_INT_SIGN, intSignDictionary);
        Dictionary<CharType, State> integerDictionary = new Dictionary<CharType, State> {
            {CharType.CHAR_NUMBER, State.STATE_INTEGER},
            {CharType.CHAR_EXP, State.STATE_EXP},
            {CharType.CHAR_POINT, State.STATE_POINT}
        };
        transfer.Add(State.STATE_INTEGER, integerDictionary);
        Dictionary<CharType, State> pointDictionary = new Dictionary<CharType, State> {
            {CharType.CHAR_NUMBER, State.STATE_FRACTION},
            {CharType.CHAR_EXP, State.STATE_EXP}
        };
        transfer.Add(State.STATE_POINT, pointDictionary);
        Dictionary<CharType, State> pointWithoutIntDictionary = new Dictionary<CharType, State> {
            {CharType.CHAR_NUMBER, State.STATE_FRACTION}
        };
        transfer.Add(State.STATE_POINT_WITHOUT_INT, pointWithoutIntDictionary);
        Dictionary<CharType, State> fractionDictionary = new Dictionary<CharType, State> {
            {CharType.CHAR_NUMBER, State.STATE_FRACTION},
            {CharType.CHAR_EXP, State.STATE_EXP}
        };
        transfer.Add(State.STATE_FRACTION, fractionDictionary);
        Dictionary<CharType, State> expDictionary = new Dictionary<CharType, State> {
            {CharType.CHAR_NUMBER, State.STATE_EXP_NUMBER},
            {CharType.CHAR_SIGN, State.STATE_EXP_SIGN}
        };
        transfer.Add(State.STATE_EXP, expDictionary);
        Dictionary<CharType, State> expSignDictionary = new Dictionary<CharType, State> {
            {CharType.CHAR_NUMBER, State.STATE_EXP_NUMBER}
        };
        transfer.Add(State.STATE_EXP_SIGN, expSignDictionary);
        Dictionary<CharType, State> expNumberDictionary = new Dictionary<CharType, State> {
            {CharType.CHAR_NUMBER, State.STATE_EXP_NUMBER}
        };
        transfer.Add(State.STATE_EXP_NUMBER, expNumberDictionary);

        int length = s.Length;
        State state = State.STATE_INITIAL;

        for (int i = 0; i < length; i++) {
            CharType type = ToCharType(s[i]);
            if (!transfer[state].ContainsKey(type)) {
                return false;
            } else {
                state = transfer[state][type];
            }
        }
        return state == State.STATE_INTEGER || state == State.STATE_POINT || state == State.STATE_FRACTION || state == State.STATE_EXP_NUMBER || state == State.STATE_END;
    }

    CharType ToCharType(char ch) {
        if (ch >= '0' && ch <= '9') {
            return CharType.CHAR_NUMBER;
        } else if (ch == 'e' || ch == 'E') {
            return CharType.CHAR_EXP;
        } else if (ch == '.') {
            return CharType.CHAR_POINT;
        } else if (ch == '+' || ch == '-') {
            return CharType.CHAR_SIGN;
        } else {
            return CharType.CHAR_ILLEGAL;
        }
    }

    enum State {
        STATE_INITIAL,
        STATE_INT_SIGN,
        STATE_INTEGER,
        STATE_POINT,
        STATE_POINT_WITHOUT_INT,
        STATE_FRACTION,
        STATE_EXP,
        STATE_EXP_SIGN,
        STATE_EXP_NUMBER,
        STATE_END
    }

    enum CharType {
        CHAR_NUMBER,
        CHAR_EXP,
        CHAR_POINT,
        CHAR_SIGN,
        CHAR_ILLEGAL
    }
}

image.png

3、时间复杂度

时间复杂度 ： O(n)

其中n是数组的长度，只需要遍历一遍数组即可求得答案。

空间复杂度： O(1)

只需要常数级别的空间存放变量。

三、总结

当然这道题有更加简便的方法解决。

就是用正则表达式匹配：

1
2
3
4
5
6
7
8
9
10
arduino复制代码class Solution {
public:
    static const regex pattern;

    bool isNumber(string str) {
        return regex_match(str, pattern);
    }
};

const regex Solution::pattern("[+-]?(?:\d+\.?\d*|\.\d+)(?:[Ee][+-]?\d+)?");

但是要注意，c++ 用正则表达式记得作为类的静态变量或全局变量，避免重复构造的开销，否则会超时。

本文转载自: 掘金

开发者博客 – 和开发相关的 这里全都有

发表于

「这是我参与11月更文挑战的第29天，活动详情查看：2021最后一次更文挑战」

描述

Given the head of a linked list, return the list after sorting it in ascending order.Can you sort the linked list in O(n logn) time and O(1) memory (i.e. constant space)?

Example 1:

1
2
ini复制代码Input: head = [4,2,1,3]
Output: [1,2,3,4]

Example 2:

1
2
ini复制代码Input: head = [-1,5,3,4,0]
Output: [-1,0,3,4,5]

Example 3:

1
2
ini复制代码Input: head = []
Output: []

Note:

1
2
kotlin复制代码The number of nodes in the list is in the range [0, 5 * 10^4].
-10^5 <= Node.val <= 10^5

解析

根据题意，就是给出了一个链表的头节点 head ，要求我们对其进行升序排序。题目还要求我们使用 O(n logn) 的时间复杂度和 O(1) 的内存。我尝试用了最简单的暴力插入，空间复杂度还是 O(1)，但是 O(n^2) 时间复杂度，还是超时了。

解答

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
python复制代码class ListNode(object):
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next
class Solution(object):
    def sortList(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        if not head or not head.next:return head
        L = ListNode(val=-1000000)
        L.next  = cur = head
        while cur.next:
            pre = L
            if cur.next.val >= cur.val:
                cur = cur.next
                continue
            while pre.next.val < cur.next.val:
                pre = pre.next
            tmp  = cur.next
            cur.next = tmp.next
            tmp.next = pre.next
            pre.next = tmp
        return L.next

运行结果

1
css复制代码Time Limit Exceeded

解析

因为这里用到了内置函数 sorted 对值进行排序，又重新建立新的链表，所以时间上复杂度上是 O(n logn) 但是竟然通过了汗颜。但是空间复杂度是 O(n)。

解答

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
python复制代码class ListNode(object):
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next
class Solution(object):
    def sortList(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        if not head or not head.next:
            return head
        node = ListNode(val = 0)
        result = node
        nlist = []
        while head != None:
            nlist.append(head.val)
            head = head.next
        nlist = sorted(nlist)
        for n in nlist:
            node.next = ListNode(val = n)
            node = node.next
        return result.next

运行结果

1
2
erlang复制代码Runtime: 284 ms, faster than 84.91% of Python online submissions for Sort List.
Memory Usage: 63.3 MB, less than 12.52% of Python online submissions for Sort List.

解析

还可以用归并排序，只要是时间复杂度为 O(n logn) 的其他排序算法都可以。

解答

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
python复制代码class ListNode(object):
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next
class Solution(object):
    def sortList(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        if not head or not head.next:return head
        mid = self.getMid(head)
        another = mid.next
        mid.next = None
        return self.merge(self.sortList(head), self.sortList(another))
    
    def getMid(self, head):
        fast = slow = head
        while fast.next and fast.next.next:
            fast = fast.next.next
            slow = slow.next
        return slow
    
    def merge(self, A, B):
        dummy = cur = ListNode(0)
        while A and B:
            if A.val > B.val:
                cur.next = B
                B = B.next
            else:
                cur.next = A
                A = A.next
            cur = cur.next
        if A: cur.next = A
        if B: cur.next = B
        return dummy.next

运行结果

1
2
erlang复制代码Runtime: 544 ms, faster than 44.25% of Python online submissions for Sort List.
Memory Usage: 45.6 MB, less than 86.45% of Python online submissions for Sort List.

原题链接：leetcode.com/problems/so…

您的支持是我最大的动力

本文转载自: 掘金

开发者博客 – 和开发相关的 这里全都有

发表于

这是我参与11月更文挑战的第29天，活动详情查看：2021最后一次更文挑战

推荐阅读

大家好，我是小魔龙，Unity3D软件工程师，VR、AR，虚拟仿真方向，不定时更新软件开发技巧，生活感悟，觉得有用记得一键三连哦。

一、题目

1、算法题目

“给定一个网格，找出一条从左上角到右下角的数字总和最大的路径。”

题目链接：

来源：力扣（LeetCode）

链接：64. 最小路径和 - 力扣（LeetCode） (leetcode-cn.com)

2、题目描述

给定一个包含非负整数的 m x n 网格 grid ，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。

说明： 每次只能向下或者向右移动一步。

image.png

1
2
3
4
lua复制代码示例 1：
输入： grid = [[1,3,1],[1,5,1],[4,2,1]]
输出： 7
解释： 因为路径 1→3→1→1→1 的总和最小。
1
2
3
lua复制代码示例 2：
输入： grid = [[1,2,3],[4,5,6]]
输出： 12

二、解题

1、思路分析

这道题没跑了，还是用动态规划，但是由于本题是要找一条最大数字和的路径，因此路径是唯一的。

对于不在第一行第一列的元素，可以从上一个元素移动一步到达，元素对应的最小路径等于上一个元素对应的最小路径和中的最小值加上当前元素的值。

2、代码实现

代码参考：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
csharp复制代码public class Solution {
    public int MinPathSum(int[][] grid) {
        int m = grid.Length;
        int n = grid[0].Length;
        int[,] dp = new int[m + 1, n + 1];
        for (int i = 2; i <= m; i++) dp[i, 0] = int.MaxValue;
        for (int j = 2; j <= n; j++) dp[0, j] = int.MaxValue;
        for (int i = 1; i <= m; i++)
        {
            for (int j = 1; j <= n; j++)
            {
                dp[i, j] = Math.Min(dp[i - 1, j], dp[i, j - 1]) + grid[i - 1][j - 1];
            }
        }
        return dp[m, n];
    }
}

image.png

3、时间复杂度

时间复杂度 ： O(mn)

其中m是网格的长，n是网格的宽，只需要遍历一遍网格即可求得答案。

空间复杂度： O(mn)

其中m是网格的长，n是网格的宽。

三、总结

空间复杂度可以优化到原地工作，也就是O1，但是会破坏原矩阵的数据。

通过分析可以发现，数据在扫描矩阵的时候，原数据信息只在扫描的时候用到一次，后续便不会再使用。

所以扫描写dp的时候，可以直接进行覆盖，而不会影响最终的结局。

也就是利用了系统为grid分配的内存进行记录动态规划的dp。

本文转载自: 掘金

开发者博客 – 和开发相关的 这里全都有

发表于

是什么

动态规划不是一种算法， 而是一种算法思想。通过将复杂问题拆分成子问题，再通过求解子问题的解进而得到原问题的解。

给定一个问题，我们通过解其不同的部分(即子问题)，再根据子问题的解解出原有问题的解。应用算法的思想解决问题的可行性，对于子问题和原问题的关系以及子问题的之间的关系有一定要求，即最优子结构和重复子问题

最优子结构

最优子结构是子问题和原问题之间的关系。

动态规划解决的是一些问题的最优解。通过将原问题拆解成不同部分的子问，然后递归的寻找每个子问题的最优解，最后通过一定的数学方法对子问题的最优解进行组合得出最终解。

将子问题的解进行组合可以得到原问题的最终解这是动态规划可行性的关键。在题解中一般是通过状态转移方程描述这种组合。例如原问题的解为f(n)，其中f(n)也叫状态。状态转移方程f(n) = f(n-1) + f(n-2)描述了子问题和原问题之间的组合关系。同时在原问题的求解过程中， 不同选择可能对应子问题之间不同的组合关系(n=2k和n=2k+1在这里表示不同的选择，对应了子问题的不同组合)：

1
2
3
scss复制代码            f(n−1)+f(n−2)  n=2k
    f(n)={  
            f(n−1)         n=2k+1

找到了最优子结构，也就能推导出一个状态转移方程，通过状态转移方程可以很快得出问题的递归实现。

重复子问题

重复子问题是指子问题和子问题之间的关系。当我们在递归的寻找某个子问题的最优解的时候会重复遇到更小子问题。这些问题会导致重复计算，动态规划保证每个重复子问题只会被计算一次。再解决重复计算问题时，一般通过记忆化递归法：若能事先确定子问题的范围就可以建表存储子问题的答案。

解决动态规划的核心： 找出子问题和原问题的关系

动态规划算法中关于最优子结构和重复子问题的理解的关键点：

  • 证明问题的方案中包含一种选择，选择之后留下一个或多个子问题
  • 设计子问题之间的组合关系，即状态状态转移方程
  • 证明子问题是重叠的，并且通过记忆化存储

怎么做

1
2
3
4
5
6
ini复制代码举例：
描述： 给定一个无序数组，找到其中长度最大的递增子序列
示例：
    输入: [10,9,2,5,3,7,101,18]
    输出: 4
    解释: 最长的上升子序列是 [2,3,7,101]，它的长度是4。

能否将问题规模减小，一些典型的减小方式是动态规划分类的依据。例如线性，区间，树形等。这里考虑数组常用的两种方式：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
css复制代码- 每次减少一半：个子问题[10,9,2,5]和[3,7,101,18]的最优解是[2,5]和[3,7,101]。这两个子问题的最优解没法通过一定的组合得到原问题的最优解[2,3,7,101]
- 每次减少一个：记f[n]为以第n个元素结尾的最长子序列，每次减少一个，将原问题分解成f[n-1], f[n-2]...f[1]共n-1个问题。n-1 = 7个问题的答案如下：
    [10, 9, 2, 5, 3, 7, 101] -> [2, 5, 7, 101]
    [10, 9, 2, 5, 3, 7] -> [2, 5, 7]
    [10, 9, 2, 5, 3] -> [2, 3]
    [10, 9, 2, 5] -> [2, 5]
    [10, 9, 2] -> [2]
    [10, 9] -> [9]
    [10] -> [10]
    已经有了7个子问题的最优解，可以发现通过一种组合方式可以得到原问题的最优解。f[6]的结果[2, 5, 7]， 7 < 18,同时长度也是f[1]~f[7]中结尾元素小于18的结果中长度最长的。f[7]的长度为4，虽然长度是最长的，但是结尾元素101大于18，无法组合成原问题的解。以上的组合方式可以归纳成一个状态转移方程：
    f[n]= maxf[i] + 1 其中i<n且a[i]<a[n]
- 总结：解决动态规划问题最难的两个点在于：
    - 如何定义f[n]
    - 如何通过f[1], f[2]...f[n-1]推导出f[n], 即如何推导出状态转移方程
  1. 递归

有了状态转移方程，实际上可以通过递归的方式直接实现了

1
2
3
4
5
6
7
8
9
golang复制代码func find(arr []int, len int) (res int){
    res := 1
    for i :=0; i<len; i++ {
        if (arr[i] < arr[len]) {
            res = max(res, find(arr , i) + 1)
        }
    }
    return res
}
  1. 自上向下(记忆法）

递归方法的求解过程中会存在大量的重复计算，记忆法通过记录在求解f[1], f[2]…过程中的结果，将结果保存在一个表中， 在后续求解子问题的时候，如果遇到之前就已得出的子问题的结果，就拿来直接使用。

1
2
3
4
5
6
7
8
9
10
11
12
13
golang复制代码func find(arr []int, len int, dp []int)(res int) {
    if (dp[len] != -1 ){
        return dp[len]
    }
    res := 1
    for i :=0; i<len; i++ {
        if (arr[i] < arr[len]) {
            res = max(res, find(arr , i) + 1)
        }
    }
    dp[len] = res
    return res
}
  1. 自底向上(迭代）

由于有状态转移方程的存在， 我们可以通过增加问题规模的方式，一步步的靠近原问题的规模。在这过程中，需要记录每个问题的解来避免重复计算

本文转载自: 掘金

开发者博客 – 和开发相关的 这里全都有

发表于

解决了什么问题？

快速ci cd ;

团队协作效率更高，更快的集成，更快的交付；走gitops模式；

file

主流的CICD过程：

file

teamcity的架构：

file

安装方式

docker的方式安装快速

安装server端

1
2
3
4
5
6
7
8
shell复制代码mkdir -p /data/teamcity_server/datadir  /data/teamcity/logs


docker run -it --name teamcity-server \
-v /data/teamcity_server/datadir:/data/teamcity_server/datadir \
-v /data/teamcity_server/logs:/opt/teamcity/logs \
-p 8111:8111 \
jetbrains/teamcity-server:EAP

然后得到访问的url,后面安装客户端的时候需要用到。

比如这里是： http://172.31.12.168:8111

数据库选择选用默认的hsqldb,这里只要挂载的目录不丢，重新安装之后数据也是存在的；

安装client端

1
2
3
4
5
6
shell复制代码mkdir -p /data/teamcity_agent/conf
chmod -R 777 /data/teamcity_agent/conf

docker run -it -e SERVER_URL="http://172.31.12.168:8111"  \
    -v /data/teamcity_agent/conf:/data/teamcity_agent/conf  \
    jetbrains/teamcity-agent:EAP

可以安装多个;

但是专业版本的限定了3个，所以为了后期的遍历，最多不超过3个客户端吧！

安装完毕之后需要在server端对agent进行授权才能使用。

file

直接备注即可加入到客户端池。

file

file

然后即可加入到服务端的客户端池子。构建的任务的执行即可按照并行度为3进行执行。

file

也可以物理化部署，不会有docker内核的问题。
​
file

这个位置可以下载物理版本的客户端安装包。结合文档修改配置参数即可；
​

主要修改的是服务端server的地址和客户端的应用名称；
位置：/data/team_agent4/conf/buildAgent.properties

file

启动指令： ./bin/agent.sh start
​

然后在服务端授权即可使用。

使用初体验

一个后端工程的CI和CD过程：
下面是实践过程:

file

创建工程

file

然后贴入你的 gitlab或者github仓库地址；

填写一个有只读权限的账号和密码。

file

配置CICD构成脚本

1 后端打jar包

file

2 打后端docker镜像

file

3 前端npm打包

file

4 前端镜像制作

file

5 推送前端和后端镜像到镜像仓库

file

6 发布到k8s环境

file

7 发动钉钉通知到项目群

file

整体的kotlin代码

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
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
java复制代码package _Self.buildTypes

import jetbrains.buildServer.configs.kotlin.v2019_2.*
import jetbrains.buildServer.configs.kotlin.v2019_2.buildSteps.MavenBuildStep
import jetbrains.buildServer.configs.kotlin.v2019_2.buildSteps.dockerCommand
import jetbrains.buildServer.configs.kotlin.v2019_2.buildSteps.maven
import jetbrains.buildServer.configs.kotlin.v2019_2.buildSteps.nodeJS
import jetbrains.buildServer.configs.kotlin.v2019_2.buildSteps.script
import jetbrains.buildServer.configs.kotlin.v2019_2.triggers.vcs

object Build : BuildType({
    name = "appBuild"
    description = "构建"

    allowExternalStatus = true
    artifactRules = "app-tp/start/target/app-tp.jar => app-tp.jar"
    publishArtifacts = PublishMode.SUCCESSFUL

    vcs {
        root(HttpGitlabH3yunComHermesSystemAppTpGitRefsHeadsMaster)

        showDependenciesChanges = true
    }

    steps {
        maven {
            name = "打jar包"
            goals = "clean install -Dmaven.test.skip=true -U"
            pomLocation = "app-tp/pom.xml"
            runnerArgs = "-Dmaven.test.failure.ignore=true"
            workingDir = "app-tp"
            userSettingsSelection = "我的nexus配置"
            localRepoScope = MavenBuildStep.RepositoryScope.MAVEN_DEFAULT
            isIncremental = true
            jdkHome = "%env.JDK_18%"
            dockerImagePlatform = MavenBuildStep.ImagePlatform.Linux
            dockerPull = true
        }
        dockerCommand {
            name = "制作后端docker镜像"
            commandType = build {
                source = file {
                    path = "app-tp/app.Dockerfile"
                }
                namesAndTags = "registry.cn-shenzhen.aliyuncs.com/cloudpivot/app-tp:tptest"
                commandArgs = "--pull"
            }
        }
        nodeJS {
            name = "前端npm打包"
            shellScript = """
                cd front-tp
                npm install
                npm run build
            """.trimIndent()
            dockerPull = true
        }
        dockerCommand {
            name = "制作前端docker镜像"
            commandType = build {
                source = file {
                    path = "front-tp/front.Dockerfile"
                }
                namesAndTags = "registry.cn-shenzhen.aliyuncs.com/cloudpivot/front-tp:tptest"
                commandArgs = "--pull"
            }
        }
        script {
            name = "登录推送到远程镜像仓库"
            scriptContent = """
                docker login -u="aaaa" -p xxxxyun registry.cn-shenzhen.aliyuncs.com
                
                echo "推送到远程仓库"
                docker push registry.cn-shenzhen.aliyuncs.com/cloudpivot/app-tp:tptest
                docker push registry.cn-shenzhen.aliyuncs.com/cloudpivot/front-tp:tptest
                
                echo "删除本地镜像===节约磁盘空间===="
                docker images | grep app-tp | awk '{print ${'$'}3 }' | xargs docker rmi
                docker images | grep front-tp | awk '{print ${'$'}3 }' | xargs docker rmi
            """.trimIndent()
        }
        script {
            name = "更新k8s环境"
            scriptContent = """
                cd %system.teamcity.build.checkoutDir%
                cd deploy
                sh app_tp_deploy.sh
                sh front_tp_deploy.sh
            """.trimIndent()
        }
        script {
            name = "推送钉钉通知到项目群"
            scriptContent = """
                url='https://oapi.dingtalk.com/robot/send?access_token=b0dc2aee487a842dd5648566ade86xxxxxxx'
                programe=技术管理平台
                server=tptest.cloudpivot.cn
                content=%teamcity.build.branch%
                buildInfo=%vcsroot.useAlternates%
                 
                function sendDingtalk(){
                    curl ${'$'}{1} \
                       -H 'Content-Type: application/json' \
                       -d "
                      {\"msgtype\": \"text\", 
                        \"text\": {
                            \"content\": \"消息内容:项目-${'$'}{2},域名-${'$'}{3},分支-${'$'}{4} 更新内容-${'$'}{5}\"
                         },
                         \"isAtAll\": true, 
                      }"
                }
                
                sendDingtalk ${'$'}{url} ${'$'}{programe} ${'$'}{server} ${'$'}{content} ${'$'}{content} ${'$'}{buildInfo}
            """.trimIndent()
        }
    }

    triggers {
        vcs {
            branchFilter = "+:refs/heads/test"
        }
    }
})

小结

teamcity专业版本限制3个执行客户端，100个构建配置，适合小型团队；

用户体验比较好，界面比较好看。

自动检测代码变化，进行构建；（可以大大提高CI效率）

file

比如推送了一个修改到某个分支，直接就发布到了集成测试环境了。

file

pk

(开发完毕一个功能，然后合并到集成测试分支，再到CICD系统点发布，碰到问题再惊起一滩鸥鹭)

更优雅。

钉钉消息通知

拉一个钉钉群，增加一个机器人：

file

file

file

完整之后，即可拿到通知token：

oapi.dingtalk.com/robot/send?…
​

​

​

准备的shell脚本：
​ 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
shell复制代码url='https://oapi.dingtalk.com/robot/send?access_token=c30f5008258474da14e65d3141536953b79df3bf3ab64f33a583e83165b19665'
programe=技术管理平台
server=tptest.cloudpivot.cn
content='程序中断'
 
function sendDingtalk(){
    curl ${1} \
       -H 'Content-Type: application/json' \
       -d "
      {\"msgtype\": \"text\", 
        \"text\": {
            \"content\": \"消息内容:项目-${2},服务地址-${3},更新内容-${4}\"
         },
         \"isAtAll\": true, 
      }"
}

sendDingtalk ${url} ${programe} ${server} ${content}

实际例子：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
shell复制代码url='https://oapi.dingtalk.com/robot/send?access_token=b0dc2aee487a842dd5648566ade86e2217dac868c0ffdcab5138cb7eab163978'
programe=技术管理平台
server=tptest.cloudpivot.cn
content=%teamcity.build.branch%
buildInfo=%vcsroot.useAlternates%
 
function sendDingtalk(){
    curl ${1} \
       -H 'Content-Type: application/json' \
       -d "
      {\"msgtype\": \"text\", 
        \"text\": {
            \"content\": \"消息内容:项目-${2},域名-${3},分支-${4} 更新内容-${5}\"
         },
         \"isAtAll\": true, 
      }"
}

sendDingtalk ${url} ${programe} ${server} ${content} ${content} ${buildInfo}

通知效果截图：

file

材料

使用手册: （必看英文材料）

www.jetbrains.com/help/teamci…

teamcity之旅 （必看中文材料）
developer.aliyun.com/article/738…

腾讯云搭建teamcity过程：（特权容器解决docker agent无法打镜像的问题）
blog.csdn.net/sD7O95O/art…
​

钉钉机器人通知文档：
ding-doc.dingtalk.com/doc#/server…
​

程序启动之后通过shell通知到钉钉群：
blog.csdn.net/weixin_3783…

原创不易，关注诚可贵，转发价更高！转载请注明出处，让我们互通有无，共同进步，欢迎沟通交流。

本文转载自: 掘金

开发者博客 – 和开发相关的 这里全都有

发表于

这是我参与11月更文挑战的第28天，活动详情查看：2021最后一次更文挑战。

中间件

有时我们需要对许多路由之前执行相同的操作，比如判断是否拥有权限访问等，这时，我们就可以通过中间件来实现，所谓中间件，其实和 Flask 框架中的请求钩子很类似，实际上是一个函数，在 request 处理之前和 response 返回之前被调用。

中间件处理逻辑：

  • 接收客户端请求
  • 对该请求执行某些自定义操作
  • 传递给应用程序相应的路由继续处理业务逻辑
  • 接收应用程序视图函数返回的响应
  • 对响应进行自定义操作
  • 返回响应

自定义中间件

可以使用 FastAPI 提供的app.middleware("http")装饰器创建中间件。

下面创建一个中间件，用于返回应用程序的处理时间：

1
2
3
4
5
6
7
python复制代码@app.middleware("http")
async def add_process_time_header(request: Request, call_next):
    start_time = time.time()
    response = await call_next(request)
    process_time = time.time() - start_time
    response.headers["X-Process-Time"] = str(process_time)
    return response

可见，中间件函数需要接收request请求对象以及call_next函数作为参数，然后call_next函数将request作为参数，然后传递给应用程序相应的路由继续处理并接收响应response，我们可以对response进行操作，最后返回。

我们可以自定义其他功能的中间件，比如请求拦截器等，检验用户访问权限等。

使用已有的的中间件

除了自定义中间件，我们也可以直接使用 FastAPI 自带的中间件，可以通过app.add_middleware()操作来引入已定义的中间件，接收两个参数，第一个参数为中间件的类，第二个参数为要传递给中间件的参数。

下面以HTTPSRedirectMiddleware中间件和TrustedHostMiddleware中间件为例，其中HTTPSRedirectMiddleware强制发来的请求协议必须是 https 或者 wss；TrustedHostMiddleware强制发来的请求必须在 Header 信息中设置了 Host 选项，为了避免 HTTP Host Header 攻击。

1
2
3
4
python复制代码app.add_middleware(HTTPSRedirectMiddleware)
app.add_middleware(
    TrustedHostMiddleware, allowed_hosts=["tigeriaf.com", "*.tigeriaf.com"]
)

另外，还有一些其他功能的中间件，可参考文档：Starlette’s Middleware docs

使用CORSMiddleware中间件解决跨域问题

开发接口服务，跨域问题也算是很常见的一个问题了，通常我们的 API 一般是给到前端去调用，但是前端和后端往往可能属于不同的源，所以需要做跨域请求支持，FastAPI通过CORSMiddleware中间件来实现。

1
2
3
4
5
6
7
8
9
10
11
12
python复制代码origins = [
    "http://localhost",
    "http://localhost:8080",
]

app.add_middleware(
    CORSMiddleware,
    allow_origins=origins,
    allow_credentials=True,
    allow_methods=["*"],
    allow_headers=["*"],
)

CORSMiddleware中间件支持的参数部分如下：

  • allow_origins：允许跨域请求的域名列表
  • allow_methods：允许跨域请求的HTTP方法列表，默认只支持GET，["\*"]表示允许所有 HTTP 方法
  • allow_headers：跨域请求支持的HTTP头信息列表。['*']表示允许所有头信息
  • allow_credentials：表示在跨域请求时是否支持cookie，默认为False
  • expose_headers：表示对浏览器可见的返回结果头信息，默认为[]
  • max_age：浏览器缓存CORS返回结果的最大时长，默认为600秒

总之，我们可以通过 FastAPI 提供的中间件灵活快速的实现拦截器、权限校验等功能。

原创不易，如果小伙伴们觉得有帮助，麻烦点个赞再走呗~

最后，感谢女朋友在工作和生活中的包容、理解与支持 ！

本文转载自: 掘金

开发者博客 – 和开发相关的 这里全都有

发表于

Redis是用ANSI C语言编写的，它是一个高性能的key-value数据库，它可以作用在数据库、缓存和消息中间件。其中 Redis 键值对中的键都是 string 类型，而键值对中的值也是有 string 类型，在 Redis 中 string 类型运用还是很广泛的。本文主要介绍 string 的数据结构—— 简单动态字符串（Simple Dynamic String） 简称sds。

sds 实现

sds 的数据结构:

1
2
3
4
5
6
7
8
9
10
11
c复制代码struct sdshdr {

     //buf 已占用的长度
     int len;

     // buf 剩余的可用的长度
     int free;
   
     // 保存字符串数据的地方
     char buf[]; 
}

结构 sdshdr 保存了 len、free 和 buf 三个属性，分别记录字符的已使用的长度，未使用的长度，以及实际保存字符串的数组。
以下是一个新建的，保存 hello world 字符串的 sdshdr 结构：

1
2
3
4
5
ini复制代码struct sdshdr {
    len = 5;
    free = 0;
    buf = "hello\0"; 
}
  • free 属性值为0，表示这个sds没有分配未使用的空间。
  • len 属性值为5，表示这个sds保存了一个五字节长的字符串。
  • buf 属性是一个 char 类型的数组，数组的前五个字节分别保存了 ‘h’、’e’、’l’、’l’、’o’ 五个字符，而最后一个字节保存了空字符’\0’。

sds 遵守 C 字符串以空字符串结尾的惯例，保存的空字符串一个字节空间不计算在 sds 的 len 属性里面。添加空字符串到字符串末尾等操作，都是由 sds 函数自动完成的，所以这个空字符对于使用者来说完全是透明的。

通过 len 属性，可以实现时间复杂度 O(1) 的长度计算。另外通过对 buf 分配一些额外的空间，并使用 free 记录未使用空间的长度，sdshdr 可以减少内存的重新分配。这是 sds 相对 c 字符串的一个优势。

为何 Redis 不用 C 语言表示字符串

Redis 是使用 C 语言开发的，而在使用最多的字符串上，Redis 没有使用 C 语言传统的字符串表示，而且使用自己构建的简单动态字符串（sds）。
在 C 语言中，字符串可以用一个 \0 结尾的 char 数组表示。比如 hello world 在 C 语言中就可以表示为”hello world\0”。数组一般初始化以后长度就已经固定了，不能支持字符串追加append和长度计算操作：

  • 每次计算字符串长度都要遍历一遍数组，所以时间复杂度是O(N)
  • 对字符串每次进行追加操作，需要对字符串进行一次内存分配

sds 优化追加字符操作

Redis 作为数据库，对于查询速度要求严格，数据修改也比较频繁，如果每次修改字符串都需要执行一次内存分配的话，都会占用大量的时间。所以 Redis 选择了 sds 而不是 C 字符串，sds 可以减少追加字符的内存分配。通过举例来说明，执行以下操作时，sds 内部的变化：

1
2
3
4
5
6
7
8
shell复制代码redis> set msg "hello world"
OK

redis> append msg " again"
(integer)18

redis> get msg
"hello world again"

首先 set 命令创建并保存hello world 到一个 sdshdr 中，这个 sdshdr 的值如下：

1
2
3
4
5
ini复制代码struct sdshdr {
     len = 11;
     free = 0;
     buf = "hello world\0";
}

当执行 append 命令时，相对应的 sdshdr 被更新，字符串 “ again” 会被追加到原来的 “hello world” 之后：

1
2
3
4
5
ini复制代码struct sdshdr {
     len = 17;
     free = 17;
     buf = "hello world again\0                ";
}

当调用 set 命令创建 sdshdr 时，Redis 没有给 sdshdr 分配多余的空间，free 属性为0。而在执行 append 操作之后，Redis 为 buf 分配了多于所需空间一倍的大小。

在执行 append 命令之后，保存 “hello world again” 共需要17 + 1 个字节，但是程序为 sdshdr 分配了 17 + 17 + 1 = 35 个字节，而后续如果在对 sdshdr 进行追加操作，只要追加的长度不超过 free 属性值，那么就不需要对 buf 进行内存重分配。

比如执行以后命令并不会引起 buf 的内存重分配，因为新追加的字符串长度小于17：

1
2
bash复制代码redis> append msg  " again"
(integer) 23

对应的 sdshdr 结构如下：

1
2
3
4
5
ini复制代码struct sdshdr {
     len = 23;
     free = 11;
     buf = "hello world again again\0               ";
}

redis 内存分配可以查看源码 sds.s/sdsMakeRoomFor，sdsMakeRoomFor 函数描述了内存分配的策略，下面的该函数的伪代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
c复制代码// sdshdr:追加前的字符
// addlen：追加字符串
sds sdsMakeRoomFor(sdshdr, addlen) {
   
    // 多余空间大于追加空间，无序再分配内存，直接返回
    if (free >= addlen) return s;
    // 计算新字符的长度
    newlen = (len+addlen); 
   // 如果新字符的长度小于 SDS_MAX_PREALLOC，就分配两倍新字符空间
  //  如果新字符的长度大于 SDS_MAX_PREALLOC，就分配新字符空间 + SDS_MAX_PREALLOC 空间
    if (newlen < SDS_MAX_PREALLOC)
        newlen *= 2;
    else
        newlen += SDS_MAX_PREALLOC;
    // 分配内存
    newsh = zrealloc(sh, sizeof(struct sdshdr)+newlen+1);
    // 更新 free 属性
    newsh.free = newlen - len;
    return newsh;
}

而对于字符的缩短操作，Redis 保存缩短后的字符串，此时并不会进行内存重分配，而是使用 free 属性记录缩短的字符长度。

总结

Redis 的 string 类型为何使用sds而不是 C 字符串，因为sds有两点优势：

  • 计算字符长度，C 字符串复杂度O（n），而 sds 复杂度为 O（1）
  • 字符追加操作，C 字符串每次都需要对内存进行重分配，而 sds 每次会进行动态扩容，当添加字符小于空闲字符时，不会对内容进行分配，减少系统等待时间

参考

Redis 设计与实现

如果觉得文章对你有帮助的话，请点个赞吧!

本文转载自: 掘金

开发者博客 – 和开发相关的 这里全都有

发表于

这是我参与11月更文挑战的第29天，活动详情查看：2021最后一次更文挑战

推荐阅读

大家好，我是小魔龙，Unity3D软件工程师，VR、AR，虚拟仿真方向，不定时更新软件开发技巧，生活感悟，觉得有用记得一键三连哦。

一、题目

1、算法题目

“给定一个矩阵，从矩阵左上角移动到右下角，并且中间还有障碍物，有多少条路径。”

题目链接：

来源：力扣（LeetCode）

链接：63. 不同路径 II - 力扣（LeetCode） (leetcode-cn.com)

2、题目描述

一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为“Start” ）。

机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为“Finish”）。

现在考虑网格中有障碍物。那么从左上角到右下角将会有多少条不同的路径？

image.png

1
2
3
4
5
6
7
8
rust复制代码示例 1：
输入：obstacleGrid = [[0,0,0],[0,1,0],[0,0,0]]
输出：2
解释：
3x3 网格的正中间有一个障碍物。
从左上角到右下角一共有 2 条不同的路径：
1. 向右 -> 向右 -> 向下 -> 向下
2. 向下 -> 向下 -> 向右 -> 向右
1
2
3
lua复制代码示例 2：
输入： obstacleGrid = [[0,1],[0,0]]
输出： 1

二、解题

1、思路分析

这道题与上一题都是寻找所有的路径，都可以用动态规划的思路解题，这道题与上道题的区别在于这道题有障碍物的设置。

定义到达右下角的走法为f(m,n)，因为只能从右上角走过去，所以可以得出递归公式：

f(m,n) = f(m-1,n)+f(m,n-1)，最后加上递归结束条件，看起来就完事了。

但是，这样会造成大量的重复计算，我们可以将算法进行优化。

2、代码实现

代码参考：

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
csharp复制代码public class Solution {
    public int UniquePathsWithObstacles(int[][] obstacleGrid) {
        //初始化动态规划数组
        int m = obstacleGrid.GetLength(0);
        int n = obstacleGrid[0].Length;
        int[,] ans = new int[m, n];

        //对第一行进行操作赋值
        for (int i = 0; i < n; i++)
        {
            if (obstacleGrid[0][i] == 1)
            {
                for (int j = i; j < n; j++)
                {
                    ans[0, j] = 0;
                }
                break;
            }
            else ans[0, i] = 1;
        }
        //对第一列进行操作赋值
        for (int i = 0; i < m; i++)
        {
            if (obstacleGrid[i][0] == 1)
            {
                for (int j = i; j < m; j++)
                {
                    ans[j,0] = 0;
                }
                break;
            }
            else ans[i,0] = 1;
        }
        //填充整体矩阵
        for (int i = 1; i < m; i++)
        {
            for (int j = 1; j < n; j++)
            {
                ans[i, j] = obstacleGrid[i][j] == 1 ? 0 : ans[i, j - 1] + ans[i - 1, j];
            }
        }
        return ans[m - 1, n - 1];
    }
}

image.png

3、时间复杂度

时间复杂度 ： O(nm)

其中n为网格的行数，m为网格的列数，只需要遍历一遍所有网格即可求得答案。

空间复杂度： O(m)

只需要常数级别的空间存放变量。

三、总结

动态规划的解题在很多题都会应用到。

比如说221题最大正方形，1152题地图分析等，这些题目都是以二维坐标作为状态，大多数也可以使用滚动数组进行优化。

滚动数组思想，是一种常见的动态规划优化方法，当我们定义的状态在动态规划的方程中只和某几个状态相关的时候，就可以考虑这种优化方法，目的是给空间复杂度降维。

滚动数组思想可以多学习一下。

本文转载自: 掘金

开发者博客 – 和开发相关的 这里全都有

0%