CodeMilk

life is not just live

git fork后如何与原仓库同步

背景

当参与到开源项目开发后,我们需要先将代码fork到自己的仓库,对代码进行修改后再提交pr。

如果在这中间原仓库有提交过代码,我们这边是无法得知的,所以我们需要在提pr前先进行merge操作,先将原仓库的内容更新下来再进行提交。

大体流程如下所示:

Redis持久化

为什么要持久化数据

由于Redis是在内存中进行存储的,当机器重启后内存里面的数据就会丢失。我们不希望这些数据是临时数据,希望它能在重启之后仍然存在,或者我们能将数据导出在其他机器上直接进行导入。这时候都需要进行持久化,将数据落盘。

持久化的方式

持久化的方式在Redis 4.x版本后有了一些区别!

持久化方式主要有两种:

  • RDB
  • AOF

最小的k个数-LeetCodeM40

题目描述

输入整数数组 arr ,找出其中最小的 k 个数。例如,输入4、5、1、6、2、7、3、8这8个数字,则最小的4个数字是1、2、3、4。

示例 1:

输入:arr = [3,2,1], k = 2
输出:[1,2] 或者 [2,1]
示例 2:

输入:arr = [0,1,2,1], k = 1
输出:[0]

限制:

0 <= k <= arr.length <= 10000
0 <= arr[i] <= 10000

给定一个数组,找出最小的k个数,对这k个数的大小顺序没有要求。

解题思路

这个题目我最开始的想法是用堆来解决的,但我解答完成看题解的时候发现了一种做法:

排序后取前k个元素

在评论区中有很多人在讨论这一种解法,虽然的他复杂度比较高,实现方式很简单,有一些专业人士在鄙视这种做法,也有一些人说这个题目的难度是简单,所以用这个也没什么问题。我的看法是支持这种做法,并不因为他的难度级别,而是解决问题的思路。在解决问题的时候每一种思路都是可取的。

堆以及堆排序

什么是堆

堆是一种特殊的树,它满足以下两点:

  • 堆是一个完全二叉树

    完全二叉树要求,除最后一层,其他层的节点个数都是满的,最后一次的节点都靠左排列。

  • 堆中每一个节点的值都必须大于等于(或小于等于)其子树中每个节点的值

    当前节点的值是子树中的最大或最小值。

我们将每个节点的值都大于等于子树中每个节点值的堆,叫做“大顶堆”。对于每个节点的值都小于等于子树中每个节点值的堆,我们叫做“小顶堆”

我们来看一下例子:

在上面的四个实例中,我们根据以上两条规则,可以判断出:

第一个、第二个是大顶堆,第三个是小顶堆,第四个由于不是完全二叉树所以不是堆。

什么是fail-fast与fail-safe

fail-fast与fail-safe

在Collection集合的各个类中,有线程安全和线程不安全这2大类的版本。

对于线程不安全的类,并发情况下可能会出现fail-fast情况;而线程安全的类,可能出现fail-safe的情况。

快速失败(fail—fast)是java集合中的一种机制, 在用迭代器遍历一个集合对象时,如果遍历过程中对集合对象的内容进行了修改(增加、删除、修改),则会抛出Concurrent Modification Exception。

安全失败(fail-sage)保存了该集合对象的一个快照副本。你可以并发读取,不会抛出异常,但是不保证你遍历读取的值和当前集合对象的状态是一致的!

fail-fast

来看一下线程不安全的类ArrayList,它实现fail-fast主要靠一个字段modCount。来从头认识一下它。

首先找到引用它的地方:

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
public boolean add(E e) {
ensureCapacityInternal(size + 1); // Increments modCount!!
elementData[size++] = e;
return true;
}

private void ensureCapacityInternal(int minCapacity) {
ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}

private void ensureExplicitCapacity(int minCapacity) {
modCount++;

// overflow-conscious code
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}

public E remove(int index) {
rangeCheck(index);

modCount++;
E oldValue = elementData(index);

int numMoved = size - index - 1;
if (numMoved > 0)
System.arraycopy(elementData, index+1, elementData, index,
numMoved);
elementData[--size] = null; // clear to let GC do its work

return oldValue;
}

可以看出,在增加元素,删除元素时都会对modCount值加一。当我们查看更新,查找的代码时并没有找到对modCount的修改。

modCount字段翻译过来就是修改次数,再结合上面的代码可以了解到只有在结构发生变化,数量增减的时候才会修改。查找不会对结构发生变化也不用修改,至于更新操作,虽然它修改了值,但是在结构上总体的数量没有改变,结构上指的是:是谁不重要,有就行。

二叉树的锯齿形层次遍历-LeetCode103

题目描述

给定一个二叉树,返回其节点值的锯齿形层次遍历。(即先从左往右,再从右往左进行下一层遍历,以此类推,层与层之间交替进行)。

例如:
给定二叉树 [3,9,20,null,null,15,7],

1
2
3
4
5
  3
/ \
9 20
/ \
15 7

返回锯齿形层次遍历如下:

1
2
3
4
5
[
[3],
[20,9],
[15,7]
]

所谓的锯齿形遍历,即是在第一层从左向右遍历,在第二层从右向左遍历,依次遍历完成。

自己动手实现一个RPC框架(七)

rpc-client

消费者端,通过代理来进行调用。

与生产者端类型,首先定义配置类:

1
2
3
4
5
6
7
8
9
10
public class ClientConfig {

private Class<? extends Encoder> encoder = FastJsonEncoder.class;

private Class<? extends Decoder> decoder = FastJsonDecoder.class;

private Class<? extends TransportClient> transportClient = NettyClient.class;

private Class<? extends RpcRegister> rpcRegister = ZookeeperRegistry.class;
}

自己动手实现一个RPC框架(六)

rpc-server

消费者的部分,这里使用配置类,将各种实现的部分在配置类中进行定义。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public class ServerConfig {
/**
* 监听端口
*/
private int port = 9090;
/**
* 网络传输
*/
private Class<? extends TransportServer> transportClass = NettyServer.class;
/**
* 注册中心
*/
private Class<? extends RpcRegister> rpcRegister = ZookeeperRegistry.class;
/**
* 编码
*/
private Class<? extends Encoder> encoder = FastJsonEncoder.class;
/**
* 解码
*/
private Class<? extends Decoder> decoder = FastJsonDecoder.class;

}

这这个配置中,定义了服务启动的端口,网络传输,注册中心,编解码的各种实现,当我们需要更换实现时只需要在这里修改即可。

自己动手实现一个RPC框架(四)

rpc-register

注册中心,这里使用zookeeper来实现。

生产者在启动服务时,将自己实现的服务注册到注册中心。

消费者调用服务时,来注册中心查找,返回调用服务实例的地址信息。

并且为了适应不同的注册实现,我们将功能定义为接口,在替换实现时在配置文件中进行替换即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public interface RpcRegister {
/**
* 注册服务
* @param serviceDescriptor
* @param responseServiceDescription
*/
void register(ServiceDescriptor serviceDescriptor, ResponseServiceDescription responseServiceDescription);
/**
* 根据服务名称查询实例地址
* @param serviceDescriptor
* @return
*/
ResponseServiceDescription lookup(ServiceDescriptor serviceDescriptor);
}