Android程序员面试会遇到的算法(part 4 消息队列的应
好久没有更新了，前段时间因为签证的问题一直很闹心所以没有写东西。
今天虽然依然没有好消息，而且按照往年的数据，现在还抽不中H1b的估计都没戏了，也可能我的硅谷梦就会就此破灭。。。
但是想了想，生活还得继续，学习不能停下。我还是要按照正常的节奏来。
这一期就主要给大家介绍在安卓应用或者轮子中最常见的一个设计，就是消息队列。
message-queue-small.png
我这次会以一个简单的例子来一步步的展示消息队列这种设计的应用，最后会借鉴Java和安卓源码中对消息队列实现的实例来做一个简化版的代码，希望大家在看完这篇文章之后在自己今后的app开发，或者轮子开发中能利用消息队列设计来优化代码结构，让代码更加可读。
1.网络请求（Volley）
相信大部分安卓开发者都有用过这个叫Volley的网络请求库，底层的网络请求实际上是用HttpUrlConnection类或者HttpClient这个库做的。Volley在这些基础库上做了封装，例如线程的控制，缓存和回调。这里我们详细说说大部分网络请求队列的处理。
一个最基本最简单的设计是，使用一个线程（非主线程），不停的从一个队列中获取请求，处理完毕之后从队列抛出并且发射回调，回调确保在主线程运行。
实现起来非常简单，这里借鉴Volley源码的设计，简化一下：
/**
简化版本的请求类，包含请求的Url和一个Runnable 回调
**/
class Request{
public String requestUrl;
public Runnable callback;
public Request(String url, Runnable callback)
{
this.requestUrl = url;
this.callback = callback;
}
}
//消息队列
Queue<Request> requestQueue = new LinkedList<Request>();
new Thread( new Runnable(){
public void run(){
//启动一个新的线程，用一个True的while循环不停的从队列里面获取第一个request并且处理
while(true){
if( !requestQueue.isEmpty() ){
Request request = requestQueue.poll();
String response = // 处理request 的 url，这一步将是耗时的操作，省略细节
new Handler( Looper.getMainLooper() ).post( request.callback )
}
}
}
}).start();
上面这一系列代码就把我们的准备工作做好了。那么往这个傻瓜版轮子里面添加一个请求就非常简单了。
requestQueue.add( new Request("http.....", new Runnable( -> //do something )) );
就这样，一个简化版的网络请求的轮子就完成了，是不是很简单，虽然我们没有考虑同步，缓存等问题，但其实看过Volley源码的朋友也应该清楚，Volley的核心就是这样的队列，只不过不是一个队列，而是两种队列(一个队列真正的进行网络请求，一个是尝试从缓存中找对应request的返回内容)
代码的核心也就是用while循环不停的弹出请求，再处理而已。
2.发送延迟消息
消息队列的还有一种玩法就是发送延迟消息，比如说我想控制当前发送的消息在三秒之后处理，那这样应该怎么写我们的代码呢，毕竟在网络请求的例子里面，我们完全不在乎消息的执行顺序，把请求丢进队列之后就就开始等待回调了。
这个时候我们可以采用链表这个数据结构来取代队列(当然Java里面链表可以作为队列的实例)，按照每个请求或者消息的执行时间进行排序。
废话不多说，先上简版代码。
//一个消息的类结构，除了runnable，还有一个该Message需要被执行的时间execTime，两个引用，指向该Message在链表中的前任节点和后继节点。
public class Message{
public long execTime = -1;
public Runnable task;
public Message prev;
public Message next;
public Message(Runnable runnable, long milliSec){
this.task = runnable;
this.execTime = milliSec;
}
}
public class MessageQueue{
//维持两个dummy的头和尾作为我们消息链表的头和尾，这样做的好处是当我们插入新Message时，不需要考虑头尾为Null的情况，这样代码写起来更加简洁，也是一个小技巧。
//头的执行时间设置为-1，尾是Long的最大值，这样可以保证其他正常的Message肯定会落在这两个点之间。
private Message head = new Message(null,-1);
private Message tail = new Message(null,Long.MAX_VALUE);
public MessageQueue(){
head.next = tail;
tail.prev = next;
}
public void run(){
new Thread( new Runnable(){
public void run(){
//用死循环来不停处理消息
while(true){
//这里是关键，当头不是dummy头，并且当前时间是大于或者等于头节点的执行时间的时候，我们可以执行头节点的任务task。
if( head.next != tail && System.currentTimeMillis()>= head.next.execTime ){
//执行的过程需要把头结点拿出来并且从链表结构中删除
Message current = head.next;
Message next = current.next;
current.task.run();
current.next = null;
current.prev =null;
head.next = next;
next.prev = head;
}
}
}
}).start();
}
public void post(Runnable task){
//如果是纯post，那么把消息放在最尾部
Message message = new Message( task, System.currentMilliSec() );
Message prev = tail.prev;
prev.next = message;
message.prev = prev;
message.next = tail;
tail.prev = message;
}
public void postDelay(Runnable task, long milliSec){
//如果是延迟消息，生成的Message的执行时间是当前时间+延迟的秒数。
Message message = new Message( task, System.currentMilliSec()+milliSec);
//这里使用一个while循环去找第一个执行时间在新创建的Message之前的Message，新创建的Message就要插在它后面。
Message target = tail;
while(target.execTime>= message.execTime){
target = target.prev;
}
Message next = target.next;
message.prev = target;
target.next = message;
message.next = next;
next.prev = message;
}
}
上述代码有几个比较关键的点。
- 消息采用链表的方式存储，为的是方便插入新的消息，每次插入尾部的时间复杂度为O(1),插入中间的复杂度为O(n),大家可以想想如果换成数组会是什么复杂度。
- 代码中可以用两个Dummy node作为头和尾，这样我们每次插入新消息的时候不需要检查空指针， 如果头为空，我们插入Message还需要做
if(head == null){ head = message } else if( tail == null ){head.next = message; tail = message}这样的检查。
3.每次发送延迟消息的时候，遍历循环找到第一个时间比当前要插入的消息的时间小。以下面这个图为例子。
Screen Shot 2018-05-01 at 10.34.06 PM.png
当前插入Message时间为3的时候，它需要插入在1和5中间，那么1节点就是我们上面代码循环中的最后的Target了。
这样，我们就完成了一个延迟消息的轮子了！哈哈，调用代码非常简单。
MessageQueue queue = new MessageQueue();
//开启queue的while循环
queue.run();
queue.post( new Runnable(....) )
//三秒之后执行
queue.postDelay( new Runnable(...) , 3*1000 )
大家可能觉得post，和postDelay看起来非常眼熟，没错，这个就是安卓里面Handler的经典方法
Screen Shot 2018-05-01 at 10.39.09 PM.png
在安卓系统中的源代码里面，postDelay就是运用上述的原理，只不过安卓系统对回收Message还有额外的处理。但是对于延迟消息的发送，安卓的Handler就是对其对应的Looper里面的消息链表进行处理，比较执行时间从而实现延迟消息发送的。
最后大家再思考一下，像上述代码的例子里面，延迟三秒，是不是精确的做到了在当前时间的三秒后运行
答案当然是NO!
在这个设计下，我们只能保证：
假如消息A延迟的秒数为X，当前时间为Y，系统能保证A不会在X+Y之前执行。 这样其实很好理解，因为如果使用队列来执行代码的话，你永远不知道你前面那个Message的执行时间是多少，假如前面的Message执行时间异常的长。。。。那么轮到当前Message执行的时候，肯定会比它自己的execTime偏后。但是这是可接受的。
如果我们需要严格让每个Message按照设计的时间执行，那就需要Alarm，类似闹钟的设计了。大家有兴趣可以想想看怎么用最基本的数据结构实现。
3.线程池的实现
说到线程池，我一直有很多疑惑，网上很多文章都会以线程池最全解析，或者史上最详细Java线程池原理诸如此类的Title为标题，但却主要以怎么操作Java线程池的API为内容。
在我看来这类文章都是耍流氓，对于一个合格的Java开发来说，如果连API都不会查，那干脆别干了，还需要你专门写一篇文章来介绍API怎么用嘛。。。。。我也一直在问我自己，为啥大家都对源代码没有兴趣。。。。
download.jpeg
这个章节我就会用简单版本的代码把线程池的实现给展示一下。
其实线程池的实现很简单，就是使用一个队列若干Thread就行了。
public class ThreadPool{
//用一个Set或者其他数据结构把创建的线程保存起来，为的是方便以后获取线程的handle，做其他操作。
Set<WorkerThread> set = null;
private Queue<Runnable> queue;
//初始化线程池，创建内部类WorkerThread并且启动它
public ThreadPool(int size){
for( int i = 0 ;i < size ;i++ ){
WorkerThread t = new WorkerThread();
t.start();
set.add( t );
}
queue = new LinkedList<Runnable>();
}
//submit一个runnable进线程池
public void submit(Runnable runnable){
synchronized (queue){
queue.add(runnable);
}
}
//WorkerThread用一个死循环不停的去向Runnable队列拿Runnable执行。
public class WorkerThread extends Thread{
@Override
public void run() {
super.run();
while(true){
synchronized (queue){
if( !queue.isEmpty() ){
Runnable current = queue.poll();
current.run();
}
}
}
}
}
}
这样，一个简单版本的线程池就完成了。。。。使用一组Thread，不停的向Runnable队列去拿Runnable执行就好了。。。看起来完全没有技术含量。但是这却是Java的线程池的基本原理。大家抽空可以去看看源码。还有很多细节我都没有写出来，比如说怎么shutdown线程池，或者线程池内部的WorkerThread怎么处理异常。怎么设置最大线程数量等等。
注意点不多，就是要使用synchronized对并发部分的代码做好同步就可以了。
调用代码简单
ThreadPool pool = new ThreadPool(5);
pool.submit(new Runnable(...))
华丽丽的分割线
后记
这一期的分享结束啦，其实上面三个例子都是大部分安卓开发者会接触到的，如果稍微有点兴趣和耐心就可以明白其原理，都是用最简单的数据结构加最“幼稚”的设计完成的。
最后我还想说，希望每个安卓开发者都能有一颗疑问的心， 比如线程池，基于Java的Thread这个类，怎么去完成一个线程池的实现，如果每次在使用这些API之后都能问问自己，为什么，保持一颗愿意提问的心，这些都能学会。愿大家都能有且保持这种热忱。
我也需要时刻提醒自己，无论能不能去硅谷都好，都要一直有这种热情，一刻也不能懈怠。如果我的热情因为不能去硅谷而破灭，那我的坚持也太脆弱了。
