帐前卒专栏

code, software architect, articles and novels.
代码,软件架构,博客和小说

LP强烈要求用中文写。嗯,好吧,用中文写吧。

Flow 简介

今天试用了一下jdk9, 最主要关注Flow这个新增的功能。结果发现,这个Flow其实是一个final class,构造函数还是private,没有任何正常方法将其实例化。这个是新功能?我抱着学习的心态看了一下java doc. 发现主要是几个interface. Interface…都是接口,到底有没有实现?

然后不知道怎么查到了reactive-stream, 其实Java的JVM Flow就是按照reactive-stream的API规范写的。

reactive-stream是什么?就是反向压力流(back pressure),其实你称其为反向控制流也行。官方说法是:一个异步非阻塞反向控制流处理的标准。嗯,相当拗口。

什么是反向控制?这里还是抄袭一下别人的图吧。图的出处在这里

flow1.png

图 1 正常流处理

下面是反向的流处理:

flow2.png

图 2 反向流处理

看到了吧,反向的流处理图 2是Subcriber需要多少数据,就给多少数据。不要不给。正常的流处理图 1是管你要多少,我有多少给你多少。图1的问题就导致数据在管道里积压,或者在Subscriber里面积压。所以正常的流一般处理时要么数据就丢弃掉了,要么JVM就OOM了。所以反向的流好棒好棒的!

嗯,感觉也不是,因为有可能反向的流在Publisher的地方挤压了…其实你的程序性能不行,处理不完,积压不可避免。所以这反向的鬼东西有什么用呢?除非你的Publisher是根据你处理的数据的性能来生产数据。这听起来很酷,这很像当年教务系统的排队选课,以及魔兽世界中的等等等…其实就是处理性能不行,只能反推给最初的生产者。当然还有一种使用场景是消除峰值,当大量数据瞬间涌入时会造成整个系统崩溃。但如果你的系统在限定的时间内慢慢处理这些数据,还是完全没有问题的。这样就增加了系统的稳定性。

Java9其实只是将这个标准写入了JVM中而已。我顺便看了一下Publisher以及Subscriber的实现类,很多都是incubate包的(即实验中)。只有一个类是特别的存在:SubmissionPublisher。

Flow 使用

这个Flow使用起来,真的好麻烦。最初我知道Flow这个Feature的时候,我以为只需要将数据push到流里,然后有一个default的Consumer获取到数据。这个Flow自己给我搞定了反向控制。No,No,No. Java9啥都没有做。啥都需要你自己写。如果没有SubmissionPublisher,那你需要根据那几个Interface自己去实现。这是什么鬼,我是不是可以宣布我写了一个可以实现全世界所有功能的框架呢?我的框架就是下面这样的:

1
2
3
4
public interface Everything {

void doEverything();
}

是不是非常棒?! Java9宣称的Flow就和我上面宣称的没有啥区别,只是它的接口更多而已。好了,它还是给出了一个SubmissionPublisher。 我就先原谅它吧… 可是怎么使用呢?我再次抄袭了这边的blog的代码。我也不知道为啥变得这么厚颜无耻,不知脸红的抄袭,可能是跟腾讯阿里学的吧。

Publisher和Subscriber简单示例

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
public static class MySubscriber<T> implements Flow.Subscriber<T> {
private Flow.Subscription subscription;

@Override
public void onSubscribe(Flow.Subscription subscription) {
this.subscription = subscription;
subscription.request(1); //这里要使用Long.MAX_VALUE就会被认为获取无穷的数据。
}

@Override
public void onNext(T item) {
System.out.println("Got : " + item);
subscription.request(1); //这里也可以使用Long.MAX_VALUE
}

@Override
public void onError(Throwable t) {
t.printStackTrace();
}

@Override
public void onComplete() {
System.out.println("Done");
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
public static void main(String[] args) throws InterruptedException {
SubmissionPublisher<String> publisher = new SubmissionPublisher<>();

//Register Subscriber
MySubscriber<String> subscriber = new MySubscriber<>();
publisher.subscribe(subscriber);

//Publish items
System.out.println("Publishing Items...");
String[] items = {"1", "x", "2", "x", "3", "x"};
Arrays.asList(items).stream().forEach(i -> publisher.submit(i));
publisher.close();
Thread.sleep(20000);
}

主要的函数是:

1
2
3
4
5
6
7
8
9
10
11
// 反向控制获取数据个数。
//代码里两处request(1)都不能丢,否则数据无法正常获取
subscription.request(1)
// 发布数据,相当于数据输入
publisher.submit(i)
// 关闭publisher,没有该函数则Subscriber.onComplete()不会被调用。
publisher.close()
// 因为是异步的流处理
// 所以没能提供同步的接口,可以自己在Subcriber中加入同步策略
// 我这里简化了,如果你去掉这段代码,那你可能什么都看不到
Thread.sleep(20000);

运行结果如下:

1
2
3
4
5
6
7
8
Publishing Items...
Got : 1
Got : x
Got : 2
Got : x
Got : 3
Got : x
Done

Flow的Processor接口

Flow还有一个重要的Processor接口,这个其实就是函数变换。其实一般的函数变换操作都可以在Subscriber中实现,Processor并没有什么卵用。不过如果让我去定义接口,我仍然会给出Processor. 为啥?这样会防止别人来喷我…嗯,其实给出了Processor接口,一样有人来喷,例如我…

看下图就知道我在说什么了。竟然无图可盗了…

withProcessor.png

图 3 带有Processor的流

withoutProcessor.png

图 4 没有Processor的流

如果增加另外一个流,就可以完全实现Processor的功能。所以表达流的最小原语不应该存在Processor这东西。但是Reactive-Stream说:我的这个就是规范。那好吧,就加一个吧。不过增加Processor的好处在于:你可以只写一个流,里面有很多Processor。而不是写很多流,将Subscriber和Publisher混在一起写。虽然你已经在Processor中将Publisher,Subscriber混在一起写了…嗯…呃…总而言之,你一定要相信规范,Processor存在一定有它的道理。

下面也给一个Process的例子:是过滤用的Processor.(这段代码是我自己写的,在Oracle官方文档中本应存在这段代码,但是他们不小心忘记写了…忘记写了…我看到的官方文档最后由 Bob Rhubart-Oracle 于 2016-9-26 下午2:03修改,版本号为6):

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

public static class MyFilterProcessor<T,K extends T> extends SubmissionPublisher<K> implements Flow
.Processor<T, K> {

private Function<? super T, Boolean> function;
private Flow.Subscription subscription;

public MyFilterProcessor(Function<? super T, Boolean> function) {
super();
this.function = function;
}

@Override
public void onSubscribe(Flow.Subscription subscription) {
this.subscription = subscription;
subscription.request(1);
}

@Override
public void onNext(T item) {
if (!(boolean) function.apply(item)) {

submit((K)item);
}
subscription.request(1);
}

@Override
public void onError(Throwable t) {
t.printStackTrace();
}

@Override
public void onComplete() {
close();
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public static void main(String[] args) throws InterruptedException {
//Create Publisher
SubmissionPublisher<String> publisher = new SubmissionPublisher<>();

//Create Processor and Subscriber
MyFilterProcessor<String, String> filterProcessor = new MyFilterProcessor<>(s -> s.equals("x"));

MySubscriber<Integer> subscriber = new MySubscriber<>();

//Chain Processor and Subscriber
publisher.subscribe(filterProcessor);
filterProcessor.subscribe(subscriber);

System.out.println("Publishing Items...");

String[] items = {"1", "x", "2", "x", "3", "x"};
Arrays.asList(items).stream().forEach(i -> publisher.submit(i));
publisher.close();
Thread.sleep(2000);
}

运行结果如下:

1
2
3
4
5
Publishing Items...
Got : 1
Got : 2
Got : 3
Done

重要的代码片段是:

1
2
3
if (!(boolean) function.apply(item)) {
submit((K)item);
}

这里的submit就是数据再发布,相信大家都能看懂,不再叙述。

Flow 性能测试

到底这个东西性能怎么样?我是不是随便写一个Flow的实现都比它快?如果它性能差,我按它这个规范写有什么意义?为了好看吗?
好吧。我自己用无锁队列实现了一下。功能就是简单的计数,看看各自的最强性能。

1
2
3
4
5
6
7
8
9
10
11
12
无锁队列执行结果:
class chillyc.info.speed.old.XFlow:27qps
class chillyc.info.speed.old.XFlow:171629qps
class chillyc.info.speed.old.XFlow:7586111qps
class chillyc.info.speed.old.XFlow:8095748qps
class chillyc.info.speed.old.XFlow:7640866qps
class chillyc.info.speed.old.XFlow:6845523qps
class chillyc.info.speed.old.XFlow:6516655qps
class chillyc.info.speed.old.XFlow:6191659qps
class chillyc.info.speed.old.XFlow:5742711qps
class chillyc.info.speed.old.XFlow:6657964qps
class chillyc.info.speed.old.XFlow:5720992qps

JVM jdk9 Flow执行结果

1
2
3
4
5
6
7
8
9
Concurrent.Flow 测试结果: 设置无穷索取, request(Long.MAX_VALUE)
class chillyc.info.speed.jdk9flow.Jdk9Flow:39688qps
class chillyc.info.speed.jdk9flow.Jdk9Flow:6798618qps
class chillyc.info.speed.jdk9flow.Jdk9Flow:6556238qps
class chillyc.info.speed.jdk9flow.Jdk9Flow:6506791qps
class chillyc.info.speed.jdk9flow.Jdk9Flow:6545895qps
class chillyc.info.speed.jdk9flow.Jdk9Flow:7129085qps
class chillyc.info.speed.jdk9flow.Jdk9Flow:7005827qps
class chillyc.info.speed.jdk9flow.Jdk9Flow:6818252qps

性能对比图:

性能对比

图 5 性能对比图

个人感觉前两次都可以忽略不计,无锁队列的实现中,前两次线程还没有完全启动,数据还没有完全填充。不过从另外一个侧面反映出jdk9 Flow启动效率非常高。我们除去前两次计算一下平均值。看到两者相差不大:无锁队列比jdk9 Flow平均快了17000+qps.

实验和数据量,buffer大小都有关系,变量太多,没有一一实验,并且两者的qps都是六七百万量级,所以我认为两者差别不大。JDK9的Flow实现的挺不错的,竟然能和我顺手写的性能差不多。我心中不由的赞叹一番。

Flow bug

因为测试了jdk9 Flow的无限索取时的性能。我想再测测每次取一个导致的最差性能(request(1))。结果就发现了bug.
测试输出如下:

1
2
3
4
5
6
class chillyc.info.speed.jdk9flow.Jdk9Flow:55296qps
class chillyc.info.speed.jdk9flow.Jdk9Flow:0qps
class chillyc.info.speed.jdk9flow.Jdk9Flow:0qps
class chillyc.info.speed.jdk9flow.Jdk9Flow:0qps
class chillyc.info.speed.jdk9flow.Jdk9Flow:0qps
class chillyc.info.speed.jdk9flow.Jdk9Flow:0qps

从结果上分析,经过一段时间之后,jdk9的Flow就无法处理数据了。这…真的能用吗?

结束语

本来应该带着虔诚敬畏的心态学习JDK9的…结果变成了吐槽大会了…罪过罪过,实在不该这样…顺便一提,jshell非常好用,tab功能提示很强大,就是我机器性能有点差,感觉很卡顿…

对了,不要以为我只会讨论jdk9…那是因为ReactJS 16发布的比较晚。

I will write an article to design Class Diagram. In before article, I draw some usecases and component diagrams.

4. Transform component diagram into class diagram

4.1 Mark noun as entity

I like OOM(Object Oriented Model). Because our world is built by things. And we describe those things as noun, like sky, bird, hand, clothes. In OOD(Object Oriented Design), things are object/class entities. So there is the equation:

1
things == noun == entities     (4.1.1)

Here, I will describe our system again. Clients will send message to our “Messager Service”. User will chat with someone. User can chat with many people in one chat room. Chatting is real-time. But if all clients of user are offline, system will send offline messages to one of user’s mobile client.

Why mobile client? Because web/pc client are hardly woke up. Emmm…Should we add a constraint? “User only use one client to login/chat.” Without this constraint, system should boradcast chat messages?

But here our key point is marking noun. I already marking them as “BOLD”. But client is not in “Server” rectangle in component diagram. I will draw client class diagram later.

class-init.png

Figure 4.1.1 init classes

4.2 Add relationship between entities

In Figure 4.1.1 Chatting class is the most important class. But Chatting means a chat message. So I change it to be “ChatMsg”. In ChatMsg class, there should be who send the message, who will receive it, and what’s the status of the message. Many users will receive the same ChatMsg Object. And one ChatMsg only contain one Message. If one ChatMsg is not exist, can the Message in it be exist? I think there should be strong relationship between Message and ChatMsg. And I call the relationship as “co-exist”. I draw solid diamond line between ChatMsg and Message. Other relationship with ChatMsg is not co-exist, but without User, the ChatMsg is meaningless. So I draw hollow diamond line between User and ChatMsg. Status is addition feature of ChatMsg. Without Status, we can not show chat status to our users. I draw arrow line between them. Now we draw Figure 4.2.1

class-init.png

Figure 4.2.1 init classes 2

Emmm…Does ChatRoom relate with ChatMsg? Yes. We consider users chat with each other in one chat room. When one chat message generated, the system will send it to the users who are in the ChatRoom. So I put Collection into ChatRoom. So here it is:

class-init.png

Figure 4.2.2 init classes 3

4.3 Think twice

Here, another problem should be considered. If we join/leave ChatRoom, the users of ChatRoom will be changed. Can we see ChatMsg even if we leave the ChatRoom? If the status of ChatMsg is sent, and then someone join the chatroom, should the ChatMsg be delivered to him? Can new comer see old ChatMsgs?
There are many requirements:

  1. new comer can see old chat messages. But someone quit the room, he can not see any chat messages be occurred in the room.
  2. new comer can not see old chat messages. And someone quit the room, he will see nothing chat messages.
  3. new comer can not see old chat messages. But even someone quit the room, he can see chat messages before he left in any time.

And there will be corresponding solutions too!

  1. Do nothing, the class digram supports the requirements 1.
  2. If ChatRoom is changed, we log it. So ChatRoom should contain version. The solution also supports requirement 1 and 3. But the performance of the system will be lower than 1 or 3.
  3. We store Collection<User> in each ChatMsg Object, and Collection<User> is only the snapshot of ChatRoom. It seems there is no relationship between ChatMsg and ChatRoom. And it will cost more spaces (memory/disk) than 1 or 2.

I will choose solution 2. The solution can adapt many requirements, and it stores the relationship between ChatRoom and ChatMsg. And I fill more field of Class Message and User. I call “ChatRoom history” as “ChatRoomSnapshot”. When ChatRoom is changing, the system will generate ChatRoomSnapshot to store old ChatRoom. The id of ChatRoomSnapshot and related ChatRoom must be the same. So the relationship between ChatRoom and ChatRoomSnapshot is weak. I just draw a line between them. In Message, I prefer JSONObject as its content.

class-init.png

Figure 4.3.1 init classes 4

All of above are our system “Server” entities. Is it enough? Those entities seem like static or immutable. And in component diagram, there are many components. Which component is related with the class diagram? The answer is none. Figure 4.3.1 only draw basic entities. Those entities will be used in each components. And now, I will draw details of each component, and “give life” to those entities.

Origin

I joined leetcode system design group to discuss how to design software. This is week3 topic:

Messenger service like What’s App with the following functionalities

  1. One to One text messaging
  2. Group Chat, Storage
  3. Read/Delivery/Sent status

Gist:

  1. We are having a conversation between two parties. A -> B. Think of this process. What happens and how do you explain to interviewer
  2. Asynchronous - meaning, “You are on a flight and you receive messages once you land. So those messages were waiting some where!” (Hope you got it). How would you design it
  3. Horizontal scaling, Load Balancer
  4. For Read/Delivery/Sent status -> 3 way handshake protocol can give you an idea.

This is a good topic. I will try to design it.

Scenario

First of all, what’s the scenarios? The scenarios will correct my design. The scenario is in which way people use our software. So let’s think scenario first. The scenario should be atomic, and can not split into two or more scenarios. The scenario is a completed interaction. For example, The scenario like:

  1. User A send message to the system.
  2. The system send message to User B.

Step 1 or Step 2 is not a scenario. Step 1 with Step 2 is a completed scenario.
And our chat system will be like:

init-system

Figure 2.1 init system

Er…It’s too simple…So let’s write more scenarios:

Scenario 1: send and get message in realtime

  1. User A send message to the system.
  2. The system send message to user B.

Scenario 2: send message and get it after a while, because user is offline.

  1. User A send message to the system.
  2. At this time, user B is offline.
  3. User B is online.
  4. The system send message to User B.

Scenario 3: read old messages

  1. User can read old messages of chat in receive-time order.

Scenario 4: group chat in realtime

  1. User A, B, and C join a chat group
  2. A send message to the system
  3. B and C receive the message from system.

Scenario 5: group chat when someone is offline

  1. User A, B, and C join a chat group
  2. User A send message to the system.
  3. C will receive the message in realtime.
  4. At this time, user B is offline.
  5. When User B is online, the system send message to User B in create-time order.

Scenario 6: chat status changing

  1. User A chat with B
  2. When A is typing words, B will get “A is typing…” message from system.
  3. When A press “send” button, A will get “the message is sending” from system.
  4. When B’s app receive the message in background, A will get “the message is delivered”.
  5. When B open the chat with A, and scroll to the message, A will get “the message has been read.”

Here, scenario 5 and 4 is similar to 2 and 1. So can we consider scenario 2 and 1 are group chat with only one person? Can I chat with myself? And there should be more scenarios be considered. For example:

  1. User sign in
  2. User sign up
  3. User quit
  4. Invite other user to use the app
  5. Find a user
  6. Add relationship with other user, family, friends, enemy, lover, couple, and so on. Others should comfire the relationship.
  7. Break the relationship.
  8. Rebuild the relationship with the same user. Er…Are you crazy? …Trust me, most of lovers will repeat break-rebuild relationship scenarios. If you don’t believe it, you must be younger than me.
  9. Build a chat group, or invite other user one by one to join chat/group chat.
  10. Exit a chat group, but can not exit one-one chat, unless breaking the relationship.
  11. Type message with emoji, gif, png, voice, and other rich text.
  12. Search old messages
  13. Delete old messages.
  14. Set/Show online/offline or other user status to one or more users.
  15. Can we chat face to face?
  16. Change user own info

In this article, we can not talk all above. It’s too complicated. I will only focus on group chat and chat status changing scenarios.

scenarios

Figure 2.2 scenarios relationship

Like Figure 2.2 describles, one-one chat is a special case of group chat. So here use inherit arrow. The interaction of scenario 6 will be included from group chat scenarios. But scenario 3 is alone. If scenario 3 is discarded, our message service will be like “Snapchat”. And I use “User” actor instead of “User A” or “User B”. Why I always write a rectangle as “Messager service”? Because the rectangle warns us, our service has its own boundary! We will not consider other scenarios. If those scenarios inside of rectangle do not be implemented, our service is useless. And if you want to add more functionalities, the rectangle will be bigger and bigger. So thinking about your limit time and money, can you add more functionalities? The correct thing is creating worked well service, notwriting piles and piles of functionalities. Mmmmm…sound like: I use your “Messager service”, will you add “beautify photo”? NO!!!

How to design?

Seems like we always talk about how user use our messager service. Er…Correct! So here I will write something about how to design it. I don’t know how to build the system. I only knows there should be a client and a server…So like that:

init-components

Figure 3.1 init components

Now, we have first components diagram. Let’s do more thinking. If we store data, we will have database. If we connect with others, there should have a channel mananger. My chat groups should be controlled by group manager. If some user is offline, can we send offline message to them by APNS? Adding schedule component for sending message to offline user is a good idea. There should have a component for transforming “chat message” to service data, and doing reverse. And another component called “chat service” controls all component to work togather.

more-components

Figure 3.2 decompose components

In Figure 3.2, I decompose “Client” into “Interface”, “Transform” and “Channel”, and decompose “Server” into other small components. How to use line to connect those components? The answer is if the connection between components exists, connecting them. It’s nosense!! And another way to deal with the connections is following data flows. In Message services, there exists at least two data flows.

  1. User -> Client Interface -> Transform message to bytes/data -> send to Channel -> Server Channel Mgr receive bytes/data -> Transfrom into server data -> according to data, pull group data from Group Mgr and store message into Database.
  2. According to group info, sending message to other group members -> Transfrom server data into bytes -> send to Channel Mgr -> delivery message to Client Channel -> Transform bytes to message -> display message to User.
  3. Schedule reading what cannot be deliveried -> send message through Chat Service -> Transfrom server data into bytes …

Er…Can we connect Group Mgr with DAO? YES. One point is you can change all diagrams in any time. And another point is, if you don’t draw line between Group Mgr and DAO, you can implement the system as well. For example,

  1. we can store group info into files
  2. we use Chat Service as proxy to store group info. Chat Service will call DAO to store group info, if chat exist. If the group members are all silence, the group will be destroyed after a while.

Is there a formal way to draw those components and lines? NO. This is why the software is attractive. Every software is artwork. Do you remember your first program? Always print: “Hello World!” It’s boring! Can we make the world different?

End? No. I will write how to decompose conponent into classes later.

引子

遇到一个陌生人,只看到他沾满泥土的鞋子。
夏日地铁里,闻到了周围人的汗臭。
朋友聚会,似乎有些人眼屎没擦干净。
初次相亲见面,就一直在说对方不好看。
你看到别人的种种不足,当面指出来,为什么没有人感谢你?
不光没有人感谢,似乎还有人恶言相向,某些人还因此要打你。
你做错了吗?
                                 ————《帐前卒的寓言》

I don't want to know

Code Review作为编码社会活动,一直被人诟病。每个人似乎都知道Code Review好,但是推广起来却有种种困难。而“用IDE编程”这事似乎根本就不用推广。这到底是为什么?因为Code Review中不可避免要指出别人的代码不足。我们也经常会遇到:

  • 评价/建议后,编码者却不修改;
  • 总是同一种错误,一犯再犯;
  • 抵制你的评价意见,寻求他人再次Review。

我们review别人的代码,不是专门为代码点赞,那是“鼓励师”要做的事情。我们主要是指出别人的代码哪里写的不好。我想,即使是最和善、最理智的程序员也肯定不喜欢那些评论。即便如此,我们还是要评论,要让别人接受我们的观点。不过为了让别人乐于接受,肯定要有恰当的鼓励。另外,在评论别人的代码之前,我们最好知道是谁写的代码。如果是匿名的,当然可以肆无忌惮的评论。但Code Review是一种非匿名的社交活动:我们都知道编码者是谁,编码者也知道评价者是谁。与说话的技巧一样:“对什么人,说什么话”。所以我们首先需要了解编码者。

读代码识人心

比鬼神更可怕的,是人心。
                    ————《盗墓笔记》

读懂人心,实在是太难了。通过代码去读懂人心,那就更难了。如果和编码者经常在一起,性格喜好自然能略知一二。如果你从来没有接触过编码者,只看代码能了解什么呢?我们无法从代码中看出那人的血型、星座、爱好;也难看出勇敢、乐观、顽强、抑郁或悲伤;更看不出他是表现型、分析性还是实干型。当然以上那些性格特点对我们评价代码也没有什么卵用。从代码中读懂人心,只需关注三个方面:

  • 是否认真编码
  • 是否对技术有激情
  • 编码水平怎么样

为什么只关注这三个方面?认真的编码者对细节格外关心,指明他代码细节的缺陷,他的技术水平一定会有提升。有激情的编码者一定会迫不及待的使用新的技术、新的语法、新的组件。应该告诉他们这些新的技术、语法、组件在代码里用的是否恰当。高水平的编码者乐于提高自己的编程技巧,也喜欢破坏现有的规则,他们看重的只有逻辑错误和运行时问题。Review时,投其所好,才能让编码者信任你,然后才可能接受你的建议。如果编码者编码不认真、技术没激情、水平也不咋样,请问该怎么办?这我们后面会说。

认真的编码者

编码者是否想到你所想到的细节,是否还考虑了你没有想到的点?是否遵循了code style规范中每一条细节?是否考虑了边界情况?在特殊处理的地方,有没有写详细的注释?当他看到你的评论时,不管同意与否,他是否每一条都认真回复了。

有激情的编码者

编码者是否尝试了新的技术:新的组件、新的语法糖?是否愿意解决一些别人不碰的难题?不那么美观的代码是否充满了不断尝试的味道?是否规避了存在问题的第三方组件?是否尝试写过一些公用组件?是否对旧的问题有新的思路?

高水平的编码者

编码水平有优劣,但这个优劣大多数只存在于人的内心。有时候你看了一眼别人的代码,你心里想:“这段代码能写的更简单,更容易。” 所以优劣大多是和自己比较的:技术比自己好,还是比自己差。如果你熟悉整个团队,那么你就能知道这个人的编码水平大概处于整个团队的什么位置。

但是编码者提交的代码量太少,或者大多是log/print/bean,无法了解他这三个方面的特质,那就用comments多交流几次。

书写评论

write comments

初识,最好多点赞,并建议如何编码。如果对方是新入职的人员,最好一次性的指出程序要修改的地方。一是他有时间修改;二是新人需要了解公司里的编码规范;三是提升他的编码水平。

在review的过程中不要否定新技术,也不要轻易肯定新技术,适用才是评判依据。为什么使用这些新技术?是旧的写起来麻烦,还是旧的无法满足需求,还是只为尝鲜?对于调研团队,我们鼓励使用各种新的技术。不管是挖坑还是填坑,需要通过他们的使用情况,了解多种新技术的功能特性、成熟度、性能优劣和适用条件。对于功能交付团队,不管是上线还是开发软件给客户使用,能满足需求的同时,一定要为了稳定不折腾。否则后期就会被bug所累,疲于奔命。

表达相同意思的一段文字可以有不同的写法。工作要有乐趣,不要评论千篇一律、枯燥乏味。下面我要说几种评论的风格:

  • 吐槽。针对熟识的同事或者针对技术水平很高的人。幽默风趣,又让人容易接受。

  • 委婉建议。针对有激情的人,不应该抹杀别人的技术追求。多以疑问句为主,让其自己反思。

  • 批评。针对多次犯同一错误的新人。他们犯的错误一般都是非常容易改正。例如,多写常量定义、使用linux换行符、打印不用System.out等等。有时用感叹句让批评的语气再严厉一点,否则下次新人还会犯同样的错误。

  • 直白陈述。可能大多数评论采用的是这种句式。另外针对编码“得过且过”的老码农,你可能需要多写点:除了点明问题所在,还应该建议他怎样去修改代码。这样可以减少他的返工次数,消减他的抵触情绪。

  • 讥讽。除非是你的好基友,否则不要用,不要用,不要用,说三遍,不要树敌。

当面交流

communicate

既然当面交流,不妨听听编码者怎么看待你的评论。不要一言不合就暴跳如雷,要问问他想怎么修改,或者为什么不想修改。

出发点还是**“利”**字。但是受益者可能不同的:是编码者得利,还是团队得利,还是公司得利。这就要看你的三寸不烂之舌,如何既讨人欢心又让人听你指示。程序员这群理智的动物,有时最看不惯的就是阿谀奉承。大家都是靠技术混饭吃的,虽然糖衣炮弹固然重要,但更重要的是言明利弊。

有些人即使你心平气和的交流,仍然不愿意修改他们的代码,这时候就要关注问题的边界。如果在容忍的边界里,或者对建议置之不理,或者允许开发者以后再修改。如果是边界之外,就应该据理力争。那边界究竟是怎样划定的呢?我写在下面:

  • 代码中存在bug。bug会导致各种错误,有些会导致数据错乱、文件错乱等难以修复的问题。
  • 代码难以理解,日后难维护。当然如果写这代码的人永不离职,自己维护尚可。可人要是离职了,还要看后继者是否愿意担风险去重构这些代码。
  • 长时间运行有问题。那多久会出问题呢?看多久再次部署,如果每天都部署一次,两天就算长时间了。但是为了让团队每个人都休息好、有自己的假期、以及不在休假时被打扰,还是尽量考虑长远一点。如果你最长假期有10天,那至少要考虑软件运行大半个月没问题。
  • 数据量大、访问量大时,代码运行缓慢或者宕机。如果估算运行部署几天后数据/访问量就会到达这个规模,那一定要尽早修改代码。
  • 改动后将大量节省他人的时间。如果将代码抽取为模块或者组件后,有更大的收益。特别是他人即将开始这部分工作时,一定要尽快的抽取出相关代码。不抽取的话,一是别人也要写相关代码;二是一旦有修改,相同功能的代码都会修改;三是即使后期再抽取了组件,也没人愿意重构。

我们都是执着的技术人,我们心中自有不可逾越的底线,我们也希望所有的编码者不要越过这条底线。我们把这底线告诉给编码者,这也是Code Review中评审者的义务。但建议也写了,见面也谈过了,编码者和审阅者两方就是各不相让。那没有其他办法,只能通过公司里的人事关系去解决:

  • 如果是你的下属,都已经讲明白道理,还是不执行,那是这个下属不称职。
  • 如果是你的上级,你已经告知了他风险,他觉得你的建议没有道理,那就请他说出自己的道理。当然你觉得是他是一个傻X领导,拍拍屁股走人就是;但如果你越职言事,那就是大忌了。
  • 如果是你的平级,告知他上级代码的风险,之后就交给他的上级处理吧。

当然你需要知道,为了权衡:有时为了紧急上线,有时为了更大的利,即使逾越了你的底线,也要先把代码merge了再说。。

Code Review是为了什么?最终是为了获利。在公司,什么都不考虑,只为把代码写的完美无缺,那才是真的傻。

本文分三个部分:先讲Review代码的流程,再讲Review的技巧,以及如何推动公司层面Code Review.

  1. Review流程这一部分比较简短。流程多变,但都是为了发现代码的问题,反复建议提交者修改。
  2. Review技巧我这部分分两个章节介绍。一章主要讲如何阅读代码,reivew的重点在于阅读。与读文章一样,也分粗读和细读。另外一章讲review代码的重点考察点,比较散乱也比较长。如何评论别人的代码并不是本文的内容。下面的言论也不是评论别人代码时用到的,所以请大家注意一下。以后会写一篇文章详细阐述如何评论别人的代码。
  3. 推动公司进行Code Review, 这一章节纯属于个人的愚见,大家有更好的想法也欢迎讨论。

第一章 Review流程

reviewflow

写完代码后,发送diff给指定人review。待给出意见后,修改代码,继续提交diff,直到review通过。通过review的代码由审阅者自动或者手工Merge代码到指定分支。多人协作review时,第一位阅读者给出粗略意见,第二位看意见是否给的恰当,再补充其他意见。多人同时review,也可将代码用投影仪打到大屏,共同review一段代码。

这里需要思考几个问题:

  1. review的分工。有多人参与时需要考虑这个问题。最好有一个总负责人。
  2. review的策略。项目初期应该主要考察代码结构是否符合规范,即代码是否放到了相应的位置。项目中期应该以逻辑正确、简化代码、重构现有代码为主要考察点。项目后期主要看程序性能相关的优化问题。
  3. review通过的策略。 什么样的代码才能通过review。 是不是需要完全符合checklist? 我个人并不赞同完全遵照checklist。后面我会细说。
  4. 如何反馈已修改?review代码的工具一般是gitlab, reviewboard, gerrit。这些工具都提供了comments这一功能。review的时候可以写下comments。 如果对照comments进行修改,那么在comments后回复已经修改即可。
  5. 如何反馈拒绝?这个最好找审阅者当面说清楚:为什么不按照建议编写代码。如果认为自己文笔非凡的也可以在review工具中写明白。
  6. review修改后再次review的策略。要对照之前的comments看看编码者是如何修改的。当然也要看看有什么新加入的代码。
  7. 代码没有必要写完后再review。可以写一部分review一部分。

第二章 阅读代码的技巧

代码

如何阅读别人提交的代码?首先要了解这代码的上下文和需求,不能不负责的指点江山。要充分了解需求,才能考虑如何实现,然后才能审阅别人的代码。不能因为读不懂别人的代码就拒绝别人的代码。这事开源界常发生,但公司内部最好杜绝发生。大家都是同事,低头不见抬头见,没必要关系僵化。你是能炒别人鱿鱼还是你自己要离职呢?看不懂代码可能有三种:一种使用了混淆、一种提交者写的烂、一种审查者能力不足。

混淆代码一般都是有特殊原因的,但不会是故意刁难审阅者。比如说机密的模块、需要隐藏秘钥或算法。这部分代码讲明白意思即可,一般也不需要review。

如果提交者写的太烂,一般都是i,j,k的命名导致。审阅者更应该读懂后,指出哪些地方需要改进:比如少写了注释,改个好名字等。写的烂并不会导致你读不懂,一般是你不愿意花时间去读。如果你说事不关己,没必要看烂的代码。这种心态也不适合进行Code Review,只适合小作坊编程。不如谦虚谨慎、虚怀若谷。

最后一个原因:请先提高自身的编程能力!有许多算法精妙难懂,在自己编程水平不足的时候决不能以读不懂为由拒掉。

当你有足够的编程能力时,review代码时请遵照下面的流程:

1
2
3
4
5
粗读(知道大概写了哪些内容) 
=> 抽取重点(架构/类的定义/代码结构)
=> 细读代码(简化/重构)
=> 逻辑判断 (各分支)
=> 细节优化(资源释放,线程安全、算法效率)
  1. 通过粗读,我们需知提交者改动了什么。是大量修改?还是大量新增?有没有针对性的测试?没有改动配置文件? 有没有改动数据库?
  2. 我们再仔细看看设计是否恰好符合了需求。是顺序的代码,用到了多线程?还是使用了设计模式?抑或用了第三方组件/架构?是集中式,还是分布式?数据是怎么存储的?单元测试有没有测重点?还有没有更好的设计?
  3. 再细读一遍代码。挑出繁琐的代码与相似的代码。看是否有简化或重构的可能。嵌套是否太深。是否有难懂的代码。
  4. 仔细寻找逻辑判读的语句if,while,for等。主要看每一个分支是否符合需求,是否是笔误。
  5. 最后把你的注意力集中在资源释放、线程安全、算法效率上。看看有没有优化的空间。

第三章 代码考察点

如果你使用IDE,例如IDEA. 在IDEA中点击Analyze => Inspect Code … 就可以做静态检查。主要检查拼写、静态变量、包和类名等. 提交者应该用这些工具在提交代码前自查,修改一些简单的语法优化和单词拼写错误,然后再交给别人审核。

编写代码如同写文章一样;审阅代码和审阅文章也有相通之处。这里大部分技巧来自审阅文章的方法。我这里不讲Java语法的东西,也不讲性能优化的事情。那些代码太特殊,太依赖于特定的语言和上下文。我这里将以Java代码为例,但你也可以将这些技巧用于审阅其他的语言。我审阅代码时一般考察以下几点:

3.1 优雅即正义

什么是优雅的代码?我觉得整齐划一的代码不一定是优雅的代码。python的代码都是优雅的?其实不管什么语言,总会写出烂代码。简练的代码不一定是优雅的代码。优雅的代码不仅格式让人舒服,而且简练易读。读过之后,清楚代码到底做了什么事,了解它在运行时大概是什么样子的,知道在哪里改动代码来满足新的需求。

如果你是一个熟知数据结构、算法、设计模式、成熟的架构、编程语法、常用中间件、操作系统的程序员,通读了代码,却无法回答以上问题,那就不是优雅的代码。一定是哪里写的比较混乱,或者隐藏了一些时序因果。不是优雅的代码,就一定有需要改动的地方。

3.2 姓谁名何

名字很重要。你所知道的各大公司。Google是什么?是一个名字。阿里巴巴是什么?也是一个名字。你能数出来的各大品牌,都是一个个名字,所以名字很重要。名字能让你区分事物。你不应该把所有的变量都命名为a,b,c,i,j,k.各位的家长也没有给大家取名叫你,我,他。所以当你review类名/变量名/函数名的时候,请想想能否起一个更好记更易懂的名字。

3.3 份内之事

一个类/函数能做完的事情,不要在类/函数外完成。下面是一个执行远程cmd并返回结果的代码片段。

1
2
3
ResultEntity result = CommandUtil.exeCommandUtil(user, location, cmd, host, opt); 
result.setSubmitTime(time);

为什么result的提交时间不能在exeCommandUtil里面补全?这函数如果出现了十几、二十几处。那每一处都要多写一行代码。能清楚的分辨类和函数的职责并不是一件容易的事情,需要大量的经验积累。其实我们大多数人连本职工作是什么都不知道,就更难写出知道自己要干什么的类/函数了。现实中我们经常遇到本应该那人份内之事,你却要催促他完成。本应该他将工作进度告知你,你却要不断询问他完成的怎么样了。本应该他代码处理的事情,非要你帮他二次处理一下。

3.4 看了代码,开始怀疑人生

很多时候看代码看不懂,或者很迷茫。说白了,是审阅者和编码者脑回路不匹配导致。主要是因为编码者实现了太多的子类,或者类的层次太深,或者子类之间没有什么共同点。有时候,编码者用消息中间件实现了组件之间的分离,代码中隐藏了生产者与消费者之间联系。我们人类是按照时序思考的,任何破坏时序因果的代码都会让我们感觉迷茫。但这样的代码并不代表质量不高。只是希望改动后能更容易读懂。对于子类中没有什么共同点的可能需要拆开重构;对于消息分离的需要多加些注释,在注释中告诉读者下一阶段的处理流程是什么。如果是生产者,需要在注释中告诉读者,生产的某一消息,将被哪些消费者使用。如果是消费者,可以在注释中说明一下可能获取怎样的消息。

3.5 逸马毙犬于道

有些人写代码总免不了说废话。精炼自己/别人的代码。代码越精简,开发/阅读速度就越快。例如:

1
2
3
4
5
// This function is for adding user
public void addUser() {

}

我觉得上面的开发者绞尽脑汁才写出了那一行注释。再如:

1
2
3
4
5
if (a > b) {
return a;
} else {
return b;
}

3.6 言不达意

需求是增加加入组织、退出组织的接口。实现者为了开发方便,将功能放入到了一个handler里面,然后用一个enum Type来标示操作类型。而Type使用了位与操作来判断可能的类型。

1
2
3
4
5
6
7
8
9
10
if (JOIN.isContainType(type)) {
try {
join(group);
} catch (Exception e) {
LOG.warn("join group with wrong.params:" + JSON.toJSONString(params), e);
}
}
if (EXIT.isContainType(type)) {
// do exit.
}

type可能是多个操作的集合吗?那JOIN这个单一操作怎么可能包含多操作type?名字也有问题。是不是改成下面的代码更好?

1
2
3
4
5
6
7
8
9
10
if (op.isContainOp(JOIN)) {
try {
join(group);
} catch (Exception e) {
LOG.warn("join group with wrong.params:" + JSON.toJSONString(params), e);
}
}
if (op.isContainOp(EXIT)) {
// do exit group.
}

再想想,其实op只可能是单一操作。看上下文请求这一个接口不可能既加入组织又退出组织。这实在太混乱了。万一不小心将EXIT判断写到JOIN前面,岂不是先退出组织再加入组织?所以合理的代码只能是下面这种

1
2
3
4
5
6
7
8
switch(op) {
case JOIN:
// do join group
break;
case EXIT:
// do exit group
break;
}

3.7 0/1日志,图灵在世

打印log的代码和下面两句非常类似:一条是正确的日志,一条是错误的日志。

1
2
log.info("user is login");
log.warn("user op error.");

输出日志可能是这样的:

1
2
3
4
5
6
7
user is login
user is login
user is login
user op error.
user op error.
user is login
user is login

What the FFFFFFFF… 我看日志我怎么知道是谁login了?又是谁做了什么导致错误了?那与只打印0, 1又有什么区别?例如:

1
2
3
4
5
6
7
1
1
1
0
0
1
1

以后都改成这个就好了。还省代码和时间。甚至连脑子都省了。

3.8 那不是一个人在战斗

思维要保持一惯性,比如函数签名。如果某个变量一直出现在另外一个变量之前,那么请保持变量的相对位置不变。另外变量名也要尽可能的一致。审阅这些代码的时候,我总有一种错觉:那不是一个人写的代码,一定有人在帮他写代码。

1
2
3
4
public void copy(String srcPath, String dstPath);
public void mv(String srcPath, String dstPath);
public void del(String path);
public void innerCopy(boolean force, String dest, String src);

src都应该在dst前面。取名最好都是srcPath和dstPath,innerCopy最好这样写:

1
public void innerCopy(String srcPath,String dstPath, boolean force);

3.9 不做标题党

1
2
3
4
5
6
public String getScript(String appId, JSONArray jobSysParams, JSONArray appParams, String userId) {
...
...
ExecShellUtils.execShell(script);
return Path.join(...);
}

起初我看到这个函数名时,我觉得这应该是一个获取用户在某个应用下的脚本。当看到ExecShellUtils.execShell,我觉得这函数应该是直接执行了这个脚本。然后又看到return Path.join(),这怎么又返回了这个脚本的路径?这样的话,函数名应该叫execScriptAndReturnScriptPath()。

3.10 请站在巨人的肩上

多使用jdk,自有库和被验证的第三方库的类和函数

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
public class ClusterManager {
private Map<String, Cluster> clusterMap = new HashMap<>();

public void setCluster(String clusterId, Cluster cluster) {
synchronized (ClusterManage.class) {
clusterMap.put(clusterId, cluster);
}
}

public Cluster getCluster(String clusterId) {
synchronized (ClusterManage.class) {
return clusterMap.get(clusterId);
}
}

public Map<String, Cluster> getAllCluster() {
return clusterMap;
}

public void clean(){
synchronized (ClusterManage.class) {
clusterMap.clear();
}
}
}

完全等价于下面的代码,ConcurrentHashMap的性能还要比上面的快许多。

1
2
3
4
public class ClusterManager  {
private Map<String, Cluster> clusterMap = new ConcurrentHashMap<>();
...
}

再如将流变为String的代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public static String inputStream2String(InputStream is) throws Exception {
ByteArrayOutputStream bos = new ByteArrayOutputStream();
try {

int i = -1;
while (( i = is.read() ) != -1) {
bos.write(i);
}
} catch (Exception e) {
throw new Exception(EXCEPTION_TYPE.READ_FILE_ERROR);
} finally {
if (is != null) {
try {
is.close();
} catch (IOException e) {

}
}
}
return bos.toString();
}
}

可以使用apache提供的commons.io替换。另外上面的代码还破坏了谁申请谁释放的原则。

1
2
3
4
5
6
7
public static String inputStream2String(InputStream is) throws Exception {
try{
IOUtils.toString(is);
} catch(Exception e) {
throw new Exception(EXCEPTION_TYPE.READ_FILE_ERROR);
}
}

甚至你可以连这个函数都不写了。直接调用IOUtils.toString()。

3.11 多歧路,今安在

下面的代码if中的判断条件太多。

1
2
3
4
5
6
7
8
9
10
11
12
if (((optLocal.immediate != 0) &&
((optLocal.immediate == 1) ||
(difftime(now(), srun_begin_time) >=
optLocal.immediate))) ||
((rc != ESLURM_NODES_BUSY) && (rc != ESLURM_PORTS_BUSY) &&
(rc != ESLURM_PROLOG_RUNNING) &&
(rc != SLURM_PROTOCOL_SOCKET_IMPL_TIMEOUT) &&
(rc != ESLURM_INTERCONNECT_BUSY) &&
(rc != ESLURM_DISABLED))) {

// do something
}

改为:

1
2
3
4
long intervalTime = difftime(now(), srun_begin_time)
if (isExpired(intervalTime, optLocal.immediate) || isSlurmdConnectedOK(rc)) {

}

3.12 云深不知处

嵌套太深不行呀。这里是一个通信协议解析的例子。下面是循环解析的函数

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
private void loop() {
while(true) {
try {
if (isConnected()) {
Cmd cmd=null;
while((cmd = read())!=null) {
switch(cmd.getCmd()) {
case "PING": {
writePong();
}
break;
default:
break;
}
}
} else {
connect();
}
} catch(Exception) {
cleanConnection();
reConnect();
}

}
}

这里代码函数幸好不长。如果长且分支多,那读代码就很容易迷失自我。应考虑拆分成多个函数。

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
private void loop() {
while(true) {
parse();
}
}

private void parse() {
try {
if (!isConnected()) {
throw Exception(...);
}
Cmd cmd=null;
while((cmd = read())!=null) {
processCmd(cmd);
}

} catch(Exception) {
cleanConnection();
reConnect();
}
}

private void processCmd(Cmd cmd) {
switch(cmd.getCmd()) {
case "PING": {
processPing();
}
break;
default:
break;
}
}

private void processPing() {
writePong();
}

3.13 己之长,彼之短

以Java为例,这是一种面向对象的语言。面向对象并不是main必须放在某个类中这么狭义,需要有一切皆对象的观念才行。对象才是主题,代码总是围绕"对象做了什么事"来发展。如果你用C写面向对象的代码:就要写结构体,在结构体里再用函数指针。那代码看起来不舒服,写起来也不舒服。在Javascript中函数才是一等公民,要用函数式的想法去写代码。

3.14 数据放在哪里?

是使用关系型数据库存储还是key-value存储?是集中存放还是分布式的?上线/发布后数据量规模?这些是否都在代码里体现了?是否有遵循范式、是否有索引加速、列是否设计的恰当、主外键设置、有没有离线查询分析的优化设计、针对业务量增大后的数据划分处理,旧的数据如何兼容等。

3.15 知难,行亦难

代码写的复杂,那有没有写mock testcase? 是否输入的数据集都有考虑?单元测试有没有覆盖大部分分支?循环分支测试时0循环和1循环是否都测试到了?if分支是不是每一个谓词都测试到了?

第四章 推动公司层面进行Code Review

首先的首先,你要推动某件事情,你一定要先成为一个坚定的人,一个让人信服的人。那大家才会觉得你推动去做的事可行。这不是一朝一夕的事情。如果公司的大部分研发没有时间进行Code Review,这将是一件极为困难的事情。因为困难所以值得认真去做。

我们不能考虑以下场景:

你振臂一呼:咱们Code Review吧。
研发人员纷纷表示赞同。
然后没两天就搭建了一个Code Review平台。
然后大家就顺顺利利开始Code review了。
老板高层纷纷表示祝贺。

这不叫你推动了Code Review. 这只能叫你赶上了好时候。因为没有你的振臂一呼,其他虾兵蟹将也能振臂一呼,只是早晚而已。所以这种事情太顺利,顺利到高层基层都统一意见:觉得这件事可行。还是那句话:你只是赶上了好时候。我们不讨论那么顺利的局面。我想说的是如何从最不利的局面开始推动。

4.1 战略篇

推动公司层面Code Review的战略思想是:

1
利益为先、攻心为上、权谋次之、政令最下

利益为先:没有永远的朋友,只有永远的利益

最为重要的一条:利益为先。公司里做事情,大家的目标就是完成KPI,而完成KPI在老板那里就是实现净利。每个公司都应该是盈利的公司,不管是现在盈利还是将来盈利。从来没有公司以不盈利为荣,因为根本就不值得炫耀。你要做的事情,首先要符合“赚钱”这一条基本原则。虽然Code Review的本质是提高效率、提高开发质量、减少成本,最终赚钱。但是Code Review投资回报周期特别长,大家特别是老板和投资人看不到这么深远,也没有那么多耐心。所以Code Review只能是辅助盈利的手段。先摒弃掉技术公司一定要Code Review的想法。如果同事们加班加点都不能在deadline之前完成项目交付/上线赚钱, 那说明他们的时间已经100%用在直接赚钱上了。那你能做的事就是等待,千万别提Code Review。

攻心为上:让每个人都想Code Review

每个人都忍住不去Code Review。当你振臂一呼的时候,事情就成了。如果每一个人都知道Code Review的好处,每一个人都感受到Code Review的甜头,无往不利。

权谋次之:求好心人帮帮你吧

希望有好心的Lead/CTO可以帮你,那就先和他们打好关系吧。在他们困难时出手相助,并解决问题。事后再宣传一下Code Review的妙处。用不了太久大家就会想尝试一下Code Review. 大家虽然带着尝试的心,但实践效果不错。这样大家就能坚定不移的进行Code Review.

政令最下:如果你是CTO/Team Lead

宣布从今天起,所有提交的代码都必须经过Code Reivew. 首先大部分人会质疑,但是你身处高位,可能不会有人对你说不不不不。但是反抗的心似乎已经埋下。如果结果稍稍不好,可能怨声载道。不过如果结果是好的,属下们还是会高呼“英明领导”。

战略思想必须贯彻始终。需要大家摆正心态,不要在意一时的得失。即使现在无法推动Code Review,不代表以后没有机会。下面的章节将介绍推动的阶段和每个阶段对应的策略。

4.2 阶段篇

我们将推动Code Review这件事情划分为四个阶段。这四个阶段一定是顺序发展的。但是每个阶段又可能直接退化到第一阶段。我称之为“逆水行舟,不进则退”。

reviewpharse

### 准备阶段 这个阶段要注意三点:培训、播种、除草。这一阶段的重点是让大家或多或少的知道Code Review;激发少部分人尝试Code Review的欲望;削弱反对派的声音。当某个团队中大部分都是赞同派时就可以开始下一阶段。

培训

首先看公司的情况。如果可以在全公司范围培训的。尽可能多培训几次。培训的主题抛砖引玉:首先如何写高质量的代码云云,然后再培训如何改进自己的代码云云,最后培训如何review别人的代码。一是宣传自己,二是让大家知道原来代码还可以这么写,三是培养一下自己的演讲技巧,四是减缓反对Code Review的情绪,五是增强赞同派的信心。所以多做培训总是有好处的。

播种

  • 有一部分人可以通过培训成为种子。
  • 你也需要找一些有力的帮手。这些帮手应该和你都是君子之交:平时点头问候、也不礼尚往来、也无直接利害关系。但是他们有应该有一个共同点:必须是各个团队的技术负责人或者技术最牛的人。你和他们怎么交流呢?抱着虚心学习的心态用Code Review交流。看过这些人的代码,你可能需要帮忙修复逻辑错误、优化代码。也可以和他们讨论一下设计/架构的问题。提出更好的解决方案,但也不能质疑别人之前的设计。这里review一定不能使用checklist。 你要是指出这些人的代码里多加了几个空格这种无伤大雅的问题。那你就别想继续推Code Review了。
  • 培养应届生。他们是最容易成为种子的人。以后也会成为公司的中坚力量。
  • 老板。你应该让老板知道不进行Code Review的危害。让他觉得我们应该找个时间尝试一下。

除草

有些人极力反对Code Review。他们觉得这占用了他们的编码时间;也可能源自他们之前的尝试。这群人的技术水平可能参差不齐,但是工作年限一般较长。技术大牛觉得你们这群杂兵就不要review我的代码了,反正我也汲取不到什么营养,还可能从我这里偷学点什么。技术一般的老人觉得我的代码怎么能公开呢?万一写的不好,威信全无。你需要慢慢转化他们的思维。你需要通过Code Review帮他们找出代码运行时确实会出现的bug。慢慢的,他们会觉得这种方法可以提升他们的效率,减少他们排错的时间。记住三点:绝对不要提无伤大雅的修改意见;绝对不要让别人大面积修改代码(即使你觉得代码结构实在混乱);绝对不要拿出你的checklist对照排查。这是一场温和的变革,不能意见不合就排挤/打压/遣散反对的人。总之一句话,化敌为友。我们需要将反对者影响的比例控制在某个阈值以下。

试点论证

现在已经有一个团队愿意尝试这件事了。这一阶段重要是让团队成员自发得出一条结论:

Code Review有利可图。

这结论应源于:

  1. 自身能力的提升。知道代码有哪些地方可以更优雅一些,能看出运行时错误,减少了debug时间,学习到编码技巧。
  2. 团队效率的提升。顺利看懂团队写的所有代码,修复其他成员引入的bug。
  3. 当自己请假时,有他人可以暂代你的工作。不会打扰你休假。
  4. 代码稳健。不为线上bug奔波。

结论已出,会进入推广阶段。

推广阶段

从一个团队,到其他的团队。这并不是一件非常困难的事情。只要那些团队有时间,就有尝试Code Review的机会。另外团队间交流/协作必不可少。以Code Review方式交流代码,潜移默化相关的团队。这一阶段结束的标志是大部分研发团队尝试使用Code Review,并保持3个月。

这一阶段的重点在于奖和速

奖励对Code Review的推动有贡献的人。迅速的推广传播也至关重要。公司不会有那么多时间等待你推广,这期间会有大量的变数(人员流动、团队重组、高层空降、KPI变更等等),所以越快越好。

巩固阶段

恭喜已经进入到了巩固阶段。这个阶段结束的标志就是研发团队进行review活动的比例和频率在持续下降。某些进行Code Review的团队已经放弃这一活动。

这一阶段的重点在于

惩罚不愿意进行Code Review的人/团队。这一阶段可以形成规范的Code Review checklist。 可以帮助研发团队整齐划一的编写代码。而在其他几个阶段我都不建议使用checklist进行教条式的Code Review。

4.3 小结

想要在公司层面大范围推动某件事,首先要让人信服。对于Code Review来说,需要基层和高层都赞同才行。要让赞同派发声,也要让反对派闭嘴。在大面积推广之前,你应该小心谨慎,步步为营,增加研发团队的认同感。始终要灌输Code Review有利可图这一理念。因为是你主导此事,所以一定要亲力亲为,决不能眼高手低:不review代码,也不写代码。但世间之事,哪能努力后就一定成功?倘若风云变幻,打回准备阶段。那也不必灰心,大侠请从头再来。

如果你技术水平还未到平均水平,仍要强推Code Review. 要么修炼自身技术;要么煽动技术大牛去推动Code Review。

第五章 总结

第一章流程部分:多人review需要注意分工协作,但是多人也容易导致无人负责。这一章主要是建立代码交流的流程。至于怎么反馈建议,使用什么工具,怎么保证这个通道畅通,并没有限制。

Code Review技巧分了两个章节。希望阅读后能有所启发。阅读代码的方式和阅读文章相似。但是读文章并没有跳转、递归、循环。在Code Review的考察点章节,可能有你似曾相识的言论,那就权当加深印象。我所写的是在Code Review经常/反复出现的代码问题,供大家参考。如果编码者看完这两章后若有所思,就已经达到目的。

第四章公司层面推动。仁者见仁,智者见智。从最不利的局面开始,如何一步步推进Code Review. 某些在公司顺风顺水、一呼百应的人完全可以忽略本文。我希望高级研发工程师和技术系高层看完后,能打开新的思路推动Code Review. Code Review这件事,毕竟和我们的职业活动息息相关,希望大家重视。

希望有人看过此文重燃起推动Code Review的念想

寓言故事

从2017年的7月5日的百度人工智能开发者大会说起。百度希望提供出来一系列的工具集来方便业务AI的开发者。这不由让我想起来摆渡者。

1
2
3
4
5
6
7
据说很久很久以前,美国的阿拉斯加州盛产黄金。
引淘金者蜂拥而至。
淘金者要搜遍阿拉斯加的每一条河流,筛出每一粒黄金。
摆渡者们日复一日为淘金者摆渡过河。
淘金者有时能淘到金子,但时常颗粒无收。
不管淘金者是否淘到金子,只要过河就要给摆渡者固定的佣金。
结果多年以后,阿拉斯加出现了大量贫困的淘金者和富裕的摆渡者。

摆渡者 => 百度 谐音之妙

争什么?

做平台的总要旱涝保收。创业者大多是淘金客。这就在于你找到金矿的几率*金子的价值是否远超你的成本。我们都知道初入此行业的人找到金矿的几率最大。后入者几率巨减。而每一个人的成本也不一样。怎么才是划算的?

后来我想如果金子那么显而易见,那估计早就被巨头们掠夺一空了。可见这世间好挖的AI金库差不多都已经被挖完了。

人工智能之争,争的是什么?大公司争平台,小公司争应用。但每一个公司争夺的都是时间和机会。这里一定又会倒掉一大批的公司。对于创业公司来说,除非几个创始人都是AI界响当当的人物。其他小角色还是不要去看这个机会了。风险远高收益。我指的是AI的核心算法和顶尖应用。如果你只是调用某些API做了某个特定领域的聊天客服。狭义上讲,你做的事情和AI一点关系都没有。不要谈什么广义的AI, 不要说什么AI产业的下游生态。本质上讲,你程序里简单写了一句a++, 这都应该算AI。你能比计算机算的快?肯定没有。在简单计算这一层面,计算机早就已经超越了你。向前推不到百年,计算机的简单计算能力还没有你快。

AI概念

所以现阶段AI这概念到底再宣扬什么?G狗围棋超越人类?那也仅仅是凭借其计算能力,再外加一点随机算法和剪枝。让你误认为计算机懂得围棋或者懂得"式"这一概念。其实不然。G狗不过是通过计算数出占了多少地盘。这个是非常精确的。但人类不一样。看"式"仅凭感觉。也就是人根本就没有数出黑白子各多少。凭借的是对图像的理解。而计算机对图像的理解仍然需要知道每一个像素点。人看事物的时候什么时候数过像素点?当然你可以说人脑其实本身也经过一系列的计算得到的,只是我们并不知道计算的方程是什么。

从广义的AI层面上讲,我们和计算机分别属于不同的物种。这两个物种之间必须靠程序员来做翻译。我们现在已经可以自动翻译中英,未来再将中文或者英文自动翻译为计算机语言就可以了。这样就完成了自动编程。

好了,现在得到了计算机专业应划归为文科的结论。唉,毕竟是翻译专业嘛。

结束语

大家有愿当摆渡者的,有愿意做淘金者的。而我希望大家成为金子。这样不管谁捡到了你,都会把你视为宝贝。怎么成为稀有的金子呢?那一定要特立独行,去摆脱芸芸众生的思量。

AI

杨梅

最近南方的杨梅下来了。但北京卖的杨梅却不知道从哪里运来的。

今天去市场买了很多杨梅。在摊位吃的时候,我觉得还挺好吃的,就多买了些。今年是第二年在北京吃杨梅。老婆说没有南方的杨梅好吃。所以她基本上没有吃。她还想送邻居一些。可能太不好吃,邻居也没有来拿。老婆之前偷偷在网上订购了江浙的杨梅,心想明天就到了。她觉得我今天已经吃了那么多杨梅,明天应该就不想吃了。我只能说她想多了。

最近南方一直在下雨,杨梅只有在晴天成熟才是甜的,在雨里只会变酸。如果南方不下雨,又是杨梅的季节,一定要去买杨梅。一年也就买一次,过季就不好吃了。

离婚律师

最近陪老婆看《离婚律师》。看到中途,老婆嫌声音太小了。我说那个叫吴文辉的角色已经老了,说话声音自然小呀,你看他病病殃殃的样子,可能下集就不行了呢,所以听不见他说什么也很正常。这电视剧有字幕呢,再对对嘴型就行了。老婆说不行,非让调大。结果我调到很大,还是听不见。感觉最有意思的角色是池海东。都这么大把年纪了,还在那里蹦蹦跳跳的。他就不累吗?但是看他跳来跳去真是特别好玩。

龙虾

早上买了一些龙虾,来做麻辣小龙虾。网上如何清理虾的视频看起来很麻烦:首先要去掉虾脚(非螯),然后用剪刀去掉虾头,拨出里面的黑色物。再然后掐虾尾中间,去掉虾线。我嫌麻烦只去掉了虾线。我觉得龙虾既然吃起来如此麻烦,为什么还要吃它?它也没有多少肉呀。还不如吃明虾和鱼。你说它好吃。这主要是靠炒料呀!生吃能好吃吗?那个炒料炒什么都好吃。所以我一直不太明白吃小龙虾的意义是什么。吃小龙虾有时还担心煮不熟,怕吃到肚子里得各种病。既然如此,直接用这个炒料炒肉吃就好了呀!还省去了清理虾和剥虾的时间。人们有时就是这么奇怪,花了不少力气,没吃到啥,还美其名曰:珍贵的美食。

奇葩说

奇葩说第四季结束了。最后几期还是很有看头的。之前的那几期完全就不需要看。说话是一门艺术,看奇葩说你就会发现,不管你离题是不是相差了十万八千里,只要你语气是对的,态度是诚恳的,总能拉到票的。所以说话一定要诚恳,语气一定要平和,待人一定要谦虚谨慎。有时我想知道他们除了没有讨论题目外,到底在讨论什么。所以奇葩说那100名观众是不是要换换了?另外除了那红蓝两个键,能不能再多给两个键呀。因为我实在看不下去了,我反对正方的发言,但是我也不支持反方,我被正方的无聊言论逼到马上要去反方的立场了。另外一个钮是反过来:被反方言论惹怒了,但是我还不想去正方。当然那些职业的辩手还是非常厉害的。

我在想第五季是不是会更差呢?让我们拭目以待。

PS4

最近我有想把PS4出租出去赚钱的想法。5000元押金,主机+两个12+游戏。每月租金200元。短租1月。每月再外加100元可以多租一款游戏。我觉得这个商业模式比较好,可以尝试一下。但是出租出去后,自己就没有游戏玩了。想想还是忍忍吧,暂时不外租了。

CSDN 时代

CSDN

最初写blog时,是在大学的时候。那时都是主站点的天下。程序员杂志影响力巨大。以程序员杂志起家的CSDN自然是程序员写作的首选。当时CSDN的竞争对手有JAVA eyes, 博客园,新浪微博等等。但是在编程方面影响力最大的还是CSDN. 所以我当时在CSDN上开创了blog, 起名帐前卒。一写就是数十年。主要是记录自己编码生涯的点点滴滴。除了如何进行编码和debug,就是电影看书、吃喝拉撒,当然也还有自己对生活的理解。现在的我再回看之前的博文,似乎总能回想起那个疯狂编码年代的故事。所以说写blog其实不是给别人看的,是给自己看的。只不过顺便兼顾了传道、授业、解惑。不过说到解惑,其实自己现在仍然很困惑。解人之惑,却解不了自己之惑。

当初CSDN的blog是可以自主添加一些计数器的JS脚本的。但是好景不长,总有恶人做恶:写些木马脚本什么的。所以CSDN就封禁了这功能。 当时我并没有觉得什么不妥,只不过在我的blog页面上消失了一个漂亮的计数器。

后来CSDN首页改版,放入了更多的文章,即使自己的文章推荐上了头条,也再也找不到在哪里了。

后来CSDN允许博客专家推荐自己的文章上头条,在那之后,上头条的荣誉感和胜利感也就随之消失。

几十年后的今天,CSDN对博客专家重新开启了自定义脚本。虽然CSDN又迈出一步,虽然我已是博客专家,但对此功能已了无兴趣。

现在CSDN又要求手机验证了,我都不想登陆CSDN了,就更别说在CSDN写blog了。

WordPress时代

Wordpress

godaddy进入中国了。可以申请域名了。不用再需要什么身份证、户口本、地址、电话才能申请个域名,省却了系统备案的时间和麻烦。于是就申请了chillyc.info. 为什么申请这个域名呢?嗯,其实我也是稀里糊涂的申请的。

我们当时几个人一起买了一个主机。主机上有我们几个人的wordpress搭建起来的blog。需要自己通过ftp上传各种php的plugins。需要自己作为admin编写博客,改写某些plugin。但是好景不长,很快就被黑掉,并植入了病毒。另外也需要主机继续购买续费。所以后来就放弃了这个wordpress搭建的blog。

但是搭建这个blog还是有很多的收获。首先有了自己的Google AD,后来使用自己申请的Google Analytics的获得的blog访问数据写了一篇论文。可惜后来Google被墙。AD和Analytics都需要翻墙。Google当时的这些服务又都是同步加载的。这导致blog加载的速度非常非常的慢,看客也就慢慢的流失了。不过当时并没有在chillyc.info上花主要精力。

Wordpress搭建blog站点的最大的问题就是没有预览功能。意味着你需要搭两个同样的wordpress服务,一个线上的一个线下的。然后再改改看看。另外当时还没有搭svn或者git,服务代码同步起来也特别麻烦。

Jekyll 与 Octopress

Octopress
再后来有了github。我开始准备将wordpress中的内容迁移到Octopress上。这是一个使用ruby写的软件服务。它将markdown的内容转变为静态html,然后再将内容传送到github上,最终通过github的域名解析变成自己的域名。这不需要自己再购买主机,省下一些银子。当时Octopress也提供了从wordpress到octopress的迁移程序。总之搞了一段时间后,终于将blog从wordpress迁移下来。其实自己并不喜欢markdown文法,虽然简单,但仍然没有wordpress的富文本编辑器简单,而且还需要各种html转义。没有鼠标点点,用vi写blog的效率还是下降了不少。还好后来渐渐习惯了vi+markdown。

有了自己的github库,再将chillyc.info wordpress的文章内容全部提交到了github上。自己也在Octopress的基础上修修改改:比如,将url从utf-8的汉字编码修改为了中文拼音。这种改变其实并没有提高什么google rank啥的。只是自己看着舒服了些。又如,将页面样式修改为动态的,添加一只追着骨头狂奔的狗。这改变又增加了不少blog的加载时间。

Octopress的问题在于:

  1. 首先要来一套ruby全家桶。
  2. 其次生成页面的速度实在慢的要死要死的,比八爪鱼爬的还要慢。

再后来我也懒得管这个blog了。因为毕竟没有什么访问量。索性还是将精力花在CSDN上。

Hexo

Hexo

从2015年开始因为V8+ES6+node,以及facebook的JS解析器啥的。JS再次火了起来。网上用JS写的服务越来越多。这次blog生成工具是hexo. 一个nodejs写成的服务。原理和Octopress一样。只不过语言换了换。

因为自己许多年没有在动chillyc.info上的blog。 ruby全家桶如何搭建自己已忘记的差不多了,又换了新的电脑。一切将要重新开始。那为什么不试试新的服务呢?于是使用的hexo. 很幸运的是hexo沿用了Octopress的设计。宣称简单到只要将source目录copy过来即可。我非常心动。于是下载了一套JS的全家桶,开始了前往Hexo的旅程。

但是这旅程实在不顺利。之前在Octopress上好好的markdown,到了Hexo上却总是报错。费劲千辛万苦改成Hexo认为合法的markdown。下一步就是找一个合适的theme. 有人推荐了pacman这个主题。这个主题的demo看起来很是不错。我使用了一下,却发现文章分类乱七八糟的。看了Hexo的官方文档才发现。其实是Hexo并不支持一篇文章多分类。这和Octopress的假设是冲突的。于是自己编写转换脚本,将分类转变为了tags。这样blog看起来就好看多了。我的blog里面还有latex。发现pacman支持的也不错。只不过需要自己先手工把过去的latex改成适合Mathjs的形式。程序员何苦为难程序员。为什么整那么多不同的格式?

好吧,搞定latex后,blog看起来不错了。而现在csdn上的登陆需要验证手机了。没有手机号是不是永远就不能登陆了?那我索性就把CSDN上这么多年的blog全部迁移到github上吧。找了一个Python写的csdn导出工具。把所有的CSDN的html文本转换成了markdown。然后放入到hexo。然后就hexo generate就卡死了,卡死了,卡死了…找了半天问题,发现还是因为blog篇数太多,不管hexo还是Octopress都没有对这些做过优化。写的blog越多,生成的就越慢。换句话说,不管hexo还是Octopress在github搭建这条路上都没有考虑到上万blog或者更多blog的情况。

后来去掉了pacman主题,速度立刻提升了不少,所以这个主题优化做的差。去掉pacman主题后,生成700篇文章从10分钟降到了1分钟。我现在使用的主题是next,性能优化的比较好。如果你只是尝鲜,或者你只是一时兴起要写blog,那随便什么主题都适合你。否则你就要仔细挑选一下主题了。我推荐next主题。虽然这个主题人用多了,就丧失了个性。但我还是推荐大家用一下。

搞定主题后,我又安插了Google AD和Google analytics。经过了那么多年,Google终于提供了异步加载的JS脚本。虽然我的网站访问量低,但是我仍然考虑着提升读者的访问速度。我不指望用Google AD赚到钱。但如果能赚到意外之财,我也会很开心。最近也出了简书等靠打赏存活的blog工具。但我觉得我用google AD赚到钱的概率应该比采用各种打赏的方式靠谱一些。

后记

为什么所有的github blog搭建方式都选择生成html? 如果直接写markdown,而在前端直接将markdown渲染成本应的样式,就没有必要把时间浪费在生成html上了。我觉得很大可能是github的原因。希望它未来会考虑将github blog做的更好。不过话又说回来,将这个功能做的更好,对它来说又有什么好处呢?除非它有更加宏伟的目标——将全世界的所有站点都迁移到github上。这样只用github搜索就足够了。不过显然这个目标太过宏伟了。

或许再过几年又会出来一款新的blog搭建工具。工具总是在推陈出新。所以折腾必不可少,计算机界有太多身后而身先的例子。或许某一天我们人类终将被历史淘汰,但我们也应坚持到那一天,不是吗?所以继续折腾吧。活到老就折腾到老吧。

因为感觉csdn的界面越来越乱了,是不是的还有各种广告。另外CSDN借工信部的名义强制要求输入手机号。像我这样根本没有手机的人,再也没有办法登陆了。所以还是把所有的blog迁移过来。从此我就再也不写csdn的blog.专心写我的这里的blog吧。

迁移工具从[email protected]:gaocegege/csdn-blog-export.git那边copy过来的。修改了一下code的生成地方和tags抽取。大家如果想将csdn的blog转换成markdown.可以参考我copy过来的这个工具。详细地址是: csdn_export

先安装一下pip
然后使用pip 安装一下 BeautifulSoup

1
2
3
4
sudo pip install BeautifulSoup
git clone https://github.com/chilly/csdn_export
cd csdn_export
./main.py -u [你的csdn的username] -f markdown

我之前的blog是blog.csdn.net/cctt_1。所以命令为:

1
./main.py -u cctt_1 -f markdown

Hi all,I should write this article in Chinese. Because there are many special Math words here. Maybe I will translate this article later.

首先是啥米叫catalan数,

h(n)=h(0)h(n1)+h(1)h(n2)+....+h(n2)h(1)+h(n1)h(0),h(0)=h(1)=1h(n)=h(0)h(n-1)+h(1)h(n-2)\\+....\\+h(n-2)h(1)+h(n-1)h(0),\\h(0)=h(1)=1

通项公式为

h(n)=1n+1(2nn)h(n)=\frac{1}{n+1}{\binom{2n}{n}}

另外还有

h(n)=h(1)h(n1)+h(2)h(n2)+...+h(n2)h(2)+h(n1)h(1),h(1)=1h(n)=h(1)h(n-1)+h(2)h(n-2)\\+...\\+h(n-2)h(2)+h(n-1)h(1),\\h(1)=1

其通项公式为

h(n)=1n(2n2n1)h(n)=\frac{1}{n}{\binom{2n-2}{n-1}}

首先是括号问题,很多问题都能转换为括号匹配问题,即在任何位置,左括号的数目都要大于等于右括号的数目。然后问你给n个左括号和n个右括号,共有多少种放置方法。具体解法为:

分析:

把左括号看作0,将右括号看作1,n个1和n个0组成的2n位二进制数。由于等待入栈的操作数按照1‥n的顺序排列、入栈的操作数b大于等于出栈的操作数a(a<=b),因此输出序列的总数目=由左而右扫描由n个1和n个0组成的2n位二进制数,1的累计数不小于0的累计数的方案种数。

在2n位二进制数中填入n个1的方案数为c(2n,n),不填1的其余n位自动填0。从中减去不符合要求(由左而右扫描,0的累计数大于1的累计数)的方案数即为所求。不符合要求的数的特征是由左而右扫描时,必然在某一奇数位2m+1位上首先出现m+1个0的累计数和m个1的累计数,此后的2(n-m)-1位上有n-m个1和n-m-1个0。如若把后面这2(n-m)-1位上的0和1互换,使之成为n-m个0和n-m-1个1,结果得1个由n+1个0和n-1个1组成的2n位数,即一个不合要求的数对应于一个由n+1个0和n-1个1组成的排列。

反过来,任何一个由n+1个0和n-1个1组成的2n位二进制数,由于0的个数多2个,2n为偶数,故必在某一个奇数位上出现0的累计数超过1的累计数。同样在后面部分0和1互换,使之成为由n个0和n个1组成的2n位数,即n+1个0和n-1个1组成的2n位数必对应一个不符合要求的数。因而不合要求的2n位数与n+1个0,n-1个1组成的排列一一对应。显然,不符合要求的方案数为c(2n,n+1)。由此得出

输出序列的总数目=

(2nn)(2nn+1)=n+11(2nn){\binom{2n}{n}}-{\binom{2n}{n+1}}=\frac{n+1}{1}{\binom{2n}{n}}

当然也可以看作第一对括号出现在什么位置,如果出现在1,2位置,则为h(0)h(2n-2),出现在3,4位置为h(2)h(2n-4),当然这里不可能出现在2,3位置,否则,左边h(1)是错误状态,不可以再递归做下去。所以原方程为

h(n)=h(0)h(2n2)+h(2)h(2n4)+...+h(2n4)h(2)+h(2n2)h(0)h(n)=h(0)h(2n-2)+h(2)h(2n-4)\\+...\\+h(2n-4)h(2)+h(2n-2)h(0)

这里将h(n)替换为f(n/2),即

h(n)=f(0)f(n1)+f(1)f(n2)+...=1n+1(2nn)h(n)=f(0)f(n-1)+f(1)f(n-2)+...\\=\frac{1}{n+1}{\binom{2n}{n}}

另外矩阵连乘,出入栈,人过街区问题和这个解法类似。

  1. 矩阵连乘即a1*a2*a3...*an这样的矩阵加括号表示成对共有多少种方法。首先可以选取某个矩阵作为起始矩阵,在这个矩阵上加括号,例如a2为起始矩阵,然后就变为a1(a2)a3...。然后如果a2与a3相乘则a1((a2)a3)...。看出来括号是否和刚才那个左右括号匹配的问题一样?所以这里共有2n个括号,然后求放置正确括号位置的种类有多少。因为最初的一对括号无用,所以这里其实有2n-2个括号,立即得到结果为:

1n(2n2n1)\frac{1}{n}{\binom{2n-2}{n-1}}

其实就是

g(n)=f(2n2)=h(n1)g(n)=f(2n-2)=h(n-1)

带入即可。

  1. 下面是问n个数出入栈,共有多少种出入栈的方式?进栈看作左括号,出栈看作右括号,然后瞬间变为左右括号匹配问题。结果依旧是

1n+1(2nn)\frac{1}{n+1}{\binom{2n}{n}}

因为第一个括号对就决定了结果的顺序,所以是2n个括号,这个与问题1有所不同。

  1. 然后是人过2n个街区工作,看作方格子,即左右走向n个街区,南北走向n个街区,但是这个家伙不会穿越但是可以碰到家到办公室的对角线,问有多少种可能的道路走法。这里因为没有通过对角线,所以走了k个左右走向的街区,最多只能再走k个南北走向的街区,否则就会穿越对角线。所以可以看作是栈问题,塞进去k个数只能弹出k个数。所以结果同2.
  2. 凸多边形区域划分三角形的方法数有多少?划分的三角形不能重叠(除三边可以重叠外)。首先选一条基边(因为划分必然要用到基边),一个顶点。图1中选中一条基边,一个顶点后,左边剩余1条基边(红色),右边剩余n-2条;图二中左边剩余两条基边,右边剩余n-3条。其中n为凸多边形顶点数。则有

f(n)=f(1)f(n2)+f(2)f(n3)+....+f(n2)f(1)f(n)=f(1)f(n-2)+f(2)f(n-3)\\+....\\+f(n-2)f(1)

  1. 圆上选择2n个点,将这些点对连接起来,且所得n条线段不相交,求可行方法数。首先选择两个点,左边剩余0个点,右边剩余2n-2个点继续这样连接。下一次选择,左边剩余两个点,右边剩余2n-4继续选择…

f(2n)=f(0)f(2n2)+f(2)f(2n4)+...f(2n)=f(0)f(2n-2)+f(2)f(2n-4)+...

f(2n)=h(n)f(2n)=h(n)

f(2n)=h(0)h(n1)+h(1)h(n2)+...=1n+1(2nn)f(2n)=h(0)h(n-1)+h(1)h(n-2)+...\\=\frac{1}{n+1}{\binom{2n}{n}}

  1. n个节点构造多少种不同的二叉树。这个问题可以转换为括号问题,与连乘不同的是,它的第一对括号决定了它的树根。当选择一个节点,左边可以有0个,右边有n-1个;左边有1个,右边n-2个…所以

g(n)=f(2n)=h(n)=1n+1(2nn)g(n)=f(2n)=h(n)=\frac{1}{n+1}{\binom{2n}{n}}

下面转载冷笑话:

从前有棵树,叫高数,树上挂了很多人
很久很久以前,在拉格朗日照耀下,有几座城:分别是常微分方城和偏微分方城这两座兄弟城,还有数理方程、随机过城。从这几座城里流出了几条溪,比较著名的 有:柯溪、数学分溪、泛函分溪、回归分溪、时间序列分溪等。其中某几条溪和支流汇聚在一起,形成了解析几河、微分几河、黎曼几河三条大河。

河边有座古老的海森堡,里面生活着亥霍母子,穿着德布罗衣、卢瑟服、门捷列服,这样就不会被开尔蚊骚扰,被河里的薛定鳄咬伤。城堡门口两边摆放着牛墩和道 尔墩,出去便是鲍林。鲍林里面的树非常多:有高等代树、抽象代树、线性代树、实变函树、复变函树、数值代树等,还有长满了傅立叶,开满了范德花的级 树…人们专门在这些树边放了许多的盖(概)桶,高桶,这是用来放尸体的,因为,挂在上面的人,太多了,太多了…

这些人死后就葬在微积坟,坟的后面是一片广阔的麦克劳林,林子里有一只费马,它喜欢在柯溪喝水,溪里撒着用高丝做成的ε-网,有时可以捕捉到二次剩鱼。
后来,芬斯勒几河改道,几河不能同调,工程师李群不得不微分流形,调河分溪。几河分溪以后,水量大涨,建了个测渡也没有效果,还是挂了很多人,连非交换代树都挂满了,不得不弄到动力系桶里扔掉。
有些人不想挂在树上,索性投入了数值逼井(近)。结果投井的人发现井下生活着线性回龟和非线性回龟两种龟:前一种最为常见的是简单线性回龟和多元线性回龟,它们都喜欢吃最小二橙。

柯溪经过不等市,渐近县和极县,这里房子的屋顶都是用伽罗瓦盖的,人们的主食是无穷小粮。

极县旁有一座道观叫线性无观,线性无观里有很多道士叫做多项士,道长比较二,也叫二项士。线性无观旁有一座庙叫做香寺,长老叫做满志,排出咀阵,守卫着一座塔方。一天二项士拎着马尔可夫链来踢馆,满志曰:“正定!正定!吾级数太低,愿以郑太求和,道友合同否?”二项士惊呼:“特真值啊!”立退。不料满志此人置信度太低,不以郑太求和,却要郑太回归。二项式大怒在密度函树下展开标准分布,布里包了两个钗钗,分别是标准钗和方钗。满志见状央(鞅)求饶命。二项式将其关到希尔伯特空间,命巴纳赫看守。后来,巴纳赫让其付饭钱,满志念已缴钱便贪多吃,结果在无参树下被噎死(贝叶斯)。

0%